二叉树图解-已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍因序列是多少，请详解（图解）

满二叉树和完全二叉树的区别图解,如下所示:

完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

对于满二叉树,除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树。而完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

满二叉树定义:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。

完全二叉树定义:若设二叉树的深度为h,除第 h 层外,其它各层 (1～h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

1 定义

2 前序遍历(根左右)

前序遍历

通俗的说就是从二叉树的根结点出发,当第一次到达结点时就输出结点数据,按照先向左在向右的方向访问。

图3.13所示二叉树访问如下:

则3.13所示二叉树的前序遍历输出为:

ABDHIEJCFG

3 中序遍历(左根右)

中序遍历

就是从二叉树的根结点出发,当第二次到达结点时就输出结点数据,按照先向左在向右的方向访问。

图3.13所示二叉树中序访问如下:

则3.13所示二叉树的中序遍历输出为:

HDIBJEAFCG

4 后序遍历(左右根)

后序遍历

就是从二叉树的根结点出发,当第三次到达结点时就输出结点数据,按照先向左在向右的方向访问。

图3.13所示二叉树后序访问如下:

则图3.13所示二叉树的后序遍历输出为:

HIDJEBFGCA

1 定义

2 图解实例

选取一个节点为参照根节点,会发现所有的左侧子节点小于等于参照点,右侧大于等于参照点。

比如根节点9, 9所有的

左侧子节点(5、2、7、1、3)

都小于等于9.

比如根节点13,13所有的

左侧子节点(11、10、12)

都大于等于13.

3 查找

查找节点 10:根节点9开始,10>9 右侧,10<13 左侧,10<11 左侧,找到10.

下图是二叉查找树的极端情况

二叉查找树就是为了提高查询效率,而当前这种和我们写了一堆for循环是一样的。

为了应对这种情况:又出现了平衡二叉树--红黑树。后面会提到。

1 定义

红黑树的特性

:

(1)每个节点或者是黑色,或者是红色。

(2)根节点是黑色。

(3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]

(4)如果一个节点是红色的,则它的子节点必须是黑色的。也就是不能有连在一起的红色节点,但是可以有连在一起的黑色节点

(5)满足所有的二叉查找树的性质

红黑树示意图如下:

2 变换规则

左旋又分为两种情况,

(1)我们操作的结点E是整棵树的根节点,那么左旋实现为下面步骤

(2)我们操作的结点E有父结点,那么左旋实现为下面步骤

3)右旋

右旋同样分为两种情况,与左旋情况类似,故实际操作参考左旋。

3 插入

注意

:上述描述中一个很重要的点是,在插入元素时,是将元素作为叶子结点插入的,插入到原红黑树的外部结点。

插入结点染色情况

插入结点后调整和平衡过程

1.变颜色的情况: 当前结点的父亲是红色,且它的祖父结点的另一个结点(也就是叔叔结点)也是红色:

2.左旋:当前父结点是红色,叔叔结点是黑色的时候,且当前的结点时右子树,则进行左旋。左旋过程不需要进行颜色变换。

3.右旋:当前父结点时红色,叔叔结点是黑色的时候,且当前的结点是左子树,则进行右旋。右旋过程中需要进行颜色变换,具体右旋过程如下。

实例讲解

参考视频:

前序遍因序列是cedba。

二又树的遍历有3种:前序、中序和后序。

①前序首先遍历访问根结点,然后按左右顺序遍历子结点。

②中序遍历首先访问左子树,然后访问根结点,最后遍历右子树。

③后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点。本题根据后序和中序遍历的结果可以得出二叉树的结构,然后再对其进行前序遍历。

二叉树

在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点。

深度为k的二叉树至多有2^k-1个结点;对任何一棵二叉树T,如果其终端结点数为n_0,度为2的结点数为n_2,则n_0=n_2+1。

一棵深度为k,且有2^k-1个节点称之为满二叉树;深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树。