DataStructure_树的基本性质(m叉树和二叉树)

文章目录

• ​​基本性质​​
• ​​任意树的通用性质​​

• ​​树的定义​​

• ​​边(分支)​​
• ​​结点数和边数的关系​​

• ​​二叉树结点和边的关系​​
• ​​m叉树的结点数量最多为:​​

• ​​

• ​​结点分类​​

• ​​分支结点​​
• ​​叶子结点​​

• ​​二叉树​​

• ​​满二叉树​​

• ​​结点和双亲的序号关系​​
• ​​
• ​​
• ​​满二叉树前i层的结点总数为:​​
• ​​满二叉树的各行尾结点编号​​
• ​​满二叉树的总结点数​​

• ​​完全二叉树​​

• ​​完全二叉树的各行首结点编号​​

• ​​完全m叉树的各行首结点编号​​

• ​​完全二叉树的分支结点​​
• ​​
• ​​最后一个分支结点的孩子结点情况分析​​
• ​​完全二叉树的任意结点的孩子分析​​
• ​​度为1的结点​​
• ​​根据双亲结点求孩子结点​​

• ​​二叉树和有序2度树​​
• ​​完全二叉树的高度/最小高度问题​​
• ​​具有n个结点的m叉树的高度问题​​
• ​​其他类型的特殊二叉树​​

• ​​只有0度结点和2度结点的二叉树​​

• ​​一个关于奇偶性的公式​​

• ​​二叉树的存储​​

• ​​顺序存储​​
• ​​链式存储​​

基本性质

任意树的通用性质

树的定义

• 树的定义是一种递归定义

• 树是n个结点的有限集合(可空)
• 对于非空树而言,它的定义是:

• 结点集合中,有且只有一个特定的点被选做根结点
• 其余结点再次划分为若干个有限集
• 这些有限集各自被作为一棵树(称为根结点的子树:再次运用树的已有定义继续选定自己集合内的根节点,再划分下去(每一次划分都会产生一批第一级的子树)
• 直到所有集合为空集为止

边(分支)

• 每一棵子树需要有一条边来链接到它的上层的根节点

• 显然,除了初始的大树根节点没有上层结点需要链接,所有它不引起边的产生
• 或者理解为除了,初始根结点没有上级结点,其余所哟结点都有且仅有一条边指向它的上级

• 这样一来有如下结论:

结点数和边数的关系

• 设一棵树的结点数为n
• 那么他又n-1条边
• ​​edges(nodes)=nodes-1​​

• 建立树的时候自顶向下
• 分析点和边的关系的时候,字底向上!

二叉树结点和边的关系

• 我们为二叉树的结点分类:

m叉树的结点数量最多为:

结点分类

分支结点

• 有孩子结点的结点就是分支结点(度>0的结点)

叶子结点

• 没有孩子结点的节点就是叶子结点(度为0的结点)

二叉树

满二叉树

• 所有层的结点数都是满的(尽可能多的)
• 所有的叶子结点都在底层

结点和双亲的序号关系

• 任意非根结点(序号为c)和它的双亲结点序号y具有关系:

• 第1
• 第2
• 第3
• 
• 第i
• 由此可见,任何二叉树的第i
• 后面我们将看到,完全二叉树的第i首结点编号就是

• 事实上,由于二叉树每个节点的度的限制,只有完全二叉树的第i层结点才能够达到最大值
• 换句话说,如果某棵树的告诉你某棵树的第i层结点数量达到

• 那么这个棵树前i-1层是全满的!

• 第i层结点数量不超过第i-1层结点数量的2倍
• 因此,可以保证,高层满的树(或者在加一个就能够满的),其低层的每一层都是满的!

满二叉树前i层的结点总数为:

满二叉树的各行尾结点编号

• 其编号就是前i行结点总数值:

• 第i
• 

满二叉树的总结点数

• 设满二叉树高度为
  

完全二叉树

• 当高度为h,结点数为n的二叉树的n个结点和等高度的满二叉树的前n个结点完全对应时,该二叉树就是完全二叉树
• 可以把满二叉树视为特别的完全二叉树

完全二叉树的各行首结点编号

完全m叉树的各行首结点编号

完全二叉树的分支结点

• 设完全二叉树的高度为h
• 那么第h-1层可能出现叶子结点!
• 最后一个非叶子结点(分支结点取决于完全二叉树的最后一个叶子结点)

• 设最后一个结点的编号是n:

最后一个分支结点的孩子结点情况分析

• 如果完全二叉树的结点数n是个偶数,的仅有左孩子
• 否则既有左孩子还有右孩子

完全二叉树的任意结点的孩子分析

• 对于有n个结点的完全二叉树,当结点p:

度为1的结点

• 由于完全二叉树是满二叉树的去掉底层右侧的连续若干个叶子结点得到的
• 处理最后一个分支结点度可能为1(仅有左孩子),其余所有分支结点的度都为2
• 所有叶子结点度都为0
• 因此,完全二叉树的所有结点中,度为1的结点数不超过1(可能么有)

根据双亲结点求孩子结点

• 假设结点p具有孩子结点(非叶子结点)
• 

二叉树和有序2度树

• 二叉树是概念先行,它允许二叉树的结点数量为0
• 但是度的概念是一个统计概念,如果一颗树的度为2,那么说明它的所有结点的最大度是且只能是2

• 2度树至少有3个结点(两个孩子结点和一个作为双亲(根)结点)

• 不过从定义上看,任意一颗有序2度树都可以通过添加适当转换规则将现有形状处理成二叉树,反之则不能

• 有序2度树的​​序​​是在双亲结点有多个孩子的时候,才有意义(仅有一个孩子的时候不区分顺序)
• 而二叉树在仅有一个孩子的时候,也要区分它是左孩子还是有孩子(从存储结构上的左右孩子指针可以看出)

完全二叉树的高度/最小高度问题

• 设完全二叉树结点总数为n;高度设为h

• 对于满二叉树:

• 高度为h-1时有关系式:
• 高度为h时:
• 
• 
• 注意,一般的
  
  

• 抽查验证:

• 构建一棵3层以内的矮树,验证临界结点

具有n个结点的m叉树的高度问题

• 最小高度:当这个m叉树是​​完全m叉树​​的时候,构成的树具有最小高度
• 有了推导二叉树的经验,从特殊到一般,我们在来推导​​完全m叉树的高度​​
  
  

其他类型的特殊二叉树

只有0度结点和2度结点的二叉树

• 按照使树达到最高的方式排列,那么每层仅有两个结点,而且它们是兄弟结点
• 按照使树有最低高度的方式排列,那么每层拥有最多结点

• 即,最后一个结点是右孩子结点的完全二叉树(n为奇数时)

• 如果结点数n为偶数,那么不可能实现没有1度的结点

• 因为
• 

一个关于奇偶性的公式

• 经过上一目的推导,可以得到公式Parity
• 
  公式Parity比较有用,可以记住(或者它的推导过程)
• 
  

二叉树的存储

顺序存储

• 适合存储完全二叉树,这样效率高

链式存储

• 适合存储非完全二叉树
• 对于每个结点设置2个指针,每一条边将占用一个指针(上层结点的指针域)

• 叶子结点的指针域全为空(NULL)
• 度为1的结点指针域被占用了一个,另一个为NULL
• 度为2的结点所有指针域都别占用,没有空指针域

• 另外,由于每个结点中有两个指针域,因而结点数为n的树总共有2n个指针域

• 其中n-1接入了边(非空)
• 区域的n+1个指针域全部为空(2n-(n-1)=n+1)