# 先序+中序 ->建树

PreOrder: GDAFEMHZ InOrder: ADEFGHMZ PostOrder: AEFDHZMG

```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;
}
//层序遍历
while(!qe.isEmpty()){
Tree node  = qe.poll();
System.out.print(node.val + " ");
if(node.left != null){
}
if(node.right != null){
}
}
}```

## 深度优先和广度优先

```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>();
while(!st.isEmpty()){
Tree node = st.pop();
System.out.print(node.val + " ");
//栈是后进先出的
//先加右孩子后加左孩子
if(node.right != null){
}
if(node.left != null){
}
}
}```

main函数：

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

89 篇文章41 人订阅

0 条评论

2674

2695

2136

353

542

3836

671

1243

1203

733