자바 이 진 트 리 를 옮 겨 다 니 는 일반적인 방법

앞 순 서 를 옮 겨 다 니 고 중간 순 서 를 옮 겨 다 니 며 후속 적 으로 옮 겨 다 닐 때 서로 다른 실현 방식(재 귀 방식,비 재 귀)을 사용 하 더 라 도 그들의 알고리즘 구 조 는 매우 유사 성 을 가진다.따라서 앞의 세 가 지 를 옮 겨 다 니 는 것 에 대해 우 리 는 통용 되 는 해결 구 조 를 정리 하여 이 진 트 리 문 제 를 해결 할 때 사용 할 수 있 도록 할 것 이다.
귀속 방식
재 귀 방식 이 이 진 트 리 를 옮 겨 다 닐 때 앞 순 서 를 옮 겨 다 니 거나 중간 순 서 를 옮 겨 다 니 거나 후속 적 으로 옮 겨 다 니 는 방식 이 든 가장 큰 차이 점 은 노드 데이터 에 대한 접근 위치 가 다르다 는 것 이다.그 밖 에 그 구조 가 완전히 일치 하기 때문에 우 리 는 다음 과 같은 구조 구 조 를 정리 했다.

void traverse(TreeNode root) {
    //    
    if(root == null) return;
    //     
    traverse(root.left);
    //     
    traverse(root.right);
    //     
}

주석 에 대응 하 는 위치 접근 데 이 터 는 서로 다른 스 트 리밍 방식 을 실현 할 수 있 습 니 다.
예 를 들 어 앞 순 서 를 옮 겨 다 니 기:

void traverse(TreeNode root) {
    if(root == null) return;
    visit(root);
    traverse(root.left);
    traverse(root.right);
}

같은 중간 순서 로 옮 겨 다 니 기:

void traverse(TreeNode root) {
    if(root ==null) return;
    traverse(root.left);
    visit(root);
    traverse(root.right);
}

다음 스 트 리밍:

void traverse(TreeNode root) {
    if(root ==null) return;
    traverse(root.left);
    traverse(root.right)
}

아주 쉬 운 가!!
비 귀속 방식
이 진 트 리 는 재 귀적 이지 않 고 솔직히 여러 가지 실현 방식 이 있 지만 본질 적 으로 전체 가 옮 겨 다 니 는 과정 을 모 의 해서 이 루어 진다.
이해 하기 편리 하도록 그 중에서 앞 순 서 는 옮 겨 다 니 고 중간 순 서 는 옮 겨 다 니 며 뒤 순 서 는 우리 가 비슷 한 알고리즘 구 조 를 사용한다.
전체 알고리즘 프레임 워 크 는 다음 과 같 습 니 다.

 public void traverse(TreeNode root) {
    //     
    if (root == null) {
      return;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
       //     ，            ，    
      if (current != null) {
        //     visit(current)
        stack.push(current);
        current = current.left;
      } else {
        //    ，        ，  ，        
        current = stack.pop();
		//     visit(current);
        current = current.right;
      }
    }
  }

후 서 를 옮 겨 다 니 는 순 서 는**"왼쪽->오른쪽->뿌리"입 니 다.앞 순서 로 옮 겨 다 니 는"뿌리->왼쪽->오른쪽"과 비교 하면 매우 유사 한 것 같 습 니 다.우 리 는 위의 프레임 워 크 를 수정 하여 앞 순서 에서 뒤 순서 로 옮 겨 다 닐 수 있 습 니까?
답 은 긍정 적 이다.우 리 는 먼저 옮 겨 다 니 는 순 서 를 구 할 수 있다.'뿌리->오른쪽->왼쪽'*'의 노드 서열 을 구 한 다음 에 순 서 를 바 꾸 면 바로 뒤의 순서 인 좌우 뿌리 이다.그리고 순 서 를 옮 겨 다 니 는 것 이 오른쪽 과 왼쪽 이 라면 하기 쉽 습 니 다.예전 에 옮 겨 다 니 는 코드 에서 두 줄 을 바 꾸 면 됩 니 다.
따라서 두 개의 스 택 을 선택 할 수 있 습 니 다.하 나 는 옮 겨 다 니 고 다른 하 나 는 결과 의 역순 에 사용 할 수 있 습 니 다.
구현 코드 는 다음 과 같 습 니 다:

//           
  public void postOrderTraverse(TreeNode root){
    Stack<TreeNode> stack = new Stack<>();
    Stack<Integer> res = new Stack<>();
    TreeNode cur = root;
    while (cur!=null || !stack.isEmpty()) {
      if (cur!=null){
        stack.push(cur);
        res.push(cur.val);
        cur = cur.right; //   
      }else{
        cur = stack.pop();
        cur = cur.left;  //    
      }
    }
    while (!res.isEmpty()){
      visit(res.pop());
    }
  }

이로써 재 귀적 으로 완성 되 지 않 으 면 쉽 지 않 겠 습 니까?!
다음 에 마지막 층 차 를 볼 수 있 습 니 다.
층 차 를 편력 하 다
층 차 를 옮 겨 다 니 는 것 은 본질 적 으로 거세 판 의 범위 가 우선 입 니 다.우 리 는 여기 서 BFS 알고리즘 의 구 조 를 직접 제시 합 니 다.

/**
*       start     target，         
**/
int BFS(Node start,Node target){
    Queue<Node> q; //      
    Set<Node> visited: //         byte       
    int step = 0; //      
    //       
    q.add(start);
    visited.offer(start);
    while(q not empty) {
        //    sz   q.size()，    sz      q.size()
        int sz = q.size();
        //           
        for(int i =0 ; i < sz; i++) {
            Node cur = q.poll();
            //       
            if(cur is target) {
                return step;
            }
            //        
            for(Node n:cur.adjs) {
                //        
                if(n is not int visited) {
                    visitd.add(n);
                    q.offer(n);
                }
            }
        }
        //     
        step++;
    }
}

여기 서 우 리 는 BFS 의 틀 을 빌려 그 실현 방법 을 직접 제시한다.

void LevelOrder(TreeNode root){
    //    ，   
    Queue<TreeNode> queue;
    queue.add(root);
    while( !queue.isEmpty()) {
        //  
        TreeNode cur = queue.poll();
        //    
        visit(cur);
        //       
        if(cur.left !=null) queue.add(cur.left);
        if(cur.right !=null) queue.add(cur.right);
    }
}

BFS 에 비해 우 리 는 층 차 를 옮 겨 다 니 며 많은 것 이 부족 하 다 는 것 을 알 게 될 것 이다.예 를 들 어 방문 한 노드(이 진 트 리 자체 의 구조 적 특징,반복 적 으로 옮 겨 다 닐 수 없 음)를 표시 하지 않 아 도 되 고 대기 열 에 있 는 노드 를 확산 시 킬 필요 도 없다 는 등 이다.
총결산
이로써 이 진 트 리 의 네 가지 옮 겨 다 니 는 방식 이 완성 되 었 다.우 리 는 이 진 트 리 의 모든 옮 겨 다 니 는 방식 이 통용 되 는 알고리즘 프레임 워 크 를 가지 고 있 음 을 발견 했다.알고리즘 자체 의 프레임 워 크 만 파악 하면 실현 코드 를 쉽게 쓸 수 있다.
이상 은 자바 이 진 트 리 를 옮 겨 다 니 는 데 자주 사용 되 는 방법 에 대한 상세 한 내용 입 니 다.자바 이 진 트 리 를 옮 겨 다 니 는 자 료 는 저희 의 다른 관련 글 을 주목 하 세 요!