이 진 트 리 의 비 재 귀적 스 트 리밍 알고리즘 (두 가지 서로 다른 사고) + 층 차 를 옮 겨 다 니 며

선언:
   지난 글 에서 우 리 는 이 진 트 리 의 순환 에 대해 토론 했다.이 진 트 리 에 있어 서 가장 쉬 운 것 은 재 귀적 인 것 이다.공부 가 반복 되 지 않 을 때 는 말 하지 않 을 수 없다.두서 가 하나 도 없다(처음에는 이 진 트 리 의 재 귀적 이지 않 고 옮 겨 다 니 는 것 이 정말 어 려 웠 습 니 다. 생각 이 정리 되 지 않 았 습 니 다. 먼저 놓 치고 싶 었 습 니 다. 뒷부분 의 내용 을 보 니 이 진 트 리 찾기, 우선 대기 열 에 있 는 이 진 트 리 문제 등 이 나무 와 많은 관 계 를 가 진 것 으로 나 타 났 습 니 다. 그 를 해결 하 는 방법 과 재 귀적 이지 않 고 옮 겨 다 니 는 것 은 큰 관계 가 없 지만 나무 에 대한 자신의 이 해 를 설명 할 수 있 습 니 다.심각 한 지 여부. 나 무 를 깊이 이해 할 수 없 기 때문에 나무의 다른 방면 의 내용 을 진행 할 수 없습니다. 예 를 들 어 결점 의 insert, delete, 스 트 레 칭 나무, B 나무 등 이 있 습 니 다. 특히 이 진 더미 의 순서 적 성질 은 최소 원 을 찾 는 것 이 간단 하지만 그 나머지 요 소 를 다시 놓 아야 할 점 을 찾 으 려 면 더욱 깊 은 이해 가 필요 합 니 다. 이 방면 은 너무 많아 서 반드시 필요 합 니 다.첫 번 째 딱딱 한 뼈 부터 뜯 어 내야 한다.
   오늘 은 두 가지 서로 다른 사고방식 의 코드 를 놓 고 제 가 공부 하 는 과정 에서 이해 하기 어 려 운 부분 을 표시 할 것 입 니 다.

      <pre name="code" class="java"><span style="white-space:pre">	</span>/**
	 *       ，     ，         。
	 *         ，              
	 *                     
	 * @param p
	 */
	//          1
	public static void inorder1(node p){	
		Stack<node> stack = new Stack<node>();
		node n = p;
		while(n != null || stack.size() > 0){
			while(n != null){//    ，          
				stack.push(n);
				n = n.getLeft();
			}
			if(stack != null){
				n = stack.pop();
				visitKey(n);
				n = n.getRight();
			}
		}
	}
	
	public static void inorder2(node p) {
		Stack<node> stack = new Stack<node>();
		while (p != null) {
			while (p != null) {
				if (p.getRight() != null)
					stack.push(p.getRight());//         
				stack.push(p);//       
				p = p.getLeft();
			}
			p = stack.pop();
			while (!stack.empty() && p.getRight() == null) {
				visitKey(p);
				p = stack.pop();
			}
			visitKey(p);
			if (!stack.empty())
				p = stack.pop();
			else
				p = null;
		}
	}

 
  
 
 
 
	/**          1*/
	protected static void prefixOrder2(node p) {
		Stack<node> stack = new Stack<node>();
		node node = p;
		while (node != null || stack.size() > 0) {
			while (node != null) {//         ，      。
					      //       pop     。
				visitKey(node);
				stack.push(node);
				node = node.getLeft();
			}
			if (stack.size() > 0) {//
				node = stack.pop();
				node = node.getRight();
			}
		}
	}
  
<span style="white-space:pre">	</span>/**          (   ) */
	protected static void iterativePreorder(node p) {
		Stack<node> stack = new Stack<node>();
		if (p != null) {
			stack.push(p);
			while (!stack.empty()) {
				p = stack.pop();
				visitKey(p);
				//    p.getLeft()  ，getRight()  
				//   while       pop
				// visit    left  ，   。           。
				if (p.getRight() != null)
					stack.push(p.getRight());
				if (p.getLeft() != null)    
					stack.push(p.getLeft());
			}
		}
	}
  
 
 
（如果想测试，就把代码复制到上一篇文章里面就可以）
 
 
以上是非递归实现前序遍历和中序遍历。根据代码可以看出中序遍历2和先序遍历2的思路大致相同，不同点在于访问结点的位置。一开始不理解的时候总觉得出栈和访问时一样的，但实际上是访问的时候才是输出，输出的方法为visitKey()。其实当理解了这两种方法以后感觉并不难，重点就是真正的把那张图看懂，二叉树的访问顺序究竟是怎样的。（后序遍历的代码之后放上~）非递归遍历过程的核心在于遍历过程中经过的结点的路线是一样的，只是访问各个结点的时机不同！
 
 
好了，非递归实现前序遍历和中序遍历说完，再谈最后一种遍历方式：层序遍历。层序遍历是使二维结构的二叉树按照一维结构输出，即二维结构的线性化。难点：当访问完某结点n的左孩子后，如何再访问n的右孩子，以及如何记录n的右孩子和n结点本身。
 
 
解决办法：
 
 
需要一个存储结构保存暂时不被访问的结点。这时候我们选择的是堆栈或者队列。前面我们讲的都是用堆栈实现，现在我们说一下如何用队列实现：遍历从根结点开始，首先将根结点入队，然后开始执行循环：结点出队、访问该结点、其左右儿子入队。代码如下：
 
 
（输出结果是按从上往下，从右到左的顺序输出，即为层序遍历）
 
 
 
 
<span style="white-space:pre">	</span>/**
	 *     
	 * @param p
	 */
	public static void levelOrder(node root){
		if(root == null) return;//         
		Queue<node> q = new LinkedList<node>();//    
		q.add(root);
		while(!q.isEmpty()){
			node n = q.poll();
			visitKey(n);//       ，     
			if(n.getLeft() != null){//            ，    
				q.add(n.getLeft());
			}
			if(n.getRight() != null){
				q.add(n.getRight());
			}
		}
	}