根据先序遍历和中序遍历建立二叉树

冷不防 2021-10-23 16:58 303阅读 0赞

title: 根据先序遍历和中序遍历建立二叉树
    date: 2019-07-23 22:37:34
    tags: 数据结构

## 问题 ##

已知一棵二叉树的先序遍历以及中序遍历，重建二叉树。二叉树的每一个节点有三个属性，左子节点，右子节点，以及节点值。

## 思路 ##

先序遍历服从规则**“根左右”**，所以由此可知，对于一个先序遍历得到的数组，第一个元素一定是**根节点**；

中序遍历服从规则**”左根右“**，所以由此可知，对于一个中序遍历得到的数组，根节点左边的元素都属于根节点的**左子树**，而根节点右边的元素都属于根节点的**右子树**；

所以，我们可以先通过先序遍历的第一个元素确定根节点，然后通过中序遍历结合根节点，获得当前根节点的左右子树，再将子树看成一棵独立的树，继续使用先序遍历判断根节点，中序遍历判断子树的方式，最终建立起整棵树；

## 例子 ##

假设有一棵二叉树，先序遍历为**\{1,2,4,7,3,5,6,8\}**，中序遍历为**\{4,7,2,1,5,3,8,6\}**，则建树过程如下：

> 首先，通过先序遍历可知树的根节点为***1***，则在中序遍历中，1左边的元素***4，7，2***即为根的左子树的元素，而***1***右边的元素***5，3，8，6***即为根节点的右子树；
> 
> > 对于左子树***4，7，2***来说，在先序遍历中，这三个点的顺序为***2，4，7***，则***2***为根节点，而在中序遍历中，***4，7***均在***2***的左边，则***4，7***均为以***2***为根树的左子树，且没有右子树；
> > 
> > > 对于***4，7***这两个节点来说，先序遍历中，***4***节点在7节点之前，所以***4***为根节点，而***7***作为子树，在中序遍历中，***7***在***4***之后，所以***7***为右子树；
> 
> > 对于根节点***1***的右子树***5，3，8，6***来说，在先序遍历中，***3***在最前面，所以***3***为这棵子树的根节点，而在中序遍历中，***5***在***3***的左边，所以属于左子树，而***8，6***在***3***的右边，属于右子树；
> > 
> > > 对于根节点***3***的右子树***8，6***，在先序遍历中，***6***在***8***之前，所以，***6***又为根节点，而在中序遍历中，***8***在***6***的左边，所以***8***是***6***的左子节点；

至此，二叉树便重建完成；

## 代码 ##

#### 树的节点 ####

1 public class TreeNode {
    2     int val;        //当前节点的值
    3     TreeNode left;    //左子节点
    4     TreeNode right;    //右子节点
    5 
    6     TreeNode(int x) {
    7         val = x;
    8     }
    9 }

### ###

#### 建树方法 ####

1 /**
     2 * pre：线序遍历得到的数组
     3 * in：中序遍历得到的数组
     4 */
     5 public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
     6     if(pre.length == 0) {
     7         return null;
     8     }
     9 
    10     int root = pre[0];
    11     TreeNode node = new TreeNode(root);
    12 
    13     //寻找根节点在in中的索引
    14     int i = 0;
    15     for( ; i<in.length; ++i) {
    16         if(in[i] == root) {
    17             break;
    18         }
    19     }
    20 
    21     //建立左子树
    22     int[] leftIn = Arrays.copyOfRange(in, 0, i);
    23     int[] leftPre = Arrays.copyOfRange(pre, 1, i+1);
    24     node.left = reConstructBinaryTree(leftPre, leftIn);
    25 
    26     //建立右子树
    27     int[] rightIn = Arrays.copyOfRange(in, i+1, in.length);
    28     int[] rightPre = Arrays.copyOfRange(pre, i+1, pre.length);
    29     node.right = reConstructBinaryTree(rightPre, rightIn);
    30 
    31     return node;
    32 }

#### 建树代码（优化） ####

1 public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
     2     return getRootTreeNode(pre, 0, pre.length-1, in, 0, in.length-1);
     3 }
     4 
     5 /**
     6 * preL：当前子树在先序遍历的数组中的起始下标
     7 * preR：当前子树在先序遍历的数组中的结束下标
     8 * inL：当前子树在中序遍历的数组中的起始下标
     9 * inR：当前子树在中序遍历的数组中的起始下标
    10 */
    11 public TreeNode getRootTreeNode(int[] pre, int preL, 
    12                                 int preR, int[] in, int inL, int inR) {
    13     if(preL > preR) {
    14         return null;
    15     }
    16 
    17     TreeNode node = new TreeNode(pre[preL]);
    18 
    19     for(int i=inL; i<=inR; ++i) {
    20         if(in[i] == pre[preL]) {
    21 
    22             node.left = getRootTreeNode(pre, preL+1, preL+i-inL, in, inL, i-1);
    23             node.right = getRootTreeNode(pre, preL+i-inL+1, preR, in, i+1, inR);
    24             break;
    25         }
    26     }
    27 
    28     return node;
    29 }

转载于:https://www.cnblogs.com/tuyang1129/p/11235173.html