一、三种遍历的定义二叉树遍历是一个递归过程先处理根节点再分别处理左、右子树。根据“根节点”被访问的位置不同有三种深度优先遍历3前序遍历根 → 左子树 → 右子树先访问根节点再前序遍历左子树最后前序遍历右子树。中序遍历左子树 → 根 → 右子树先中序遍历左子树再访问根节点最后中序遍历右子树。后序遍历左子树 → 右子树 → 根先后序遍历左子树再后序遍历右子树最后访问根节点。递归和非递归实现得到的序列完全一致非递归只是用显式栈模拟递归过程。二、示例例如二叉树text1 / \ 2 3 / \ \ 4 5 6前序序列1,2,4,5,3,61,2,4,5,3,6中序序列4,2,5,1,3,64,2,5,1,3,6后序序列4,5,2,6,3,14,5,2,6,3,1三、遍历序列的重要性质1. 子树在序列中是连续区间以任意节点为根的子树在三种序列中都对应一个连续区间。并且在这个区间内前序序列中根节点在区间最前面中序序列中根节点在左子树区间和右子树区间之间后序序列中根节点在区间最后面。这是“由遍历序列还原二叉树”的核心基础。2. 根节点的定位前序序列的第一个元素一定是整棵树的根节点。后序序列的最后一个元素一定是整棵树的根节点。中序序列中根节点左边的元素全部来自左子树右边的元素全部来自右子树。因此只要有了“中序 前序”或“中序 后序”就能确定根并区分左右子树。3. 二叉树还原的唯一性前序序列 中序序列能唯一确定一棵二叉树。后序序列 中序序列能唯一确定一棵二叉树。前序序列 后序序列一般不能唯一确定二叉树。反例树 A 是根节点 1 只有左孩子 2树 B 是根节点 1 只有右孩子 2。树 A 和树 B 的前序序列都是 1,21,2后序序列都是 2,12,1但它们是两棵不同的二叉树。所以已知前序和中序可以唯一推出后序已知后序和中序可以唯一推出前序但只知道前序和后序无法唯一确定中序遍历序列。若额外限制为严格二叉树每个内部节点都有左右两个孩子则前序 后序可以唯一还原二叉树1。4. 与二叉搜索树的关系对于二叉搜索树BST中序遍历序列一定按关键字递增排列因为中序序列隐含已知所以仅凭前序序列或后序序列也能唯一重建这棵 BST。5. 表达式树中的应用表达式树的前序、中序、后序遍历分别对应前序序列前缀表达式中序序列中缀表达式后序序列后缀表达式也就是逆波兰式用栈求值非常方便。6. 其他性质三种深度优先遍历中叶子节点的从左到右相对顺序相同。三种遍历的时间复杂度都是 O(n)O(n)其中 nn 是节点数递归栈空间为 O(h)O(h)hh 是树高最坏情况下为 O(n)O(n)。四、由序列还原二叉树的方法前序 中序还原前序序列的第一个元素是根节点在中序序列中找到根节点根左侧长度为 LL前序序列中根节点之后的前 LL 个元素属于左子树剩余元素属于右子树递归处理左右子树即可12。后序 中序还原后序序列的最后一个元素是根节点在中序序列中找到根节点根左侧长度为 LL后序序列中前 LL 个元素属于左子树接下来若干元素属于右子树最后是根节点递归处理左右子树即可12。
一、三种遍历的定义二叉树遍历是一个递归过程先处理根节点再分别处理左、右子树。根据“根节点”被访问的位置不同有三种深度优先遍历3前序遍历根 → 左子树 → 右子树先访问根节点再前序遍历左子树最后前序遍历右子树。中序遍历左子树 → 根 → 右子树先中序遍历左子树再访问根节点最后中序遍历右子树。后序遍历左子树 → 右子树 → 根先后序遍历左子树再后序遍历右子树最后访问根节点。递归和非递归实现得到的序列完全一致非递归只是用显式栈模拟递归过程。二、示例例如二叉树text1 / \ 2 3 / \ \ 4 5 6前序序列1,2,4,5,3,61,2,4,5,3,6中序序列4,2,5,1,3,64,2,5,1,3,6后序序列4,5,2,6,3,14,5,2,6,3,1三、遍历序列的重要性质1. 子树在序列中是连续区间以任意节点为根的子树在三种序列中都对应一个连续区间。并且在这个区间内前序序列中根节点在区间最前面中序序列中根节点在左子树区间和右子树区间之间后序序列中根节点在区间最后面。这是“由遍历序列还原二叉树”的核心基础。2. 根节点的定位前序序列的第一个元素一定是整棵树的根节点。后序序列的最后一个元素一定是整棵树的根节点。中序序列中根节点左边的元素全部来自左子树右边的元素全部来自右子树。因此只要有了“中序 前序”或“中序 后序”就能确定根并区分左右子树。3. 二叉树还原的唯一性前序序列 中序序列能唯一确定一棵二叉树。后序序列 中序序列能唯一确定一棵二叉树。前序序列 后序序列一般不能唯一确定二叉树。反例树 A 是根节点 1 只有左孩子 2树 B 是根节点 1 只有右孩子 2。树 A 和树 B 的前序序列都是 1,21,2后序序列都是 2,12,1但它们是两棵不同的二叉树。所以已知前序和中序可以唯一推出后序已知后序和中序可以唯一推出前序但只知道前序和后序无法唯一确定中序遍历序列。若额外限制为严格二叉树每个内部节点都有左右两个孩子则前序 后序可以唯一还原二叉树1。4. 与二叉搜索树的关系对于二叉搜索树BST中序遍历序列一定按关键字递增排列因为中序序列隐含已知所以仅凭前序序列或后序序列也能唯一重建这棵 BST。5. 表达式树中的应用表达式树的前序、中序、后序遍历分别对应前序序列前缀表达式中序序列中缀表达式后序序列后缀表达式也就是逆波兰式用栈求值非常方便。6. 其他性质三种深度优先遍历中叶子节点的从左到右相对顺序相同。三种遍历的时间复杂度都是 O(n)O(n)其中 nn 是节点数递归栈空间为 O(h)O(h)hh 是树高最坏情况下为 O(n)O(n)。四、由序列还原二叉树的方法前序 中序还原前序序列的第一个元素是根节点在中序序列中找到根节点根左侧长度为 LL前序序列中根节点之后的前 LL 个元素属于左子树剩余元素属于右子树递归处理左右子树即可12。后序 中序还原后序序列的最后一个元素是根节点在中序序列中找到根节点根左侧长度为 LL后序序列中前 LL 个元素属于左子树接下来若干元素属于右子树最后是根节点递归处理左右子树即可12。
)
