자바 이 진 트 리 의 네 가지 옮 겨 다 니 기(재 귀 와 비 재 귀)

이 진 트 리 의 옮 겨 다 니 는 것 은 앞 순서,중간 순서,뒤 순서,차원 으로 나 눌 수 있다.
앞 뒤 는 중간 노드,즉 앞 순 서 를 옮 겨 다 니 는 것 을 말 합 니 다.노드 를 옮 겨 다 니 는 순 서 는 중->왼쪽->오른쪽 입 니 다.
중간 순 서 를 옮 겨 다 니 고 노드 를 옮 겨 다 니 는 순 서 는 왼쪽->중->오른쪽 이다.
뒤의 순서 가 옮 겨 다 니 고 노드 를 옮 겨 다 니 는 순 서 는 왼쪽->오른쪽->중 입 니 다.
앞 순 서 를 편력 하 다.

순환 실현

public void preorder_Traversal(TreeNode root)
  {
    if(root==null)return;
    
    //          
    System.out.print(root.val+" ");
    
    preorder_Traversal(root.left);
    preorder_Traversal(root.right);
  }

비 귀속 과정 은 다음 과 같다.
1.한 노드 를 옮 겨 다 닐 때마다 먼저 노드 가 스 택 에 들 어간 다음 에 현재 노드 의 왼쪽 노드 를 찾 습 니 다.(이전 순서 로 옮 겨 다 니 기 때문에 노드 가 스 택 에 들 어가 기 전에 노드 에 접근 할 수 있 습 니 다)
2.특정한 노드 의 왼쪽 노드 가 비어 있 지 않 을 때 반복 과정 1.
3.왼쪽 노드 가 비어 있 을 때 현재 노드 를 창고 에서 꺼 내 고 이 를 통 해 오른쪽 노드 를 찾 습 니 다.오른쪽 노드 가 비어 있 지 않 을 때 반복 과정 1-2
4.오른쪽 노드 도 비어 있 을 때 이전 노드 의 부모 노드 로 돌아 갑 니 다.(즉,현재 노드 가 스 택 에서 나 왔 기 때문에 현재 스 택 에서 맨 윗 노드 는 현재 노드 의 부모 노드 입 니 다)
비 귀속 실현

public void preorder(TreeNode root)
  {
    Stack<TreeNode>  stack=new Stack<>();
    while(root!=null||!stack.isEmpty())
    {
      //       ，   ，                
      //       ，             ，      ，         。
      while(root!=null)
      {
        System.out.print(root.val+" ");
        stack.push(root);
        root=root.left;
      }
      if(!stack.empty())
      {
        //         ，     ，          stack    
        root=stack.pop();
        root=root.right;
      }
    }
  }

중간 순서 로 옮 겨 다 닌 다.

순환 실현

public void inorder_Traversal(TreeNode root)
  {
    if(root==null)return;
    inorder_Traversal(root.left);
    
     //          
    System.out.print(root.val+" ");
    
    inorder_Traversal(root.right);
  }

비 귀속
앞의 순서,중간 순 서 를 비교 해 보면 코드 가 거의 똑 같 지만 유일한 차이 점 은 방문 노드 의 위치 가 다르다 는 것 이다.중간 순 서 는 왼쪽 노드 가 방문 되 었 거나 존재 하지 않 을 때 중간 노드 를 방문 할 수 있다 는 것 이다.그래서 여기 서 방문 노드 의 위 치 는 왼쪽 노드 가 존재 하지 않 을 때,즉 노드 가 스 택 에서 나 올 때 이다.즉,왼쪽 노드 가 존재 하지 않 을 때 방문 하 는 것 이다.
비 귀속 실현

public void Inorder(TreeNode root)
  {
    Stack<TreeNode> stack=new Stack<>();
    while(root!=null||!stack.isEmpty())
    {
      //       ，   ，                
      while(root!=null)
      {
        stack.push(root);
        root=root.left;
      }
      //      ，          ，       ，              ，  
               
      if(!stack.empty())
      {
        root=stack.pop();
        System.out.print(root.val+" ");
        root=root.right;
      }
    }
  }

뒤 순 서 를 옮 겨 다 닌 다.

순환 실현

public void postorder_Traversal(TreeNode root)
  {
    if(root==null)return;
    postorder_Traversal(root.left);
    postorder_Traversal(root.right);
    
     //          
    System.out.print(root.val+" ");
  }

