学习数据结构--第四章:树与二叉树(二叉树的概念、性质、特殊二叉树)

学习数据结构--第四章:树与二叉树(二叉树的概念、性质、特殊二叉树)

Scroll Down

第四章:树与二叉树(二叉树的逻辑结构)

1.二叉树

二叉树是树结构的一种,故二叉树也是逻辑结构。

二叉树:二叉树是n(n≥0)个结点的有限集合。

  • 1)n=0时,二叉树为空;
  • 2)n>0时,由根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树也分别是一棵二叉树。

五种基本形态

三个结点的二叉树有多少种??

2.二叉树VS度为2的有序树

  • 1)二叉树可以为空,而度为2的有序树至少有三个结点

度为2的有序树,则说明必须有一个结点的子节点为两个

  • 2)二叉树的孩子结点始终有左右之分,而度为2有序树的孩子结点次序是相对的

在度为2的有序树中,如果有一个结点只有一个孩子结点,则是不分左右的。

3.特殊二叉树

3.1满二叉树

满二叉树:一棵高度为h,且含有2^h-1个结点的二叉树为满二叉树。

上篇文章中讲树的时候我们知道:高度为h的m叉树至多有(m^h-1)/(m-1) 个结点。这里我们把m换成2,即可。

编号规则:从上到下、从左到右;

观察上述编号可以发现下面结论:

对于编号为 i 的结点,若存在,其双亲的编号为(i/2取整),左孩子为2i,右孩子为2i+1

3.2完全二叉树

完全二叉树:设一个高度为h、有n个结点的二叉树,当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一 一对应时,称为完全二叉树。

我们可以发现,如果一个二叉树是完全二叉树,则此二叉树除了最后一层结点数不满外,其余层结点数都是满的。

完全二叉树的性质

  • 若 i <= n/2 取整数,则结点 i 为分支结点,否则为叶子结点。

i 是结点编号,n 是结点的总数。

  • 叶子结点只可能在层次最大的两层上出现。对于最大层次的叶子结点,都依次排在最左边的位置上。
  • 度为1的结点若存在,则可能只有一个,且是编号最大的分支结点,并且孩子结点一定是左结点。

因为完全二叉树的编号是按照从上到下,从左到右编号的,而且除了最后一层结点数不满外,其余层结点数都是满的,所以度为1的结点可能存在也可能不存在,如果存在只可能在最后一个结点的双亲结点才能出现度为1的结点。

所有的性质都紧紧依赖完全二叉树的编号是从上到下,从左到右的。

3.3二叉排序树

二叉排序树:一棵二叉树,若树非空则具有如下性质:

  • 对任意结点若存在左子树或右子树,则其左子树上所有结点的关键字均小于该结点。
  • 右子树上所有结点的关键字均大于该结点。

可以发现二叉排序树的左子树和右子树都是一棵二叉排序树。

3.4平衡二叉树

平衡二叉树:树上任意结点左子树右子树的深度差不超过1

f复习:高度和深度的定义,某节点的深度是指从根节点到该节点的最长简单路径边的条数,而高度是指从该节点到叶子节点的最长简单路径边的条数。记住:深度是从根结点到该结点的边数的,而高度是从叶子节点往上数到该结点的边数。
注意:这里边的条数是规定根节点的深度和叶子节点的高度是0;
所以树的深度和高度是相等的,而对其他节点来说深度和高度不一定相等。

上图就不是一个平衡二叉树:

上图根结点的左子树深度为3,右子树深度为2,3-2=1,没问题,但是A结点的左子树深度为2,而A结点的右子树深度为0,2-0=2>1,不对。

4.二叉树的性质

4.1n0=n2+1

  • 非空二叉树上的叶子结点数等于度为2的结点数加1,即n0=n2+1.

如图上述二叉树:

  • 首先我们知道二叉树的结点数等于各种度数二叉树结点的和,即n=n0+n1+n2
  • 另外n=0*n0+1*n1+2*n2+1,这个计算方法是按照子节点个数计算的,0*n0代表叶子节点的子节点数(叶子结点子节点数为0,故乘以0),1*n1代表子节点数为1的结点的个数,2*n2代表子节点数为2的结点的个数,最后加上1,代表根结点。

将上面的两个关于n的式子相减即可得到:n0=n2+1

4.2性质2

非空二叉树上第 k 层上至多有 2^(k-1)个结点(k≥1)

4.3性质3

高度为h的二叉树至多有2^h -1个结点(h>=1) [满二叉树结点的总数]

4.4性质4

4)对完全二叉树按从上到下、从左到右的顺序依次编号1,2,....n,则有以下关系:

  • 当 i>1 时,结点的双亲结点标号为 i/2 取整数, 即当 i 为偶数时,其双亲结点的编号为 i/2 ,他是双亲结点的左孩子;当为奇数时,其双亲结点的编号为(i-1)/2, 他是双亲结点的右孩子。
  • 当 2i <= n 时,结点 i 的左孩子编号为 2i ,否则无左孩子
  • 当 2i+1<=n 时,结点 i 的右孩子编号为 2i+1,否则无右孩子

4.5性质5

则第h层,2^(h-1) =< i < 2^h ,对该式子两端取对数,则h-1 =< log2i< h,我们对log2i取下界,则得到h-1,再加1则得到系欸但所在的层次:[log2i] +1

4.6性质6

由性质3:高度为h的二叉树至多有2^h -1个结点(h>=1)。令2^h -1=n,则可以推出 h = log2(n+1),至于这里为啥要取上界,是因为这个性质3,是按照满二叉树情况,但是完全二叉树的最后一层结点数不一定能达到最多,但也要算一层。

关于数据结构的知识,持续更新中,欢迎关注公众号理木客