白话篇：利用二叉树先序/中序/后序确定二叉树求法分析_2.假二叉树 bt 的后序遍历序列为 ao;a1,..,an-1,设计一个算法按 ax-1、

作者：AllinToyou | 2024-04-09 10:53:44

踩

2.假二叉树 bt 的后序遍历序列为 ao;a1,..,an-1,设计一个算法按 ax-1、

前篇：

二叉树的遍历是指按照一定次序访问二叉树中所有的节点，并且每个节点仅仅能够访问一次。这也是二叉树最基本的运算。

常用的3钟递归遍历方式：

1.先序遍历，过程：

（1）访问根节点

（2）访问左子树

（3）访问右子树

2.中序遍历，过程：

（1）访问左子树

（2）访问根节点

（3）访问右子树

3.后序遍历：
（1）访问左子树

（2）访问右子树

（3）访问根节点

为了能够更好的理解到这三种遍历方式，我们画图来模拟一下：

对于一颗二叉树：

1.先序遍历结果：ABDGCEF

2.中序遍历结果：DGBAECF

3.后序遍历结果：GDBEFCA

首先我们先证明一下可行性：对于任何n（n>0）个不同节点的二叉树，都可以由它的中序序列和先序序列唯一确定：

采用数学归纳法证明：

当n=0时，二叉树为空，结论正确。

假设：节点数小于n的任何二叉树，都可以由它的中序和先序序列唯一确定。

若一棵树具有n个节点，其先序序列为：a0，a1，a2……an-1，中序序列：b0，b1，b2……b

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/392240