이 진 트 리: 먼저 순차 적 으로 옮 겨 다 니 고 중간 순 서 를 옮 겨 다 니 며 재 귀적 으로 이 루어 집 니 다.

데이터 구조 에 있어 서 옮 겨 다 니 는 것 은 흔히 볼 수 있 는 조작 이다.이 진 트 리 는 기본 적 인 데이터 구조 로 모든 노드 의 아들 수가 2 보다 많 지 않 은 나무 이다.이 진 트 리 의 노드 설명 은 다음 과 같 습 니 다.

class Node{  
    public int value;  
    public Node left;  
    public Node right;  
    public Node(int v){  
        this.value=v;  
        this.left=null;  
        this.right=null;  
    }  
      
}  

이 진 트 리 의 옮 겨 다 니 는 것 은 주로 먼저 옮 겨 다 니 고 중간 순 서 를 옮 겨 다 니 며 뒷 순 서 를 옮 겨 다 니 며 네 가지 방식 이 있 습 니 다. 다음은 하나씩 소개 하 겠 습 니 다.1. 먼저 차례 를 옮 겨 다 니 며 노드 에 대한 방문 작업 은 아들 이 방문 되 기 전에 이 루어 집 니 다.다시 말 하면 먼저 방문 노드 를 옮 겨 다 니 는 순 서 는 뿌리 노드 - 왼쪽 아들 - 오른쪽 아들 이다.나 무 는 재 귀 를 통 해 정의 할 수 있 기 때문에 나무의 흔 한 조작 은 재 귀 로 이 루어 지 는 것 이 편리 하고 뚜렷 하 다.재 귀적 으로 실 현 된 코드 는 다음 과 같다.

재 귀 코드 를 통 해 알 수 있 듯 이 이 재 귀 는 꼬리 재 귀 (꼬리 재 귀 즉 재 귀 형식 은 함수 말미 또는 함수 가 곧 돌아 오기 전에) 이다.마지막 재 귀적 인 재 귀적 호출 은 스 택 으로 호출 된 정 보 를 저장 해 야 하 며 데이터 규모 가 클 때 스 택 공간 을 넘 기 쉽다.현재 대부분의 컴 파일 러 는 자동 으로 꼬리 재 귀 를 제거 할 수 있 지만 그래도 우 리 는 스스로 제거 해도 무방 하 다.비 재 귀적 우선 순위 알고리즘 기본 사고: 스 택 사용
(1). 노드 를 만 나 서 방문 한 다음 에 스 택 을 누 르 고 왼쪽 트 리 를 옮 겨 다 닙 니 다.
(2). 왼쪽 나무 가 옮 겨 다 니 는 것 이 끝 난 후에 스 택 꼭대기 에서 이 노드 를 꺼 내 오른쪽 아들 에 게 가리 키 고 a 절 차 를 계속 합 니 다.
(3). 모든 노드 가 마지막 으로 방문 한 트 리 노드 가 비어 있 을 때 중단 합 니 다.
구현 코드 는 다음 과 같 습 니 다:

class BinaryTreeTraversal {  
    /** 
     * @param root      
     *        
     */  
    public static void preOrderRec(Node root){  
        if(root!=null){  
            System.out.println(root.value);  
            preOrderRec(root.left);  
            preOrderRec(root.right);  
        }  
    }  

2. 중간 순 서 를 옮 겨 다 니 는 경로 가 먼저 옮 겨 다 니 는 경로 와 똑 같 습 니 다.그 실현 의 사고방식 도 선착순 과 매우 비슷 하 다.그 주요 한 차이 점 은 방문 노드 의 순서 가 다르다 는 것 이다. 중 서 는 모든 왼쪽 아들 을 방문 한 후에 뿌리 노드 를 방문 하고 마지막 으로 오른쪽 아들, 즉 왼쪽 아들 - 뿌리 노드 - 오른쪽 아들 을 방문 하 는 것 이다.
재 귀적 으로 실 현 된 코드 는 다음 과 같다.

/** 
     * @param root      
     *        
     */  
    public static void inOrderRec(Node root){  
        if(root!=null){  
            preOrderRec(root.left);  
            System.out.println(root.value);  
            preOrderRec(root.right);  
        }  
    }  

4. 567917. 후 서 는 후 서 를 옮 겨 다 니 고 중 서 를 옮 겨 다 니 며 먼저 옮 겨 다 니 는 경로 도 똑 같 습 니 다.주요 한 차이 점 은 방문 노드 를 옮 겨 다 니 는 순서 가 왼쪽 아들 과 오른쪽 아들 을 먼저 방문 하고 마지막 으로 방문 노드, 즉 왼쪽 아들 - 오른쪽 아들 - 뿌리 노드 이다
순환 실현 사고 와 중 서 를 옮 겨 다 니 는 것 과 선 서 를 옮 겨 다 니 는 것 이 비슷 하 다. 코드 는 다음 과 같다.

    /** 
     * @param root      
     *        
     */  
    public static void postOrderRec(Node root){  
        if(root!=null){  
            preOrderRec(root.left);  
            preOrderRec(root.right);  
            System.out.println(root.value);  
        }  
    }