이 진 트 리 의 세 가지 역 주 행 비 재 귀적 실현

1. 이 진 트 리 앞 순 서 를 옮 겨 다 니 는 비 재 귀적 실현     * 사고방식 을 실현 하려 면 먼저 루트 노드 를 방문 한 다음 에 왼쪽 트 리 와 오른쪽 트 리 를 방문 해 야 한다. 이것 은 분명히 귀속 정의 이지 만 여 기 는 창고 로 이 루어 진 것 이다
     * 먼저 스 택 꼭대기 에서 노드 를 꺼 낸 다음 에 이 노드 를 방문 해 야 합 니 다. 만약 에 이 노드 가 비어 있 지 않 으 면 이 노드 를 방문 하 는 동시에 이 노드 의 오른쪽 트 리 를 먼저 스 택 에 들 어간 다음 에
     * 왼쪽 나무 가 창고 에 들어가다.순환 이 끝 나 는 조건 은 창고 에 노드 가 없 는 것 이다.즉!s.empty()

public void preOrder(Node root) {
	Stack s = new Stack();
	s.push(root);
	Node p = null;
	while (!s.empty()) {
		p = s.pop();
		if (p != null) {
			System.out.print(p.val+" ");
			s.push(p.right);
			s.push(p.left);
		}
	}
}

2. 이 진 트 리 의 중간 순서 가 반복 되 지 않 고 이 루어 집 니 다.
     * 사고방식 을 실현 하려 면 중 서 를 옮 겨 다 니 는 것 은 먼저 왼쪽 나 무 를 옮 겨 다 니 고 그 다음 에 노드 와 마지막 에 오른쪽 나 무 를 옮 겨 다 니 는 것 이다.그래서 먼저 노드 를 창고 에 넣 고 왼쪽 나 무 를 창고 에 계속 넣 어야 합 니 다.     * 왼쪽 나무 가 비어 있 을 때 까지 창고 에 들 어 가 는 것 을 멈 추 십시오.창고 꼭대기 노드 는 우리 가 방문 해 야 할 노드 입 니 다. 창고 꼭대기 노드 p 를 취하 고 방문 합 니 다.그리고 노드 를 바 꾸 면 오른쪽 나무 가 있 을 수 있 기 때문에     * 노드 p 를 방문 한 후에 p 의 오른쪽 하위 트 리 가 비어 있 는 지 판단 해 야 합 니 다. 비어 있 으 면 다음 에 방문 할 노드 가 스 택 꼭대기 에 있 기 때문에 p 대 가 를 null 로 합 니 다.하면, 만약, 만약...     * p 를 오른쪽 하위 트 리 의 값 으로 할당 합 니 다.순환 이 끝 나 는 조건 은 p 가 비어 있 지 않 거나 스 택 이 비어 있 지 않 습 니 다.

public void inOrder(Node root) {
      Stack s = new Stack();
      Node p = root;
      do {
          while (p != null) {
             s.push(p);
             p = p.left;
          }
          p = s.pop();
          System.out.print(p.val+" ");
          if (p.right != null) {
              p = p.right;
          }
          else p = null;
     } while(p != null || !s.empty());
}

3. 이 진 트 리 의 뒷 순 서 는 반복 되 지 않 고 이 루어 집 니 다.
     * 사고방식 을 실현 하려 면 뒷 순 서 를 옮 겨 다 닐 때 먼저 왼쪽 나 무 를 옮 겨 다 닌 다음 에 오른쪽 나 무 를 옮 겨 다 니 고 마지막 에 뿌리 노드 를 옮 겨 다 녀 야 한다.그래서 비 재 귀적 실현 에서 먼저 뿌리 노드 를 창고 에 넣 어야 한다.     * 그리고 왼쪽 나무 가 비어 있 을 때 까지 왼쪽 나 무 를 창고 에 넣 으 세 요. 이때 창고 에 들 어 가 는 것 을 멈 추 세 요.이 때 스 택 지붕 은 방문 해 야 할 요소 이기 때문에 방문 p 를 직접 꺼 냅 니 다.방문 이 끝 난 후에 도 피 방 을 판단 해 야 한다.     * 노드 p 가 스 택 꼭대기 노드 의 왼쪽 하위 트 리 인지 물 었 습 니 다. 그렇다면 스 택 꼭대기 노드 의 오른쪽 하위 트 리 를 방문 해 야 하기 때문에 스 택 꼭대기 노드 의 오른쪽 하위 트 리 를 추출 하여 p 에 할당 합 니 다.하면, 만약, 만약...     * 이 는 스 택 꼭대기 노드 의 오른쪽 하위 트 리 가 이미 방문 되 었 음 을 나타 낸다. 그러면 이 제 는 스 택 꼭대기 노드 에 접근 할 수 있 기 때문에 p 대 가 를 null 로 할 수 있다.끝 을 판단 하 는 조건 은 p 가 비어 있 거나 스 택 이 아 닙 니 다.     * 비어 있 지 않 습 니 다. 만약 에 두 가지 조건 이 만족 하지 않 으 면 모든 노드 가 이미 방문 이 완료 되 었 음 을 나타 냅 니 다.

       public void postOrder(Node root) {
		
		Stack s = new Stack();
		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;
		}
	}

마지막 으로 노드 의 자바 류 코드 를 첨부 합 니 다.

//     
class Node {
	public int val; //   
	public Node left; //   
	public Node right; //   
	public Node() {}
	public Node(int val, Node left, Node right) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}