树

基本概念

1. 根节点
2. 内部节点
3. 叶节点
4. 相交
5. 孩子
6. 双亲
7. 兄弟
8. 度：树各个节点度的最大值
9. 深度或高度
10. 森林

树的存储结构

双亲表示法

以一组连续空间存储树的节点，在每个节点中，附设一个指示器指示其双亲节点到链表中的位置。

#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)个节点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根节点或两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

特点

1. 每个节点最多两棵子树，不存在度大于2的节点。
2. 左子树和右子树是有序的。
3. 即使树中某节点只有一棵子树，也要区分它是左子树还是右子树。

基本形态

1. 空二叉树
2. 只有一个根节点
3. 根节点只有左子树
4. 根节点只有右子树
5. 根节点既有左子树又有右子树

特殊二叉树

斜树

所有的节点都只有左子树的二叉树叫做左斜树。所有节点都只有右子树的二叉树叫做右斜树。这两者统称为斜树。

满二叉树

在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

完全二叉树

对一棵具有n个节点的二叉树按层序编号，如果编号为i(1<=i<=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

二叉树性质

结论

1. 在二叉树的第i层上至多有(2^i-1)个节点(i>=1)
2. 深度为k的二叉树至多有(2^k)-1个节点(k>=1)
3. 对任何一棵二叉树T，如果其终端(叶子)节点数为n0，度为2的节点数为n2，则n0 = n2 + 1
4. 具有n个节点的完全二叉树的深度为[logn] + 1([x]表示不大于x的最大整数，所有log都是以2为底数，下文都是如此)
5. 如果对一棵有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>(2^{k-1)-1。又由于n是整数，则(2}k-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);
    }
}