树和二叉树

一、树

1. 树的概念

树(Tree)是$n(n>=0)$个节点的有限集，在任意一颗非空树中：

(1) 有且仅有一个特定的称为根(Root)的节点，根节点是没有前驱节点的。

（2）当 $n>1$时，其余节点可以分为$m(m>0)$个互不相交的有限集，其中每一个集合本身又是一颗树，并且称为根的子树。

树和非树

树要满足以下几个条件

• 子树是不相交的
• 除了根节点以外，每个节点有且仅有一个父节点
• 一棵$N$个节点的树有$N-1$条边

比如下面的两棵树就是非树

再来看一下一些比较重要的概念，通过下面这棵树来举例子

• 节点的度：一个节点含有的所以子树称为该节点的度，如上图A和D节点的度都为3
• 叶子节点(终端节点)：度为0的节点成为叶子节点，比如上图的绿色的节点都是叶子节点(K、L、F、G、M、I、J)
• 非终端节点(分支节点)：度不为0的节点，比如上图的 E、B、C、D等都是分支节点
• 双亲节点(父节点)：若一个节点含有子节点，则这个节点成为其子节点的双亲(父节点)，比如上图中A是B的双亲，A就是B的父节点。
• 孩子节点(子节点)：一个节点含有的子树的根节点称为该节点的子节点，上图中B是A的孩子节点
• 兄弟节点：具有相同父节点的节点称为兄弟节点，比如上图中 B、C、D 就是兄弟节点
• 树的度：一个树中，最大节点的度称为树的度，上图树的度为3
• 节点的层次：从根节点开始，根为第1层，根节点的子节点为第2层，以此类推
• 树的高度或者深度：树中节点的最大层次，如上图树的高度为4
• 堂兄弟节点：双亲在同一层的节点互为堂兄弟，比如K和L、M互为堂兄弟，又比如B和C、D互为堂兄弟
• 节点的祖先：从根到该节点所经分支上所以节点，比如根节点A是所以节点的祖先，又比如K的祖先是E、B、A
• 子孙：以某节点为根的子树中仁义节点都称为该节点的子孙，如上如所有节点都是A节点的子孙
• 森林：由$m(m>0)$棵互不相交的树的集合称为森林

2. 树的表示

树结构相对于线性表来说就比较复杂，要存储表示起来就比较麻烦了，实际中由很多种表示方法,比如：双亲表示法、孩子表示法、孩子兄弟表示法等。其中最常用的就是孩子兄弟表示法。

typedef int DataType;
struct Node
{
    struct Node* firstChild1; // 第一个孩子结点
    struct Node* nextBrother; // 指向其下一个兄弟结点
    DataType _data; // 结点中的数据域
};

二、二叉树

1. 二叉树的概念

二叉树(Binary Tree)是另一种树形结构，它的特点是每个节点至多只有两棵子树(即二叉树中不存在度大于2的节点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。

下面几颗树都可以叫做二叉树

特殊的二叉树

1. 满二叉树：一个二叉树，如果每一层的节点数都都能达到最大值，则这个二叉树就是满二叉树，也就是说，如果一个二叉树的层数为$k$,且总节点个数是$2^{k-1}$,则它就是满二叉树。
2. 完全二叉树：完全二叉数是效率很高的数据结构，完全二叉树是由满二叉树而引出来的，对于深度为$k$的，由$n$个节点的二叉树，当且仅当其每一个节点都与深度为$k$的满二叉树中编号从$1$至$n$的节点一一对应时称为完全二叉树，需要注意的是满二叉树是一种特殊的完全二叉树。

2. 二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的**第i层上最多有$2^{(i-1)}$**个结点($i>=1$)
2. 若规定根节点的层数为1，则深度为$k$的二叉树至多有$2^k-1$个节点($k>=1$)
3. 任何一颗二叉树，如果度为0的叶子节点的个数为$n_0$,度为2的分支节点个数为$n_2$,则有$n_0=n_2+1$
4. 若规定根节点的层数为1，具有具有$n$个节点的满二叉树的深度为$lo{g}_2(n+1)$
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
   • 若$i>0$,$i$位置节点的双亲序号：$(i-1)/2$，$i=0$,$i$为根节点，无双亲节点
   • 若$2i+1<n$，左孩子序号：$2i+1$，$2i+1>=n$否则无左孩子
   • 若$2i+2<n$，右孩子序号：$2i+2$，$2i+2>=n$否则无右孩子

3. 二叉树的顺序存储

顺序存储就是使用数组来存储，一般顺序存储只适用于完全二叉树，因为如果不是完全二叉树会存在空间的浪费。而实际情况中，只有堆才会使用数组来存储。二叉树的顺序存储在物理上是一个数组，而在逻辑上才是一棵二叉树

4. 二叉树链式存储

设计不同的节点结构可构成不同形式的链式存储结构。由二叉树的定义可知，二叉树的节点由一个数据元素分别指向其左右子树的两个分支构成，则表示二叉树的链表中的结点至少包含3个域：数据域和左右指针域，左右指针分别指向左右孩子所在的链节点的存储地址。

// 二叉树
struct BinaryTreeNode
{
    struct BinTreeNode* pLeft; // 指向当前节点左孩子
    struct BinTreeNode* pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}

---