六. 树

树的定义: 树是n(n >= 0)个结点的有限集。n = 0时称为空树。在任意一棵非空树中: (1)有且仅有一个特定的称为根(Root)的结点；(2)当n > 1时，其余结点可分为m(m > 0)个互不相交的有限集，其中每个集合本身又是一棵树，并且称为根的子树。
结点拥有的子树数称为结点的度。度为0的结点称为叶结点或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。
结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中结点的最大层次称为数的深度或高度。
如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

树的存储结构

双亲表示法

假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示双亲结点在数组中的位置。

#define MAX_TREE_SIZE 20

typedef int TElemType;

/**
 结点结构
 */
typedef struct PTNode {
    TElemType data;
    int parent;
}PTNode;

/**
 树结构
 */
typedef struct {
    PTNode nodes[MAX_TREE_SIZE]; //结点数组
    int r, n; //根的位置和结点树
}PTree;

孩子表示法

每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。
孩子表示法则是把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。

/**
 结构结点
 */
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;

孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

typedef struct CSNode {
    TElemType data;
    struct CSNode *firstchild, *rightsib;
}CSNode, *CSTree;

这个表示法的最大好处是它把一颗复杂的树变成了一颗二叉树。

二叉树

二叉树是n(n >= 0)个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的，分别称为根结点的左子树和右子树的二叉树组成。
二叉树具有五种基本形态:

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

特殊二叉树

1. 斜树
   所有的结点都只有左子树的二叉树叫左斜树。所有结点都只有右子树的二叉树叫做右斜树。这两者统称为斜树。
2. 满二叉树
   在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
3. 完全二叉树
   对一颗具有n个结点的二叉树按层序编号，如果编号为i(1 <= i <= n)的结点与通样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的。

完全二叉树的特点:

1. 叶子结点只能出现在最下两层。
2. 最下层的叶子一定集中在左部连续位置。
3. 倒数二层，若有叶子结点，一定都在右部连续位置。
4. 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
5. 同样结点树的二叉树，完全二叉树的深度最小。

二叉树的性质

• 性质1: 在二叉树的第i层上至多有2^{i - 1}个结点(i >= 1)。
• 性质2: 深度为k的二叉树至多有2^k - 1个结点(k >= 1)。
• 性质3: 对任何一棵二叉树T，如果其终端结点数为n⁰，度为2的结点数为n²，则n⁰ = n² + 1。注: 下标中的0为没有叶结点，下标2为子树有2个结点。
• 性质4: 具有n个结点的完全二叉树的深度为㏒₂ⁿ + 1([x]表示不大于x的最大整数)。
• 性质5: 如果有一棵有n个结点的完全二叉树(㏒₂ⁿ + 1)的结点按层序编号(从第1层到第㏒₂ⁿ + 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。

二叉树的存储结构

二叉树的顺序存储

二叉树的顺序存储结构就是用一堆数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。顺序存储结构一般只用于完全二叉树。

二叉链表

二叉树每个结点最多有两个孩子，所以为它涉及一个数据域和两个指针域，这样的链表叫做二叉链表。

/**
 二叉树的二叉链表结点结构定义
 */
typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

遍历二叉树

假设二叉树的结构如下

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
如果限制了从左到右的遍历方式则主要分为四种：

1. 前序遍历
   规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

void PreOrderTraverse(BiTree T) {
    if (T == NULL) { return; }
    printf("%c", T->data);
    PreOrderTraverse(T->lchild); //一直递归调用左子树直到结点为NULL(叶结点)
    PreOrderTraverse(T->rchild); //再递归调用右子树
}

遍历的顺序为: A->B->D->G->H->C->E->I->F

2. 中序遍历
   规则是若树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结点，从左子树的最后一层的左边的叶结点开始)，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。

void InOrderTraverse(BiTree T) {
    if (T == NULL) { return; }
    InOrderTraverse(T->lchild);
    printf("%c", T->data);
    InOrderTraverse(T->rchild);
}

遍历的顺序为: G->D->H->B->A->E->I->C->F