비 귀속 버 전 1
두 개의 스 택 을 통 해 우리 의 노드 와 표시 위 치 를 저장 합 니 다.과정 은 다음 과 같 습 니 다.
1.한 노드 를 옮 겨 다 닐 때마다 먼저 노드 가 스 택 s 에 들 어가 고 s2 가 스 택 의 표지 위치 0 에 들 어간 다음 에 현재 노드 의 왼쪽 노드 를 찾 습 니 다.
2.특정한 노드 의 왼쪽 노드 가 비어 있 지 않 을 때 반복 과정 1.
3.왼쪽 노드 가 비어 있 을 때 현재 노드 peek 를 꺼 냅 니 다(노드 를 꺼 내 려 고 하지만 스 택 에 이 노드 가 있 습 니 다).그리고 이때 s2 가 스 택 꼭대기 에 대응 하 는 표지 위 치 를 1 로 바 꾸 고 이 를 통 해 오른쪽 노드 를 찾 습 니 다.오른쪽 노드 가 비어 있 지 않 을 때 반복 과정 1-2
4.오른쪽 노드 도 비어 있 을 때 s2 에 대응 하 는 식별 자가 1 일 때 s1 스 택 꼭대기 의 현재 노드 를 팝 업 하고 s2 의 식별 자 를 팝 업 합 니 다(즉,현재 노드 가 스 택 에서 나 오지 않 았 기 때문에 현재 스 택 의 맨 위 에 있 는 노드 는 현재 절 입 니 다).s1 이 현재 노드 를 팝 업 하고 방문 하지만 루트 에 값 을 부여 하지 않 습 니 다.이 루트 는 이때 null 입 니 다.
5.프로 세 스 3 에 들 어가 면 루트 는 peek 에 의 해 현재 노드 의 부모 노드(프로 세 스 4 에서 현재 노드 가 나 왔 기 때문에 s1 스 택 정상 은 현재 노드 의 부모 노드)의 오른쪽 부분 노드 입 니 다.
6.반복 과정 1-5

public void Postorder(TreeNode root)
  {
    Stack<TreeNode> s =new Stack<>(); 
    Stack<Integer> s2 =new Stack<>();
    Integer i=new Integer(1);
    while(root!=null||!s.isEmpty())
    {
      //        ，   
      while(root!=null)
      {
        s.push(root);
        s2.push(new Integer(0));
        root=root.left;
      }
      //s2     1，      s1                  。
      while(!s.empty()&&s2.peek().equals(i))
      {
        s2.pop();
        System.out.print(s.pop().val+" ");
      }
      if(!s.isEmpty())
      {
        s2.pop();
        s2.push(new Integer(1));
        root=s.peek();
        root=root.right;
      }
      
    }
  }

비 귀속 버 전 2
실현 방향:
뒷 순 서 를 옮 겨 다 닐 때 는 왼쪽 트 리 를 옮 겨 다 니 고 오른쪽 트 리 를 옮 겨 다 니 며 마지막 에 뿌리 노드 를 옮 겨 다 녀 야 합 니 다.그래서 재 귀적 이지 않 은 실현 에서 먼저 뿌리 노드 를 창고 에 넣 은 다음 에 왼쪽 트 리 를 창고 에 넣 고 왼쪽 트 리 가 비어 있 을 때 까지 창고 에 들 어 가 는 것 을 멈 춰 야 합 니 다.이 때 스 택 지붕 은 방문 해 야 할 요소 이기 때문에 방문 p 를 직접 꺼 냅 니 다.방문 이 끝 난 후에 방문 한 노드 p 가 스 택 꼭대기 노드 의 왼쪽 하위 트 리 인지 판단 해 야 합 니 다.그렇다면 스 택 꼭대기 노드 의 오른쪽 하위 트 리 를 방문 해 야 하기 때문에 스 택 꼭대기 노드 의 오른쪽 하위 트 리 를 추출 하여 p 에 할당 해 야 합 니 다.그렇지 않 으 면 스 택 꼭대기 노드 의 오른쪽 하위 트 리 가 이미 방문 했다 는 것 을 설명 합 니 다.그러면 이 제 는 스 택 꼭대기 노드 를 방문 할 수 있 습 니 다.그래서 이 때 p 대 가 를 null 로 할당 합 니 다.판단 이 끝 난 조건 은 p 가 비어 있 지 않 거나 스 택 이 비어 있 지 않 습 니 다.만약 에 두 가지 조건 이 모두 만족 하지 않 으 면 모든 노드 가 방문 이 완료 되 었 음 을 나타 냅 니 다.
비 귀속 실현

public void postOrder(Node root) {
		
	Stack<Node> s = new Stack<Node>();
	Node p = root;
	while (p != null || !s.empty()) {
		while(p != null) {
			s.push(p);
			p = p.left;
		}
		p = s.pop();
		System.out.print(p.val+" ");
	//        ，  p         ，                       
	//            ，               ，        ，   p   NULL
	//    
		if (!s.empty() && p == s.peek().left) {
			p = s.peek().right;
		}
		else p = null;
	}
}
 

층 차 를 편력 하 다

대기 열 로 구현,절 차 는:
1.비어 있 지 않 은 결점 에 대해 서 는 먼저 이 결점 을 대열 에 넣 습 니 다.
2.팀 에서 결점 을 꺼 내 고 이 결점 의 좌우 결점 이 비어 있 지 않 으 면 각각 좌우 결점 을 대열 에 넣는다.
3.대기 열 이 비어 있 을 때 까지 상기 조작 을 반복 합 니 다.

public void LaywerTraversal(TreeNode root){
  if(root==null) return;
  LinkedList<TreeNode> list = new LinkedList<TreeNode>(); 
  list.add(root);
  TreeNode currentNode;
  while(!list.isEmpty()){
    currentNode=list.poll();
    System.out.println(currentNode.val);
    if(currentNode.left!=null){
      list.add(currentNode.left);
    }
    if(currentNode.right!=null){
      list.add(currentNode.right);
    }
  }
}

자바 이 진 트 리 에 관 한 네 가지(재 귀 와 비 재 귀)글 은 여기까지 소개 되 었 습 니 다.더 많은 자바 이 진 트 리 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 바 랍 니 다!