二叉搜索树的后序遍历序列_二叉排序树和二叉搜索树区别

二叉树的前序遍历，中序遍历和后序遍历分别有什么作用？　　先序遍历：在第一次遍历到节点时就执行操作，一般只是想遍历执行操作（或输出结果）可选用先序遍历；　　中序遍历：对于二分搜索树，中序遍历的操作顺序（或输出结果顺序）是符合从小到大（或从大到小）顺序的，故要遍历输出排序好的结果需要使用中序遍历　　后序遍历：后续遍历的特点是执行操作时，肯定已经遍历过该节点的左右子节点，故适用于要进行破坏性操作的情况，比如删除所有节点　　什么是二叉树　　简单理解为对于一个节点来说，最多拥有一个上级节点，同时最多具备左右两个下级节点的数据结构。　　由于很多排序算法都是基于二叉树实现的，多叉树也是二叉树延伸过去的，所以二叉树的建树和遍历就显得非常重要。　　二叉树建树　　一般情况是给你一个串，要求让你以前序，中序，后序的方式建树。那么此时我们就需要首先了解三个概念：前序遍历中序遍历后序遍历　　我们来看看一棵二叉树的结构： 0 / \ 1 2 / \ / \ 3 4 5 60就是整个二叉树的根节点，1就是0这个节点的左子树，2就是0这个节点的右子树。有了这个知识，我们就可以理解前中后序遍历这个位置属性就是指的根在哪个位置，前序遍历就是根在前，所以就是根左子树右子树的遍历方式；中序遍历就是根在中间，所以就是左子树根右子树的遍历方式；后序遍历就是根在最后，所以就是左子树右子树根的遍历方式。　　遍历的方式有三种，对应的建树方式有已知中序和前序建树，已知中序和后序建树，已知前序和后序建树三种。如果我们仅仅是想构建一棵二叉平衡树，可以简单使用某一种序列建树。用伪代码表示这三种遍历方式就是前序遍历的方式建树　　中序遍历的方式建树　　后序遍历的方式建树　　前序建树　　我们现在以序列 1, 2, 3, 4, 5, 6, 7, 8, 9 为例，如果是前序建树方式，那么二叉树的结构应该为：

　　实现也比较简单　　执行结果如下：　　中序建树　　以 1，2，3，4，5，6，7序列为例，如果是中序建树的方式，那么二叉树的结构应该为

　　代码如下：　　相对前序建树以扩展的方式建立二叉树，中序建树由于无法很好的控制索引，所以这里使用了一个队列来存储整个序列，同时需要算出以当前的节点数，算出建立一棵二叉平衡树，最小的深度为多少。然后按照之前给出的伪代码，按照左根右的方式赋值和递归调用即可。运行的结果如下：　　后序建树　　有了中序遍历，其实后序遍历就非常简单了，以序列1,2,3,4,5,6,7为例，建树应该为

　　代码如下：　　通过分析三个建树方法的代码你可以发现，其实本质上，根赋值代码，与调用左右子树建树函数的摆放的位置不同，就早就了这三种不同的算法。三种建树方法对应的三种遍历方法本质区别也就是打印值语句与调用左右子树打印值函数的摆放位置不同。如果举一反三的话，我们可以很容易的得出二叉树前中后序遍历的代码。那么，请你自己先尝试一下。　　二叉树的遍历　　根据建树的经验，知道，我们只需要写出一种遍历方法，那么其他两种遍历方式都有了。区别只不过是换换打印语句的位置。对于前序遍历，写法如下：　　那么我们来做一个实验，首先根据序列1,2,3,4,5,6,7利用前序遍历构建出一棵平衡二叉树，然后打印出其前序中序后序遍历的顺序。完整的代码如下：　　最终的结果如下：

　　是否和你的一致呢？　　二叉树的非递归及层次遍历　　1.前序遍历　　遍历顺序：根节点→左孩子→右孩子；　　具体算法思想：将二叉树的根结点赋值给遍历的指针，由该指针进行遍历；若当前节点非空，则访问该节点并将该节点压栈（将该节点的地址压栈），继而遍历其左子树；循环执行，直到当前节点为空时，取栈顶素并访问其右子树，再重复如上操作，直至遍历节点的指针为空且栈也为空；　　具体遍历过程如图：