3. 后序遍历
   规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。

void PostOrderTraverse(BiTree T) {
    if (T == NULL) { return; }
    InOrderTraverse(T->lchild);
    InOrderTraverse(T->rchild);
    printf("%c", T->data);
}

遍历的顺序为: G->H->D->B->I->E->F->C->A

4. 层序遍历
   规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对接点逐个访问。

遍历的顺序为: A->B->C->D->E->F->G->H->I

二叉树的建立

为了能让每个结点确认是否有左右孩子，将二叉树中每个结点的空指针引出一个虚结点，其值可以为一特定值，比如'#'。称这种处理后的二叉树为原二叉树的扩展二叉树。

void CreateBiTree(BiTree *T) {
    TElemType ch;
    scanf("%d", &ch);
    if (ch == '#') {
        *T = NULL; //将二叉树每个结点的空指针引出一个虚结点，其值为一特定值，比如'#'
    } else {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (!*T) { exit(OVERFLOW); }
        (*T)->data = ch;
        CreateBiTree(&(*T)->lchild); //左结点
        CreateBiTree(&(*T)->rchild); //右结点
    }
}

线索二叉树

指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树。

/* Link == 0 表示指向左右孩子指针，Thread == 1表示指向前驱或后继的线索 */
typedef enum {Link, Thread} PointerTag;

typedef struct BiThrNode {
    TElemType data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag;
    PointerTag RTag; // 左右标志
}BiThrNode, *BiThrTree;

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索，由于前驱和后继的信息只有在遍历该二叉树时才能获得，所以线索化的过程就是在遍历的过程中修改空指针的过程。

//中序遍历线索化的递归函数

BiThrTree pre;

void InThreading(BiThrTree p) {
    if (p) {
        InThreading(p->lchild);
        if (!p->lchild) {
            p->LTag = Thread;
            p->lchild = pre;
        }
        if (!p->rchild) {
            p->RTag = Thread;
            pre->rchild = p;
        }
        pre = p;
        InThreading(p->rchild);
    }
}

Status InOrderTraverse_Thr(BiThrTree T) {
    BiThrTree p;
    p = T->lchild; //p指向根结点
    while (p != T) { //空树或遍历结束时，p == T
        while (p->LTag == Link) { //当LTag == 0时循环到中序序列第一个结点
            p = p->lchild;
            printf("%c", p->data);
        }
        while (p->RTag == Thread && p->rchild != T) {
            p = p->rchild;
            printf("%c", p->data);
        }
        p = p->rchild; //p进至其右子树根
    }
    return OK;
}

如果所用的二叉树需经常遍历或查找结点时需要某种便利序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。时间复杂度为O(n)。

树、森林与二叉树的转换

树转换为二叉树

步骤如下:

1. 加线。在所有兄弟结点之间加一条连线。
2. 去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
3. 层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。

森林转换为二叉树

森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作。
步骤如下:

1. 把每个树转换为二叉树。
2. 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

二叉树转换为树

二叉树转换为树转换为二叉树的逆过程。

1. 加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点.......，左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。
2. 去线。删除原二叉树中所有结点与其右孩子结点的连线。
3. 层次调整。使之结构层次分明。

二叉树转换为森林

判断一棵二叉树能够转换成一棵树还是森林，只需要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。

1. 从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除，直到所有右孩子连线都删除为止，得到分离的二叉树。
2. 再将每棵分离后的二叉树转换为树即可。

树与森林的遍历

树的遍历分两种方式。

1. 一种是先根遍历树，即先访问树的结点，然后依次先根遍历根的每棵子树。
2. 另一种是后根遍历，即先依次后根遍历每棵子树，然后再访问根结点。

森林的遍历分两种方式。

1. 前序遍历：先访问森林中第一棵树的根结点，然后再依次先根遍历的每棵子树，再依次用同样方式遍历除去第一棵树的剩余数构成的森林。
2. 后序遍历：是先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。

赫夫曼树

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度就是从树根到每一结点的路径长度之和。