二叉树的性质

前言

学习笔记
在学了二叉树后的一些笔记，干货哦（其实我好久没写文了，之前写的文章多了些粉丝，于是我又继续写了起来，你们的点赞和关注都是对我的鼓舞，谢谢你们）。
参考文献：严蔚敏.吴伟民.数据结构(C语言结构)[M].北京：清华大学出版社，2011.

一、树

1.树的定义

树(Tree)是n(n>= 0)个结点的有限集。n为0时为空树，不为0时为非空树。
对于非空树：

• 有且仅有一个特定的称为根的结点。

• 当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。（递归过程）

2.树的基本术语

如图示：
1、 结点的度(Degree): 子树的个数，也就是，结点有几条边，度就是几；

2、 树的度：树的所有结点度中最大的；

3、 叶结点：度为0的结点，也为终端结点，除叶子结点外的点为非终端结点；

4、 父结点：有子树的结点，这个结点为子树的父结点；

5、 子结点:若A结点是B结点的父结点，B结点是A结点的子结点，也称孩子结点；

6、 兄弟结点：具有同一父结点的各结点，彼此是兄弟结点；

7、 路径：从结点n1到nk的路径，为一 个结点序列n1 , n2 ,… , nk , ni，是 ni+1的父结 点；

8、 路径长度：路径所包含边的个数为路径的长度；

9、 祖先结点：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点；

10、子孙结点：结点的子树上的结点都为这个结点的子孙结点；

11、结点的层次：规定根节点在1层，下一层就加1为2层；

12、树的深度（高度）：最多有多少层结点；

二、二叉树

1.二叉树的定义

树是n个结点的有限集。当n = 0时称为空树，n>0时为非空树。
对于非空树有：

• 有且仅有一个特定的称为根的结点
• 当n > 1时，其余结点可分为两个互不相交的有限集T1、T2（二叉树种结点的度最大为2，最小为0）
• 二叉树的子树有左右之分，其次序不能随意颠倒。

2.二叉树与树的区别

由树和二叉树的定义的区别：

• 二叉树：

1. 其余结点可分为两个互不相交的有限集T1、T2（二叉树种结点的度最大为2，最小为0）
2. 二叉树的子树有左右之分，其次序不能随意颠倒。

• 树：
  其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm

可以看出区别：二叉树的左右子树有次序，树的不讲究，并且二叉树的度最大为2

2.1二叉树的五种基本形态

n个结点可构成二叉树的基本形态数：(卡特兰公式)

2.1二叉树的基本性质

性质1:在二叉树的第i层上至多有2^(i-1)个结点 (i≥1)。
性质2: 深度为h的二叉树至多有2^h - 1个结点 (h≥1)。
性质3: 叶子结点数n0，度为2的结点数为n2，则: n0 = n2 + 1。
解析：
总结点数n = 度为1的结点数n1 + 度为2的结点数n2 + 度为0的结点数n0,即：
n = n1 + n2 + n0
总结点数 = 总的边数 + 1，即：
n = n1 + 2n2 + 1
连立式子：n0 = n2 + 1
性质4：具有n个结点的完全二叉树的深度为 floor(log2n) + 1。
解析：
根据性质2深度为k，则最多有2^k - 1个结点。
性质5: 对于一棵n个结点的完全二叉树，对任一个结点(编号为i)，有以下关系：

1. 如果i=1, 则结点i为根, 无父结点; 如果i>1, 则其父结点编号为 floor(i/2)。
2. 如果 2i > n, 则结点i无子节点, 即结点i为叶结点; 否则左孩子编号为2i。
3. 如果 2i+1 > n, 则结点i无右孩子, 否则右孩子编号为2i+1。

总结

加油呀，摘下那颗最璀璨的星星。最近烦心事好多，经常不开心，压力大，但是一切都会值得的！