二叉树的一些性质

ゝ一纸荒年。 2022-06-11 07:37 239阅读 0赞

在介绍二叉树性质之前，先谈一下二叉树的度与深度区别：

**二叉树的度**：子树就是二叉树的分支。度就是分支的数目。没有分叉的二叉树节点的度就是0度。如果一个节点只有一个分叉就是1度。两个分叉就是2度的子树。

**二叉树的深度**：二叉树的根结点所在的层数为1，根结点的孩子结点所在的层数为2，以此下去。深度是指所有结点中最深的结点所在的层数。

注意一个问题：区别二叉树的深度与高度。

对于树的基本概念上理解，对于才接触[数据结构][Link 1]的人来说，树的高度和深度是一个容易混淆的知识点，现解释如下：

**1.高度**

对于高度的理解，我们不管他数据结构什么什么知识，就拿楼房来说，假如一个人提问：楼房的高度有好高？我们会下意识的从底层开始往上数，假如楼有6层，则我们会说，这个楼有6层楼那么高，则提问者就会大概知道楼有多高了。所以高度就是以从下往上对比，这是我们的习惯。而在树中，树的高度也是从下往上数，如图所示

![Center][]

K节点在树的底层，是一个叶子节点，则一般定义为K的高度在最低为1，以此类推，O的高度也是为1，P的节点也是为1。M节点是叶子节点O的父节点，从下往上数，M节点高度为2。那么G节点的高度是多少呢？从G-L的高度为2，从G-M-O节点高度为3，到底G节点高度为多少呢，正确答案是3，请看定义：

高度的定义为：从结点x向下到某个叶结点**最长简单路径**中**边的条数**

**注意：**对于是否是边的条数这个不清楚，待我后来查证，这个主要是由于其初值是1还是0来确定的，一般都是以1开始

**2.深度**

理解了高度，则深度的理解就很容易了，深度是从根节点往下，列如上图中：B的深度为2。

**3.总结**

对于整棵树来说，最深的叶结点的深度就是树的深度；树根的高度就是树的高度。这样树的高度和深度是相等的。

对于树中**相同深度**的每个结点来说，它们的**高度不一定相同**，这取决于每个结点下面的叶结点的深度。

**二叉树的一些性质：**

1.二叉树第i层至多有2^（i-1）个结点（i>=1）。

2.深度为k的二叉树上，至多含2^k-1个结点（k>=1）   
3.n0 = n2 + 1（度）   
4.满二叉树：深度为k且含有2^k-1个结点的树。   
5.完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。   
（树中所含n个结点和满二叉树中编号为1至n的结点一一对应）。   
6.具有n个结点的完全二叉树的深度为\[log2n\] + 1。   
7.二叉树的链式存储表示：二叉链表、三叉链表（增加双亲指针域）、双亲链表、 线索链表。   
8.二叉树的遍历：前、中、后。   
9二叉树的遍历 [算法][Link 1] ：递归、非递归（栈：现在经过不访问，一会访问的结点入栈，栈空结束遍历）。   
10.二叉树递归遍历引申的算法：求树的深度、结点个数、复制二叉树等。   
11.二叉树相关算法一定要考虑空树的情况。   
13.表达式和二叉树的关系： \[第一操作数\]\[二元运算符\]\[第二操作数\] = \[左节点\]\[双亲结点\]\[右结点\]，   
（先中后）缀对应（前中后）遍历。   
14.线索二叉树：二叉链表中增加两个标志域，让左右两个指针增加功能：有子结点则指向子结点，没有则指向前驱和后继（某种遍历方式）。   
15.树和二叉树的相互转换，树的叶子结点：左子树空。 [ 树、森林与二叉树的转换][Link 2]    
16.遍历二叉树的所有叶子节点。   
17.树的存储结构

18.[哈夫曼树][Link 3]

19.平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

补充说明一下：哈夫曼树

1.哈夫曼树：给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。  
2.哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。  
3.构造  
    1.权值最小的两个结点，构造成一棵二叉树，该二叉树的权值为两个结点之和，并把该二叉树看成结点。  
    2.重复1步骤。  
4.哈夫曼编码：字符出现次数等同于权值，是变长编码。  
5.可以使用哈夫曼编码进行压缩文件。  
6.哈夫曼树只是一棵最优二叉树,不一定是完全二叉树,也不一定是平衡二叉树。  
7.哈夫曼树每个结点要么没有子节点，要么有两个子节点，可考虑哈夫曼树的构成。

转载：http://blog.csdn.net/songzige/article/details/51298123

[Link 1]: http://lib.csdn.net/base/datastructure
[Center]: /images/20220611/437445062cd74f328d2ecf040405f44a.png
[Link 2]: http://blog.csdn.net/songzige/article/details/50505178
[Link 3]: http://blog.csdn.net/songzige/article/details/52155330