　　算法代码实现如下：　　2.中序遍历　　遍历顺序：左孩子→根节点→右孩子；　　具体算法思想：将二叉树的根结点赋值给遍历的指针，由该指针进行遍历；若当前节点非空，则将该节点压栈并访问其左子树，循环执行，直至当前节点为空时，取栈顶素访问并弹栈，然后访问其右子树，再重复如上操作，直至遍历节点的指针为空在且栈也为空。（中序遍历和前序遍历的不同在于：前序遍历是入栈的同时访问结点，而中序遍历是出栈的同时访问结点）；　　具体遍历过程如图：

　　算法代码实现如下：　　3.后序遍历　　遍历顺序：左孩子→右孩子→根节点；　　具体算法思想：将二叉树的根结点赋值给遍历的指针，由该指针进行遍历；若当前节点非空，则将该节点压栈并访问其左子树，循环执行，直至当前节点为空时，取栈顶素，判断其右子树是否为空且是否已遍历，如果非空且为遍历则访问其右子树，再将其压栈遍历其左子树；如果右子树为空或已遍历则访问该结点并弹栈，同时设置标记指针记录遍历过的点（用于判断右子树是否已遍历），再将遍历指针置空（下次遍历直接取栈顶素），直至遍历节点的指针为空且栈也为空。　　算法代码实现如下：　　4.层次遍历　　具体算法思想：将根节点入队，访问队头素，并将其左右孩子入队，循环直至队列为空结束。　　算法代码实现如下：　　5.具体实现　　后序遍历二叉树，指的是从根结点出发，按照以下步骤访问树中的每个结点：优先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；如果当前结点没有左子树，则进入它的右子树，以同样的步骤遍历右子树中的结点；直到当前结点的左子树和右子树都遍历完后，才访问该结点。　　以下图所示的二叉树为例：

图 1 二叉树　　后序遍历这棵二叉树的过程是：　　最终，后序遍历图 1 中的二叉树，访问各个结点的顺序是：　　4 5 2 6 7 3 1 　　递归后序遍历二叉树　　后序遍历二叉树，最常用的实现方式就是递归。　　对于顺序表存储的二叉树，递归实现后序遍历的 C 语言程序为：　　对于链表存储的二叉树，递归实现后序遍历的 C 语言程序为：　　以上给出的是后序遍历二叉树的 C 语言关键代码，猛击这里完整源码。　　非递归后序遍历二叉树　　递归的底层实现过程是借助栈存储结构完成的，因此我们可以手动模拟一个栈结构，实现二叉树的后序遍历。　　后序遍历是在遍历完当前结点的左右孩子之后才访问该结点，所以需要在当前结点进栈时为其配备一个标志位。当遍历该结点的左孩子时，设置当前结点的标志位为 0；当要遍历该结点的右孩子时，设置当前结点的标志位为 1，进栈。　　这样当遍历完该结点的左右子树并将其弹栈时，查看该结点标志位的值：如果是 0，表示该结点的右孩子还没有遍历；如果是 1，说明该结点的左右孩子都遍历完成，可以访问此结点。　　对于顺序表存储的二叉树，非递归实现后序遍历的 C 语言程序为：　　运行结果为：　　按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:1 2 3 4 5 6 7 #4 5 2 6 7 3 1 　　对于链表存储的二叉树，非递归实现后序遍历的 C 语言程序为：　　运行结果：　　1 2 4 0 0 5 0 0 3 6 0 0 7 0 04 5 2 6 7 3 1以上内容是解学武：数据结构与算法教程（C语言版）中的一篇文章，六年创作，三次迭代，千般打磨，成就了今天这套精品数据结构教程。教程适合有 C 语言基础的小伙伴，想系统学习数据结构的同学，欢迎加 q（）或 V（x）联系我。

二叉搜索树的后序遍历序列_二叉排序树和二叉搜索树区别

相关推荐