二叉树的前（先）序中序和后序遍历 以及如何通过两个序列确定唯一二叉树 |
您所在的位置：网站首页 › 前序序列怎么排的 › 二叉树的前（先）序中序和后序遍历 以及如何通过两个序列确定唯一二叉树 |
二叉树的前（先）序中序和后序遍历 以及如何通过两个序列确定唯一二叉树
|
文章目录
三种遍历前（先）序遍历。中序遍历。后序遍历。
举几个例子两个序列确定一个二叉树
最近做了一套卷子，考了二叉树的遍历。有点生疏，回顾一下，如何通过两种遍历序列确定一颗二叉树。 三种遍历先中后表示对根节点访问的先后顺序，对子树都是先左后右。 前（先）序遍历。遍历顺序是 根节点 ->左子树（节点）->右子树（节点） 可以理解成 1 存在根节点，访问根节点2 存在左子树或节点的话，访问该节点，若存在左子树，继续执行2，直到左路走到底3 左子树访问到底，该节点只剩下右子树（节点），访问该节点。（此时可以理解成该节点左子树和右子树为空）当一个左子树遍历完。回溯到上一节点。遍历右子树。直到全部遍历完。 中序遍历。遍历顺序是 左子树（节点） ->根节点->右子树（节点） 可以理解成当一个节点的左子树遍历完，才遍历这个节点，故需要找到最左的叶子节点开始遍历。若不存在则先遍历根节点，然后在右子树中寻找最左的叶子节点 1 寻找最左边最下的叶子节点，访问该节点2 遍历完左边子树（节点），访问该节点对应的父节点。3 访问父节点后，遍历右子树（也可以当做一个新的树处理） 后序遍历。遍历顺序是 左子树（节点） ->右子树（节点）->根节点 可以理解成当一个节点的左子树和右子树都遍历完，才遍历这个节点，同样需要找到最左的叶子节点开始遍历。 1 寻找最左下的叶子节点，访问该节点2 遍历完左边子树（节点），访问该节点对应的兄弟节点。3 访问根节点4 回溯到上一层（3中的根节点作为向上一层的左或右节点）继续执行123，直到遍历到根节点 举几个例子
给出一个中序序列，再给一个前序或后续序列，则可以确定一个个唯一的二叉树。 这里需要注意的是，两个序列中必须有一个中序序列才可以。 前序和后续组合无法确定唯一二叉树 根据三种遍历方式的特性，可以知道。前序遍历第一个出现的则是它的根节点。后续最后一个是根节点。而将这个节点放在中序序列中，左边则是根节点的左子树，右边是右子树。 我们用最后一个例子的前序和中序来试着确定一个唯一的二叉树。 首先A是根节点，由于A在中序中位于最后，则这个二叉树没有右子树。则B是A的左节点B在中序中，左边只有C，故B的左子树只有C由前序知道，D是B的右节点，同时可以把它当做是一个新的子树来分析。把ABC从中序序列中拿掉，同时D的右边只有F，则D的右子树只有F这时，只剩下E和G没有位置了。无疑，这两个位于D的左子树。这时他俩的前序序列是EG，则E是D的左节点，中序序列是EG，则G是E的右节点。完成 |
前序序列：ABCDEF 中序序列：CBDAEF 后续序列：CDBFEA 
前序序列：ABDEFGCHI 中序序列：DBFEGACIH 后续序列：DFGEBIHCA
前序序列：ABCDEGF 中序序列：CBEGDFA 后续遍历：CGEFDBA【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |