# 先序+中序 ->建树

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 条评论

## 相关文章

991

1032

3007

622

### Android NDK and OpenCV development with Android Studio

Android NDK and OpenCV development with Android Studio

752

### 使用crs_profile管理RAC资源配置文件

profile通常指配置文件，crs_profile望文生义可知，就是管理集群的配置文件。在Oraclele RAC中，所有的CRS资源存放在OCR磁盘...

653

### Emulex LightPulse FC9002L光纤卡安装日志

# tar xvf solaris-6.01c-1a.tar x EmlxApps300a8-Solaris.tar, 6850560 bytes, 13380...

1072

### 常见的几种Flume日志收集场景实战

这里主要介绍几种常见的日志的source来源，包括监控文件型，监控文件内容增量，TCP和HTTP。 Spool类型 　　用于监控指定目录内数据变更，若有新文...

2775

### CodeForces 709C Letters Cyclic Shift

C. Letters Cyclic Shift time limit per test 1 second memory limit per test ...

2866

3003