一、树的遍历操作
树的遍历：从根节点出发，按照某种次序访问树中所有结点，使得每个结点被访问一次且仅被访问一次。
遍历的实质为将树结构（非线性结构）转换为线性结构。
树通常有前序（根）遍历、后序（根）遍历和层序（次）遍历三种方式。
前序遍历：
树的前序遍历操作定义为： 
若树为空，则空操作返回；
否则
（1）访问根结点；
（2）按照从左到右的顺序前序遍历根结点的每一棵子树
图中树的前序遍历序列为：A B D E H I F C G
树的后序遍历操作定义为：
若树为空，则空操作返回；
否则
⑴ 按照从左到右的顺序后序遍历根结点的每一棵子树；
⑵ 访问根结点。
图中树的后序遍历序列： D H I E F B G C A
树的层序遍历操作定义为：
从树的第一层（即根结点）开始，自上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
图中树的层序遍历序列： A B C D E F G H I
二、二叉树的遍历操作
前序（根）遍历：
若二叉树为空，则空操作返回；
否则：
①访问根结点；
②前序遍历根结点的左子树；
③前序遍历根结点的右子树。
图中二叉树的前序遍历序列：A B D G C E F
中序（根）遍历：
若二叉树为空，则空操作返回；
否则：
①中序遍历根结点的左子树；
②访问根结点；
③中序遍历根结点的右子树。
图中二叉树的中序遍历序列：D G B A E C F
后序（根）遍历：
若二叉树为空，则空操作返回；
否则：
①后序遍历根结点的左子树；
②后序遍历根结点的右子树；
③访问根结点。
图中二叉树的后序遍历序列：G D B E F C A
层序遍历：
二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。
图中二叉树的层序遍历序列：A B C D E F G
三、方法
已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：
1. 根据前序序列的第一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在前序序列中确定左右子树的前序序列；
4. 由左子树的前序序列和中序序列建立左子树；
5. 由右子树的前序序列和中序序列建立右子树。
- 还没有人评论，欢迎说说您的想法！
客服
