Java中二叉树的建立和各种遍历实例代码

PreOrder: GDAFEMHZ InOrder: ADEFGHMZ PostOrder: AEFDHZMG

java;">class Tree{	char val;	Tree left;	Tree right;	Tree(char val, Tree left, Tree right){		this.val = val;		this.left = left;		this.right = right;	}	Tree(){	}	Tree(char val){		this.val = val;		this.left = null;		this.right =null;	}}

public static Tree buildTree(char[] preOrder, char[] inOrder){	//preOrder是先序序列	//inOrder是中序序列	if(preOrder == null || preOrder.length == 0){		return null;	}	Tree root = new Tree(preOrder[0]);	//找到inOrder中的root的位置	int inOrderIndex = 0;	for (char i = 0; i < inOrder.length; i++){		if(inOrder[i] == root.val){			inOrderIndex = i;		}	}	//preOrder的左子树和右子树部分	char[] preOrderLeft = Arrays.copyOfRange(preOrder, 1, 1+inOrderIndex);	char[] preOrderRight = Arrays.copyOfRange(preOrder, 1+inOrderIndex, preOrder.length);	//inOrder的左子树和右子树部分	char[] inOrderLeft = Arrays.copyOfRange(inOrder, 0, inOrderIndex);	char[] inOrderRight = Arrays.copyOfRange(inOrder, inOrderIndex+1, inOrder.length);	//递归建立左子树和右子树	Tree leftChild = buildTree(preOrderLeft, inOrderLeft);	Tree rightChild = buildTree(preOrderRight, inOrderRight);	root.left = leftChild;	root.right = rightChild;	return root;}

public static void postOrderPrint(Tree root){    //后续遍历    //左右根    if(root.left != null){      postOrderPrint(root.left);    }    if(root.right != null){      postOrderPrint(root.right);    }    System.out.print(root.val + " ");  }

public static void layerOrderPrint(Tree root){    if(root == null){      return;    }    //层序遍历    Queue<Tree> qe = new LinkedList<Tree>();    qe.add(root);    while(!qe.isEmpty()){      Tree node = qe.poll();      System.out.print(node.val + " ");      if(node.left != null){        qe.add(node.left);      }      if(node.right != null){        qe.add(node.right);      }    }  }

public static void deepFirstPrint(Tree root){    //深度优先遍历等价于先序遍历    //所以可以直接使用先序遍历    if(root == null){      return;    }    System.out.print(root.val + " ");    if(root.left != null){      deepFirstPrint(root.left);    }    if(root.right != null){      deepFirstPrint(root.right);    }  }public static void deepFirstPrintNoneRec(Tree root){    //深度优先遍历的非递归形式    if(root == null){      return;    }    Stack<Tree> st = new Stack<Tree>();    st.add(root);    while(!st.isEmpty()){      Tree node = st.pop();      System.out.print(node.val + " ");      //栈是后进先出的      //先加右孩子后加左孩子      if(node.right != null){        st.add(node.right);      }      if(node.left != null){        st.add(node.left);      }    }  }

public static void main(String[] args) {    char[] preOrder = "GDAFEMHZ".toCharArray();    char[] inOrder = "ADEFGHMZ".toCharArray();    Tree root = Main.buildTree(preOrder, inOrder);//   Main.postOrderPrint(root); //后序遍历//   Main.layerOrderPrint(root); //层序遍历//   Main.deepFirstPrint(root); //深度优先遍历//   Main.deepFirstPrintNoneRec(root); //深度优先遍历的非递归版本  }