基本概念
- 根节点
- 内部节点
- 叶节点
- 相交
- 孩子
- 双亲
- 兄弟
- 度：树各个节点度的最大值
- 深度或高度
- 森林
树的存储结构
双亲表示法
以一组连续空间存储树的节点，在每个节点中，附设一个指示器指示其双亲节点到链表中的位置。
#define MAX_TREE_SIZE 100
typedef int TElemType;
typedef struct
{
TElemType data; /* 节点数据 */
int parent; /* 双亲位置 */
} PTNode;
typedef struct
{
PTNode nodes[MAX_TREE_SIZE]; /* 节点数组 */
int r, n; /* 根的位置和节点数 */
} PTree;
孩子表示法
每个节点有多个指针域，其中每个指针指向一棵子树的根节点，我们把这种方法叫做多重链表表示法。
方案一
指针域的个数等于树的度。
缺点：对于树中各节点的度相差很大时，比较浪费空间，因为很多节点的指针域是空的。
方案二
每个节点指针域的个数等于该节点的度，专门取一个位置来存储节点指针域的个数。
缺点：各个节点的链表是不相同的结构，加上需要维护节点度的数值，在运算上会带来时间上的损耗。
孩子表示法概念
把每个节点的孩子节点排列起来，以单链表作存储结构，则n个节点有n个孩子链表，如果是叶子节点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。
#define MAX_TREE_SIZE 100
typedef struct CTNode /* 孩子节点 */
{
int child; /* 节点下标 */
struct CTNode *next;
} *ChildPtr;
typedef struct /* 表头结构 */
{
TElemType data;/* 节点数据 */
ChildPtr firstChild;
} CTBox;
typedef struct /* 树结构 */
{
CTBox nodes[MAX_TREE_SIZE]; /* 节点数组 */
int r, n; /* 根的位置和节点数 */
} CTree;
上述结构对于查找某个节点的孩子、兄弟只需要查找这个节点的孩子单链表即可。对于遍历整棵树只需要对节点的数组循环即可。
对于查找某个节点的双亲是比较麻烦的，需要遍历整棵树。那么在CTBox结构中加入一个parent字段，这就是改进版的孩子表示法，我们把这种方法叫做双亲孩子表示法。
孩子兄弟表示法
任意一棵树，它的节点第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该节点的第一个孩子和此节点的右兄弟。
/* 树的孩子兄弟表示法结构定义*/
typedef struct CSNode
{
TElemType data;
struct CSNode *firstChild, *rightSib;
} CSNode, *CSTree;
孩子兄弟表示法的最大好处就是通过变形，它把一颗复杂的树变成了一棵二叉树。
二叉树
定义
二叉树(Binary Tree)是n(n>=0)个节点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根节点或两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
特点
- 每个节点最多两棵子树，不存在度大于2的节点。
- 左子树和右子树是有序的。
- 即使树中某节点只有一棵子树，也要区分它是左子树还是右子树。
基本形态
- 空二叉树
- 只有一个根节点
- 根节点只有左子树
- 根节点只有右子树
- 根节点既有左子树又有右子树
特殊二叉树
斜树
所有的节点都只有左子树的二叉树叫做左斜树。所有节点都只有右子树的二叉树叫做右斜树。这两者统称为斜树。
满二叉树
在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
完全二叉树
对一棵具有n个节点的二叉树按层序编号，如果编号为i(1<=i<=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
二叉树性质
结论
- 在二叉树的第i层上至多有(2^i-1)个节点(i>=1)
- 深度为k的二叉树至多有(2^k)-1个节点(k>=1)
- 对任何一棵二叉树T，如果其终端(叶子)节点数为n0，度为2的节点数为n2，则n0 = n2 + 1
- 具有n个节点的完全二叉树的深度为[logn] + 1([x]表示不大于x的最大整数，所有log都是以2为底数，下文都是如此)
- 如果对一棵有n个节点的完全二叉树(其深度为[logn]+1)的节点按层序编号(从第1层到第[logn]+1层，每层从左到右)，对任一节点i(1<=i<=n)有：
1> 如果i=1，则节点i是二叉树的根，无双亲；如果i>1，则其双亲是节点[i/2]
2> 如果2i>n，则节点i无左孩子(节点i为叶子节点)；否则其左孩子是节点2i
3> 如果2i+1>n，则节点i无有孩子；否则其右孩子是节点2i+1
推理
二叉树第1层有2^0个节点
二叉树第2层有2^1个节点
根据数学归纳法可知二叉树第i层有(2^i-1)个节点
深度为1的二叉树至多有2^0个节点
深度为2的二叉树至多有2^0 + 2^1个节点
根据等差数列求和可知深度为k的二叉树至多有(2^k)-1个节点(k>=1)
树T节点总数为：n = n0(叶子) + n1(度为1) + n2(度为2)
树T分支线总数为：n - 1 = n1 + 2n2
由上述可以推导出：n0 = n2 + 1
根据满二叉树定义可知，深度为k的满二叉树的节点数为n = (2^k)-1，则可推出完全二叉树的节点数n <= (2^k)-1。由于完全二叉树
的叶子节点只会出现在最下面的两层，那么n>(2k-1)-1。又由于n是整数，则(2k-1) =< n < (2^k)。等式两边取对数可知，k-1 =< logn < k，因此深度k为logn + 1且k为整数。
二叉树存储结构
二叉树顺序存储结构
二叉树顺序存储结构就是用一维数组存储二叉树中的节点，并且节点的存储位置即是数组的下标要能体现节点之间的逻辑关系。顺序存储结构一般只用于完全二叉树。
二叉树链式存储结构
二叉树每个节点最多有两个孩子，每个节点由一个数据域和两个指针域组成，这样的链表我们称为二叉链表。结构定义如下所示：
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
| 左孩子指针 | 数据域 | 右孩子指针 |
|---|---|---|
| lchild | data | rchild |
二叉树遍历
二叉树遍历(traversing binary tree)：指从根节点出发，按照某种次序依次访问二叉树中所有节点，使得每个节点有且仅被访问一次。
二叉树遍历方法
前序遍历
若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。
中序遍历
若二叉树为空，则空操作返回，否则从根节点开始，中序遍历根节点的左子树，然后才是访问根节点，最后中序遍历右子树。
后序遍历
若树为空，则空操作返回，否则从左到右先叶子后节点的方式遍历访问左右子树，最后是访问根节点。
层序遍历
若树为空，则空操作返回，否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，从左到右的顺序对节点逐个访问。
二叉树遍历性质
- 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
- 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
二叉树建立
将二叉树中每个节点的空指针引出一个虚节点，其值为一特定值(如：'#')，我们称这种处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树可以做到一个遍历序列确定一棵二叉树。
/* 输入前序遍历的扩展二叉树方式来创建二叉树 */
void CreateBiTree(BiTree *T)
{
ElemType ch;
cin >> ch;
if ('#' == ch)
{
*T = NULL;
}
else
{
*T = (BiTree) malloc(sizeof(BiTNode));
if (!*T)
{
exit(OVERFLOW);
}
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
