遍历二叉树

比眉伴天荒 2022-06-08 00:48 301阅读 0赞

## 遍历二叉树 ##

二叉树是由3个基本单元组成的：根结点、左子树和右子树。  
若限定先左后右的顺序，则遍历二叉树只有三种情况分别称为先（根）序遍历、中（根）序遍历和后（根）序遍历。

*  先序遍历二叉树的操作定义为：  
    
    
     *  若二叉树为空，则空操作；否则  
        
        
         *  访问根结点；
         *  先序遍历左子树；
         *  先序遍历右子树。
 *  中序遍历二叉树的操作定义为：  
    
    
     *  若二叉树为空，则空操作；否则  
        
        
         *  中序遍历左子树；
         *  访问根结点；
         *  中序遍历右子树。
 *  后序遍历二叉树的操作定义为：  
    
    
     *  若二叉树为空，则空操作；否则  
        
        
         *  后序遍历左子树；
         *  后序遍历右子树；
         *  访问根结点。

举例说明：  
如图所示的二叉树表示下述表达式

a+b\*(c-d)-e/f

![这里写图片描述][SouthEast]

二叉树的先序序列为：-+a\*b-cd/ef  
二叉树的中序序列为：a+b\*c-d-e/f  
二叉树的后序序列为：abcd-\*+ef/-

![这里写图片描述][SouthEast 1]

--------------------

### 知道两个序列求另一个序列 ###

1、已知先序和中序，求后序

我们来举个简单的例子，先序序列为：ABDECF，中序序列为：DBEAFC。

算法思想：先序遍历树的规则为中左右，可以看到先序遍历序列的第一个元素必为树的根节点，比如上例中的A就为根节点。再看中序遍历为：左中右，再根据根节点A，可知左子树包含元素为：DBE，右子树包含元素：FC。然后递归的 进行左子树的求解（左子树的先序为：BDE，中序为：DBE），递归的进行右子树的求解（即右子树的先序为：CF，中序为：FC）。如此递归到没有左右子树为止。

2.已知中序和后序，求先序

同样举上面的例子，中序序列为：DBEAFC，后序序列为：DEBFCA。  
算法思想：同样采用分段递归的思想解决。由后序序列知道最后一个节点一定是根节点，此处为A，在根据中序序列知道左子树和右子树，之后在分段递归。

3、已知先序和后序，求中序

同样举上面的例子，先序序列为：ABDECF，后序序列为：DEBFCA。  
**此种情况是不可唯一确定解的**，只能确定根节点，而对于左右子树的组成不确定。

[SouthEast]: /images/20220608/5a9ff665348c4b4699f689734fca5a77.png
[SouthEast 1]: /images/20220608/a798bcd6180c43b4a23dd977d7cafec3.png