二叉树深度遍历非递归实现

二叉树遍历使用递归的思想就非常简单。比如前序遍历，先节点，再左子树，最后右子树。其他遍历同理，但是非递归就不一样了，要能正确的实现遍历，就肯定要对一些基本的数据结构有认识，还要去学会辨别不同的数据结构(我觉得最难的地方就在这里)。

又是一个大难题，哎。。。慢慢来吧。。

非递归实现中序遍历：

	public void inOrderVisitWithStack() {
		ObjectStack os = new ObjectStack();//栈我自己设置的是默认最大长度是10个长度。
		BinaryCharTree tempnode = this;//准备第一个节点
		while(!os.isEmpty() || tempnode != null) {//这里就直接排除了二叉树为空的情况
			if(tempnode!=null) {
				os.enstack(tempnode);
				tempnode = tempnode.LChild;
			}//左孩子存在的情况
			
			else {
				tempnode = (BinaryCharTree) os.destack();
				System.out.print(" "+tempnode.value+" ");
//				os.enstack(tempnode.RChild);
				tempnode = tempnode.RChild;
			}//左孩子不存在的情况
		}
	}

非递归实现先序遍历：

public void preOrderVisitWithStack() {//前序遍历只需要将中序遍历的思路稍微改一下即可，基本没有差别。
		ObjectStack os = new ObjectStack();
		BinaryCharTree tempnode = this;
		while(!os.isEmpty()||tempnode!=null) {
			if(tempnode!=null) {
				System.out.print(" "+tempnode.value+" ");
				os.enstack(tempnode);
				tempnode = tempnode.LChild;
			}
			else {
				tempnode = (BinaryCharTree) os.destack();
				tempnode = tempnode.RChild;
			}
		}
	}

非递归实现后序遍历：

public void postOrderVisitWithStack() {
		ObjectStack os = new ObjectStack();
		BinaryCharTree tempnode = this;
		ObjectStack finalStack = new ObjectStack();
		while(!os.isEmpty()||tempnode!=null) {
			if(tempnode!=null) {
				finalStack.enstack(new Character(tempnode.value));
				os.enstack(tempnode);
				tempnode = tempnode.RChild;
			}
			else {
				tempnode = (BinaryCharTree) os.destack();
				tempnode = tempnode.LChild;
			}
		}
		while(!finalStack.isEmpty()) {
			System.out.print(" "+finalStack.destack()+" ");
		}
	}
	

思路上还有些陌生，还得不断地熟练才行。

以下就是这篇博客写的东西的集合了，包中的内容是我自己的，不是java自带的，好像在前几篇的博客里有写。

package tree;

import queue.*;
import stack.*;
import java.util.Arrays;

public class BinaryCharTree {
	
	char value;
	BinaryCharTree LChild;
	BinaryCharTree RChild;
	
	public BinaryCharTree(char name) {
		value = name;
		LChild = null;
		RChild = null;
	}//创建二叉树节点
	public static BinaryCharTree ManualBinaryTree() {
		//构建只有节点的树:
		BinaryCharTree tempTreeA = new BinaryCharTree('a');
		
		//所有节点如下:
		BinaryCharTree tempTreeB = new BinaryCharTree('b');
		BinaryCharTree tempTreeC = new BinaryCharTree('c');
		BinaryCharTree tempTreeD = new BinaryCharTree('d');
		BinaryCharTree tempTreeE = new BinaryCharTree('e');
		BinaryCharTree tempTreeF = new BinaryCharTree('f');
		BinaryCharTree tempTreeG = new BinaryCharTree('g');

		tempTreeA.LChild = tempTreeB;
		tempTreeA.RChild = tempTreeC;
		tempTreeB.RChild = tempTreeD;
		tempTreeC.LChild = tempTreeE;
		tempTreeD.LChild = tempTreeF;
		tempTreeD.RChild = tempTreeG;
		
		return tempTreeA;
	}
	
	public void preOrderVisit() {//前序遍历
		System.out.print(value);
		if(LChild!=null) {
			LChild.preOrderVisit();
		}
		if(RChild!=null) {
			RChild.preOrderVisit();
		}
	}
	
	public void inOrderVisit() {//中序遍历
		if(LChild!=null) {
			LChild.inOrderVisit();
		}
		System.out.print(value);
		if(RChild!=null) {
			RChild.inOrderVisit();
		}
	}
	
	public void postOrderVisit() {//后序遍历
		if(LChild!=null) {
			LChild.postOrderVisit();
		}
		if(RChild!=null) {
			RChild.postOrderVisit();
		}
		System.out.print(value);
	}
	
	public int getDepth() {
		if(this==null) {
			return 0;
		}
		if(LChild==null&&RChild==null) {
			return 1;
		}
		int lnum=0,rnum=0;
		if(LChild!=null) {
			lnum = LChild.getDepth();
		}
		if(RChild!=null) {
			rnum = RChild.getDepth();
		}
		if(lnum>=rnum) return lnum+1;
		else return rnum+1;
	}
	
	public int getNumNodes() {
		if(this==null) {
			return 0;
		}
		if(RChild==null&&LChild==null) {
			return 1;
		}
		int lnum = 0,rnum = 0;
		if(RChild!=null) {
			rnum = RChild.getNumNodes();
		}
		if(LChild!=null) {
			lnum = LChild.getNumNodes();//注意节点可能为空的情况，
		}
		return rnum+lnum+1;
	} 
	
	//定义两个数组用来存储数值和下标值
	char[] CharArr;
	int[] IntArr;
	public void toDataArrays() {
		int dlength = getNumNodes();//我原来肯定是getNumNodes出问题了。
		CharArr= new char[dlength];
		IntArr = new int[dlength];
		int i = 0;//标记以上两个数组的下标
		CircleObjectQueue CharQueue = new CircleObjectQueue();//使用队列能够实现非递归先序，目前只知道这一个，以后还要继续了解
		CircleObjectQueue IntQueue = new CircleObjectQueue();
		
		Integer tempnum = Integer.valueOf(0);//不是会自动装箱吗，是不是不需要这一步？？？
		CharQueue.enqueue(this);
		IntQueue.enqueue(tempnum);
		
		BinaryCharTree tempbt = (BinaryCharTree)CharQueue.dequeue();//因为默认从object数组出来的都是object类型，所以这里要进行数据转换。
		CharArr[i] = tempbt.value;
		int index = ((Integer)IntQueue.dequeue()).intValue();//此时已经被取走了
		IntArr[i] = index;//前面作为一个整体的Integer包装类，使用intValue得到数据大小。
		i++;
		
		while(tempbt!=null) {
			
			if(tempbt.LChild!=null) {
				CharQueue.enqueue(tempbt.LChild);
				tempnum = Integer.valueOf(2*index+1);
				IntQueue.enqueue(tempnum);
			}
			if(tempbt.RChild!=null) {
				CharQueue.enqueue(tempbt.RChild);
				tempnum = Integer.valueOf(2*index+2);
				IntQueue.enqueue(tempnum);
			}
			tempbt =(BinaryCharTree)CharQueue.dequeue();//特别要注意的一点，循环队列在这时如果为空，会返回null(详见队列代码)。
			if(tempbt==null) break;//在这里设置条件，防止为空。
			CharArr[i] = tempbt.value;
			index = ((Integer)IntQueue.dequeue()).intValue();
			IntArr[i] = index;
			i++;
		}
	}
	//在编写过程中，遭遇了许多的困难，首先是数据类型的转换。其次是空指针的问题，主要表现在队列取走一个元素后再去元素就会发生OutOfIndex的问题。
	//再者，还有调用成员变量的问题，不要重复定义变量。这些都是我在打代码时所亲身经历的问题。
	
	
	
	
	//创建二叉树这里直接写构造方法。(当然返回一个二叉树的普通方法也行)
	public BinaryCharTree(char[] InputCharArr,int[] InputIntArr) {//InputIntArr是每一个节点的位置。
		int allnums = InputCharArr.length;
		BinaryCharTree []AllNodes = new BinaryCharTree[allnums];
		for(int i = 0;i