树形结构是一种十分重要的数据结构。二叉树、树与树林都属于树形结构。

树形结构每个结点最多只有一个前驱结点，但可以有多个后继的结构。

5.1 二叉树及其抽象数据类型

5.1.1 基本概念

二叉树可以定义为结点的有限集合，这个集合或者为空集，或者由根结点、左子树和右子树的二叉树组成。二叉树是一个递归定义。

相关概念

父结点、左右孩子结点、边：
若x是某二叉树的根结点，结点y是x的左(右)子树的根，则称x是y的父结点，y是x的左(右)孩子结点。有序对<x, y>称作从x到y的边。

兄弟：
具有同一父结点的结点彼此称作兄弟。

祖先、子孙：
如果结点y在以结点x为根的左右子树中，且 y != x，则称x是y的祖先，y是x的子孙。

路径、路径长度：
如果x是y的一个祖先，又有x = x0， x1,..., xn = y，满足 xi 为xi+1的父结点则称x0, x1,..., xn 为x到y的一条路径，n称为路径长度

结点的层数：
规定根的层数为0，其余结点的层数等于其父结点的层数加一。

结点的度数(边数)：
结点的非空子树(即后缀)个数叫作结点的度数。在二叉树中，结点的度数最大为2，即最多有两条边。 度数 = 总结点数 - 1

二叉树的高度(深度)：
二叉树中结点的最大层数称为二叉树的高度。

树叶、分支结点：
左(右)子树均为空二叉树的结点称为树叶，否则称为分支结点。

特殊二叉树

满二叉树：
如果一颗二叉树的任何结点或是树叶，或有两颗非空子树，则称为满二叉树，结点度数一定为0或者2.

完全二叉树：
如果一颗二叉树中，只有最下面两层结点度数小于2，其余各层结点度数都等于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

扩充的二叉树：
扩充的二叉树是对一个已有二叉树的扩充，扩充后原二叉树的结点都变为度数为2的分支结点。也就是说，如果结点的度数为2，则不变，度数为1，则增加一个分支，度数为0则增加两个分支。增加的结点称为外部结点，原有的结点称为内部结点。

5.1.2 主要性质

一般二叉树的性质

性质1 在非空二叉树的i层上，至多有2^i个结点(i >= 0)

性质2 在高度为k的二叉树上，最多有2^(k+1) - 1个结点(k >= 0)

性质3 对于任意一颗非空的二叉树，如果叶结点的个数为n0，度数为2的结点个数为n2，则 n0 = n2 + 1。
证明： B为边的总数，n为结点总数，则 n = n0 + n1 + n2, B = n - 1。 则 B = n0 * 0 + n1 * 1 + n2 * 2, 由此可以求得 n0 = n2 + 1。

完全二叉树的性质

性质4 具有n个结点的完全二叉树高度k为lgn

性质5 对于具有n个结点的完全二叉树，如果按照以上(从根结点)到下(叶结点)和从左到右的顺序对二叉树中的所有结点从0开始到n-1进行编号，则对于任意的下标为i的结点，有：
(1) 如果i = 0， 则它是根结点，如果i>0, 则它的父结点的下标为 (i - 1) / 2
(2) 如果2i+1 <= n-1, 则下标为i的结点的左孩子结点的下标为2i+1, 否则下标为i的结点没有左孩子结点
(3) 如果2i+2 <= N-1, 则下标为i的结点的右孩子结点的下标为2i+2，否则下标为i的结点没有右孩子结点

满二叉树性质

性质6 在满二叉树中，叶节点的个数比分支结点个数多1.

扩充的二叉树性质

性质7 在扩充二叉树中，外部结点的个数比内部结点的个数多1。这个由性质6和内外部结点的定义可以得到

性质8 对任意扩充的二叉树，外部路径长度E和内部路径长度I之间满足以下关系： E = I + 2n, 其中n是内部结点的个数

5.1.3 抽象数据类型

假设 BinTree 表示二叉树类型，用BinTreeNode 表示二叉树中结点的类型，作为抽象数据类型二叉树可以提供的操作十分丰富。在ADT BinTree中，定义了最常见的操作如下：

ADT BinTree is 
operations
    // 创建一颗空的二叉树
    BinTree createEmptyBinTree(void);
    // 返回一颗二叉树，其根结点是root，左右二叉树分别为left 和 right
    BinTree consBinTree（BinTreeNode root, BinTree left, BinTree right);
    // 判断二叉树是否为空
    int isEmpty(BinTree tree);
    // 返回二叉树的根结点
    BinTreeNode root(BinTree tree);
    // 返回结点p的双亲结点
    BinTree parent(BinTree tree, BinTreeNode p);
    // 返回p结点的左子树
    BinTree leftChild(BinTree tree, BinTreeNode p);
    // 返回p结点的右子树
    BinTree rightChild(BinTree tree, BinTreeNode p);
end ADT BinTree

5.2 二叉树的遍历

5.2.1 什么是遍历？

二叉树的遍历是一种按某种方式系统地访问二叉树中的所有结点的过程，使每个结点都被访问一次且只被访问一次。

5.2.2 遍历的分类

遍历的方法尅分成两类，一类是广度优先遍历，一类是深度优先遍历。

深度优先遍历

二叉树的遍历有6种，如果限定从左到右，则只能采用三种，即先根次序遍历、后根次序遍历和中根次序遍历。

先根次序 先访问根，然后先序遍历左子树，再先序遍历右子树

后根次序 先后序遍历左子树，然后后序遍历右子树，再遍历根

中根次序 先中序遍历左子树，然后遍历根，然后中序遍历右子树

广度优先遍历

若二叉树的高度为h，则从0到h逐层如下处理：从左到右逐个访问存在的结点

广度优先遍历一颗二叉树所得到的结点序列，叫作这颗二叉树的层次序列

5.2.3 一个例子 (略过)

5.2.4 遍历的抽象算法

二叉树的先序遍历递归描述：

void preTreeWalk(BinTree tree) {
    if (tree == NULL) {
        return;
    }
    visit(root(tree));
    preTreeWalk(leftChild(tree));
    preTreeWalk(rightChild(tree));
}

二叉树的先序遍历非递归描述：

void iterativePreTreeWalk(BinTree tree) {
    Stack s;
    BinTreeNode *c;
    if (tree == NULL) {
        return;
    }
    s = createEmptyStack();
    push(s, t);
    while(!isEmptyStack(s)) {
        c = top(s);
        pop(s);
        if (c != NULL) {
            visit(root(c));
            push(s, rightChild(c));
            push(s, leftChild(c));
        }
    }
}

二叉树的中序遍历递归描述：

void inTreeWalk(BinTree tree) {
    if (tree == NULL) {
        return;
    }
    inTreeWalk(leftChild(tree));
    visit(root(tree));
    inTreeWalk(rightChild(tree));
}

二叉树的中序遍历非递归描述：

void iterativeInTreeWalk(BinTree tree) {
    Stack s = createEmptyStack();
    BinTree c = t;
    if (c == NULL) {
        return;
    }
    do {
        while (c != NULL) {
            push(s, c);
            c = leftChild(c);
        }
        c = top(s);
        pop(s);
        visit(root(c));
        c = rightChild(c);

    } while (c != NULL || !isEmptyStack(s));
}

二叉树的后序遍历递归描述：

void postTreeWalk(BinTree tree) {
    if (tree == NULL) {
        retur;
    }
    postTreeWalk(leftChild(tree));
    postTreeWalk(rightChild(tree));
    visit(root(tree));
}

二叉树的后序遍历非递归描述：

void iterativePostTreeWalk(BinTree tree) {
    Stack s = createEmptyStack();
    BinTree pr;
    BinTree p = tree;
    while (p != NULL || !isEmptyStack(s)) {
        // 将左子树压入栈中
        while (p != NULL) {
            push(s, p);
            pr = rightChild(p);
            p = leftChild(p);
            if (p == NULL) {
                p = pr;
            }
        }
        // 从栈顶取出元素
        p = top(s);
        pop(s);
        // 访问元素
        visit(root(p));
        // 取得右子树
        if (!isEmptyStack(s) && leftChild(top(s)) == p) {
            p = rightChild(top(s));
        } else {
            p = NULL;
        }
    }
}

广度优先遍历二叉树的伪代码描述如下：

void levelTreeWalk(BinTree tree) {
    
    BinTree c, cc

    Queue q = createEmptyQueue();

    if (tree == NULL) {
        return;
    }
    c = tree;
    enQueue(q,c)
    while (!isEmptyQueue(q)) {
        c = frontQueue(q);
        deQueue(q);
        visit(root(c));
        cc = leftChild(c);
        if (cc != NULL) {
            enQueue(q, cc);
        }
        cc = rightChild(c);
        if (cc != NULL) {
            enQueue(q, cc);
        }
    }
}

5.3 二叉树的实现

5.3.1 顺序表示

二叉树的顺序表示，也是采用一组连续的存储单元来存放二叉树中的结点。对于完全二叉树，只要通过数组下标的关系，就可以确定结点之间的逻辑关系，其他类型二叉树无法根据存储的先后顺序确定
顺序表示的二叉树定义如下：

struct SeqBinTree {
    int MAXIMUM;    // 允许结点的最大个数
    int n;          // 改造成完全二叉树后，结点的实际个数
    DataType * nodelist;    // 存放结点的数组
};
typedef struct SeqBinTree *PSeqBinTree; // 顺序二叉树的指针类型

运算的实现

下标为p的结点双亲结点的下标：

int parent(PSeqBinTree tree, int p) {
    if (p < 0 || p >= tree->n) {
        return -1;
    }
    return (p - 1) / 2;
}

下标为p的结点左孩子结点的下标：

int leftChild(PSeqBinTree tree, int p) {
    if (p < 0 || p >= tree-> n) {
        return -1;
    }
    return 2 * p + 1;
}

下标为p的结点左孩子结点的下标：

int rightChild(PSeqBinTree tree, int p) {
    if (p < 0 || p >= tree-> n) {
        return -1;
    }
    return 2 * (p + 1);
}

显然，顺序表示对完全二叉树比较合适，既可以节省空间，又可以利用数组元素的下标确定结点在二叉树中的位置以及结点之间的关系。

5.3.2 链表表示

二叉树的链表表示是用一个链表来存储一颗二叉树，二叉树中的每个结点对应链表中的一个结点。

每个结点可以形象地描述为：
|left|right|info|

C语言描述如下：

typedef struct BinTreeNode {
    DataType info;
    struct BinTreeNode * left;
    struct BinTreeNode * rightl
} BinTreeNode;

运算的实现

返回p结点的左孩子结点的指针：

BinTreeNode *leftChild(BinTreeNode *p) {
    if (p == NULL) {
        return NULL;
    }
    return p->left;
}

返回p结点的右孩子结点的指针：

BinTreeNode *rightChild(BinTreeNode *p) {
    if (p == NULL) {
        return NULL;
    }
    return p->right;
}

实现求双亲结点的操作比较困难，需要从根结点出发查找当前结点的位置。为了方便使用，可以增加一个双亲指针parent

5.3.3 线索二叉树

线索二叉树是对左-右指针表示法的一种修改
它利用空的左指针存储该节点的某种遍历序列前驱结点的位置，利用空的右指针在同种遍历序列中的后继结点的位置
这种附加的指向前驱和后继结点额指针称为线索。

为了区分左右指针和线索，需要在每个结点里面增加两个标志位ltag 和rtag，当tag置为1时，表示线索
用C语言表述如下：

typedef struct ThreadTreeNode {
    DataType *info;
    struct ThreadTreeNode * left;
    struct ThreadTreeNode * right;
    int ltag, rtag;
} ThreadTreeNode, ThreadTree;

中序线索化二叉树：

void threadTree(ThreadTree *tree) {
    // 创建一个M大小的空顺序栈，M一般为树的高度
    SeqStack *st = createEmptyStack(M);
    
    ThreadTree *p, *pr;
    if (tree == NULL) {
        return;
    }

    p = tree;
    pr = NULL;
    do {
        while (p != NULL) {
            push(st, p);
            p = p->left;
        }
        p = top(st);
        pop(st);
        if (pr != NULL) {
            if (pr->right == NULL) {
                pr->right = p;
                pr->rtag = 1;
            }
            if (p->left == NULL) {
                p->left = pr;
                p->ltag = 1;
            }
        }
        pr = p;
        p = p->right;
    } while (!isEmptyStack(st) || p != NULL);
}

构造中序线索二叉树的最大意义是：可以很方便地从中找到指定结点在中序序列中的前驱和后继，而不必重新遍历二叉树

中序遍历中序线索二叉树：

void threadInTreeWalk(ThreadTree *tree) {
    ThreadTree *p = tree;
    if (tree == NULL) {
        return;
    }
    while (p->left != NULL && p->ltag == 0) {
        p = p->left;
    } 
    while (p != NULL) {
        visit(*p);
        if (p->right != NULL && p->rtag == 0) {
            p = p->right;
            // 右子树的左子树一直向下
            while (p->left != NULL && p->ltag == 0) {
                p = p->left;
            }
        } else {
            p = p->right;
        }
    }
}

5.4 二叉树的应用

5.4.1 堆与优先队列

首先给出堆得定义：n个元素的序列 K = (k0, k1,..., kn-1) 称为堆，当且仅当满足条件：
ki >= k(2i+1) && ki >= k(2i+2)
或者
ki <= k(2i+1) && ki <= k(2i+2)

这个特征称为堆序性。 如果堆根结点最小，则称为小根堆，根结点最大，则称为大根堆

优先队列

优先队列是一种常见的抽象数据类型，跟普通的队列不同，不遵循“先进先出”的原则，而遵循“最小元素先出”的原则。优先队列的基本操作有三种：
添加元素，找出做小元素和删除优先队列中的最小元素
优先队列的抽象数据类型如下：

ADT PriorityQueue is 
Operations
    // 创建一个空的优先队列 
    PriorityQueue createEmptyPriQueue(void);
    // 判断队列是否为空
    int isEmpty(PriorityQueue s);
    // 添加元素
    void add(PriorityQueue s, DataType data);
    // 返回最小元素
    DataType min(PriorityQueue s);
    // 删除最小元素
    void removeMin(PriorityQueue s);

end ADT PriorityQueue

在优先队列中找出最小元素并删除：

DataType deleteMin(PriorityQueue pq) {
    DataType result;
    result = min(pq);
    removeMin(pq);
    return result;
}

优先队列的实现

(1) 存储结构
优先队列的定义与二叉树的顺序表示基本一样：

typedef struct PriorityQueue {
    int MAXNUM; // 堆中的元素个数上限
    int n;      // 堆中的实际元素个数
    DataType *pq;   //堆中元素的顺序表示
} PriorityQueue;

(2) 操作的实现
向优先队列中插入一个元素：

void addHeap(PriorityQueue *queue, DataType x) {
    int i;
    if (queue->n >= MAXNUM - 1) {
        printf("Full !\n");
        return;
    }

    for (i = queue->n; i >0 && queue->pq[(i - 1) / 2] > x; i = (i - 1) / 2) {
        queue->pq[i] = queue->pq[(i - 1) / 2];
    }
    queue->pq[queue->i] = x; 
    queue->n++;
}

从优先队列中删除最小元素：

void removeMin(PriorityQueue *queue) {
    int s;
    if (isEmptyHeap(queue)) {
        printf("Empty!\n");
        return;
    }
    s = --queue->n;
    queue->pq[0] = queue->pq[s];
    sift(queue, s, 0);
}

把完全二叉树从指定结点调整为堆：

void sift(PriorityQueue *queue, int size, int p) {
    DataType temp;
    int i, child;
    temp = queue->pq[queue->p];
    i = p;
    child = 2 * i + 1;
    while (child < size) {
        if (child < size-1 && queue->pq[child].key >queue->pq[child + 1].key) {
            child++;
        }
        if (temp.key > queue->pq[child].key) {
            queue->pq[i] = queue->pq[child];
            i = child;
            child = 2 * i + 1;
        } else {
            break;
        }
    }
    queue->pq[i] = temp;
}

5.4.2 哈夫曼树及其应用

若用E表示某扩充二叉树的外部路径长度，则有：
E = ∑li, i = 1 to m
其中li为从根到第i个外部结点的路径长度，m为外部结点的个数。
设扩充二叉树具有m个带有权值得外部结点，那么从根结点到外部结点的路径长度与相应权值的乘积和，叫做扩充二叉树的带权外部路径：
WPL = ∑wili，i = i to m
wi是第i个外部结点的权值

假设有一组(无序)实数{w1,w2,w3,...,wm}, 现要构造一颗以wi为权的m个外部结点的扩充二叉树，使得带权的外部路径长度WPL最小，满足这一要求的扩充二叉树就被称作哈夫曼树，又称最优二叉树。
例子：
给出带权是{ 2,3,4,11 }, 可以构造出不同的扩充二叉树，其中三种如下：

    O                        O                    O
   / \                      / \                  / \
  11  O                    O   2                O   O
     / \                  / \                  / \ / \
    4   O                3   O                2 11 3  4
       / \                  / \
      2   3                4  11
      (a)                   (b)                  (c)

上面的带权外部路径长度分别为：
(a) WPL = 1x11 + 2x4 + 3x2 + 3x3 = 34
(b) WPL = 1x2 + 2x3 + 3x4 + 3x11 = 53
(c) WPL = 2x2 + 2x11 + 2x3 + 2x4 = 40

由此可见，对于一组带有确定权值的外部结点，构造出不同扩充二叉树，带权外部路径长度并不相同。

哈夫曼树的构造

从上面的例子可以看出，一棵扩充二叉树要使得WPL最小，必须使权值越大的外部结点离根越近，权值越小离根越远。使用哈夫曼算法可以构造一棵最优二叉树。

算法的基本思想：
(1) 由给定的m个权值{w1,w2,w3,...,wm}，构造m棵由空二叉树扩充得到的扩充二叉树{T1,T2,...,Tm}。每个Ti(1<= i <= m)只有一个外部结点，其权值外wi.
(2) 在已经构造的所有扩充二叉树中，选取根结点的权值最小和次最小的两棵，将其作为左、右子树，构造成一棵新的扩充二叉树，根结点的权值置为左、右子树根结点权值之和
重复步骤(2)，每次都使扩充二叉树的个数减一，当只剩一棵扩充二叉树时，它便是所要构造的哈夫曼树。

数据结构：
C语言定义为：

typedef struct HTNode {
    int wpl;        // WPL权值
    int parent;     // 双亲结点下标，无则置为-1
    int left;       // 左孩子结点下标，无则置为-1
    int right;      // 右孩子结点下标，无则置为-1
} HTNode;

typedef struct HTTree {
    int m;          // 外部结点个数
    int root;       // 根结点下标
    HTNode *hTree;  // 存放 2xm-1个结点的数组
} HTTree;

哈夫曼算法：

HTTree *huffmanTree(int m, int *w) {
    HTTree *pht;
    int i, j, x1, x2, m1, m2;
    pht = (HTTree *) malloc(sizeof(HTTree));
    if (pht == NULL) {
        printf("Out of space!\n");
        return pht;
    }
    pht->hTree = (HTNode *) malloc(sizeof(HTNode));

    // 设置数组初始值
    for (i = 0; i <2 * m-1; i++) {
        pht->hTree[i].left = -1;
        pht->hTree[i].right = -1;
        pht->hTree[i].parent = -1;
        if (i < m) {
            pht->hTree[i].wpl = w[i];
        } else {
            pht->hTree[i].wpl = -1;
        }
    }

    for (i = 0; i < m - 1; i++) {
        m1 = MAXINT;    // 最小权值
        m2 = MAXINT;    // 次最小权值
        x1 = -1;        // 最小下标
        x2 = -1;        // 次最小下标

        // 找出最小权的无双亲结点的结点
        for (j = 0; j < m+i; j++) {
            if (pht->hTree[j].wpl < m1 && pht->hTree[i].parent == -1) {
                m2 = m1; 
                x2 = x1;
                m1 = pht->hTree[j].wpl;
                x1 = j; // x1存放最小权的无双亲结点的结点下标
            } else if (pht->hTree[j].wpl < m2 && pht->hTree[j].parent == -1) {
                m2 = pht->hTree[j].wpl;
                x2 = j; // x2存放次最小权的无双亲结点的结点下标
            }
        }

        // 构造内部结点
        pht->hTree[x1].parent = m + i;
        pht->hTree[x2].parent = m + i;
        pht->hTree[m+i].wpl = m1 + m2;
        pht->hTree[m+i].left = x1;
        pht->hTree[m+i].right = x2;
    }
    // 根结点的位置
    pht->root = 2 * m - 2；
    return pht;
}

哈夫曼编码：
设
d = {d1,d2,...,dn}为需要编码的字符集合
w = {w1,w2,...,wn}为d中各个字符出现的概率
现要对d进行二进制编码，使得：
(1) 按给出的编码传输文件时，通讯编码总长最短
(2) 若di != dj，则di的编码不可能是dj编码的开始部分(前缀)
满足上述要求额二进制编码称为最优前缀编码

最优前缀编码(哈夫曼编码)可以用哈夫曼树来实现：
d1,d2,..,dn作为外部结点，w1,w2,...,wn作为外部结点的权值，构建哈夫曼树。在哈夫曼树中，把从每个结点的指向左孩子结点的边标上二进制数"0"，指向右孩子的边标上二进制数"1"。从根到每个叶结点路径上的二进制数连接起来，就是这个叶节点所代表的最优前缀编码。这种编码叫作哈夫曼编码。

编码的结果是，出现概率大的字符其编码较短，出现概率小的字符其编码较长。

解码时，从二叉树的根结点开始，用需要编码的二进制位串，从头开始与二叉树根结点到子结点边上标的0、1相匹配，确定一条到达树叶结点的路径，一旦到达树叶结点，则译出一个字符，然后再回到根结点，从二进制位串中的下一位开始继续解码。

5.5 树及其抽象数据类型

树形结构在客观世界是大量存在的。一棵树几种不同的表现形式：树形、文氏图、凹入表、嵌套括号

5.5.1 基本概念

树氏包含 n(n>=0) 个结点的有穷集合T，当T非空时满足：
(1) 有且仅有一个特别标出的称作根的结点
(2) 除了根结点外，其余结点分别为若干个不相交的非空集合T1,T2,...,Tm，这些集合中的每一个又都是树。树T1,T2,...,Tm称作这个根结点的子树

只包括一个结点的树是仅由根结点构成。不包含任何结点的树称作空树。

树中的一个结点的子结点个数叫作这个结点的度数。其中度数最大的结点的度数叫作树的度数。

对于子树的次序不加区别的树叫作无序树，对于子树之间的次序加以区别的树叫作有序树。

5.5.2 抽象数据类型

树型结构的抽象数据结构如下：

ADT Tree is
Operations
    // 创建一棵空树
    Tree createEmptyTree(void)
    // 以p为根，t1,...,ti为子树创建一颗树
    Tree consTree(Node p, Tree t1, ... Tree ti)
    // 判断树是否为空
    int isEmpty(Tree t)
    // 父结点 
    Node parent(Node p)
    // 左孩子结点
    Tree leftChild(Tree t)
    // 右兄弟树
    Tree rightSibling(Tree t);
end ADT Tree

5.5.3 树的遍历

树的遍历是一种按某种方式系统地访问树中的所有结点的过程，它使每个结点都被访问一次并且只访问一次。

深度优先遍历

先序遍历 —— 首先访问根结点，然后从左到右按先序遍历根结点的每棵子树
后序遍历 —— 首先从左到右按后序遍历根结点的每棵子树，最后访问根结点

先序遍历的递归算法：

void preTreeWalk(Tree *tree) {
    Tree *subTree;
    if (tree == NULL) {
        return;
    }
    visit(root(tree));
    subTree = leftChild(tree);
    while (subTree != NULL) {
        preTreeWalk(subTree);
        subTree = rightSibling(subTree);
    }
}

先序遍历的非递归算法：

void iterativeTreeWalk(Tree *tree) {
    Tree *subTree = tree;
    Stack *s = createEmptyStack();
    do {
        while (subTree != NULL) {
            visit(root(subTree));
            push(s, subTree);
            subTree = leftChild(subTree);
        }
        while ((subTree == NULL) && !isEmptyStack(s)) {
            subTree = rightSibling(top(s));
            pop(s);
        }
    } while (subTree != NULL);
}

后序遍历的递归算法：

void postTreeWalk(Tree *tree) {
    Tree *subTree;
    if (tree == NULL) {
        return;
    }
    subTree = leftChild(tree);
    while(subTree != NULL) {
        postTreeWalk(subTree);
        subTree = rightSibling(subTree);
        visit(root(tree));
    }
}

广度优先遍历算法：

void levelTreeWalk(Tree *tree) {
    Tree *subTree;
    Queue *queue;
    queue = createEmptyQueue();
    subTree = tree;
    if (subTree == NULL) {
        return;
    }
    // 将子树入队
    enQueue(queue, subTree);
    while (!isEmptyQueue(queue)) {
        // 不断从队列中取出子树
        subTree = frontQueue(queue);
        deQueue(queue);
        // 访问子树的根结点
        visit(root(subTree));
        // 找到长子
        subTree = leftChild(subTree);
        while (c != NULL) {
            // 子树入队
            enQueue(queue, subTree);
            // 找到当前子树的右兄弟子树入队
            subTree = rightSibling(subTree);
        }
    }
}

5.6 树的实现

5.6.1 父指针表示法

用一组连续的存储空间，存储树中的各个结点，数组中的一个元素为一个结构，其中包含结点本身的信息以及本结点的父结点在数组中的下标，树的这种存储放方法称为父指针表示法。
结构体定义如下：

struct ParTreeNode{
    DataType info;
    int parent;
};

树的定义如下：

typedef struct ParTree {
    int MAXNUM;
    int n;
    ParTreeNode *nodeList;
} ParTree;

求兄弟结点的位置：

int rightSibling(ParTree *tree, int p) {
    int i;
    if ( p >= 0 && p < tree->n) {
        for (i = p + 1; i < tree->n; i++) {
            if (tree->nodeList[i].parent == tree->nodeList[p].parent) {
                return i;
            }
        }
    }
    return -1;
}

求左孩子结点的位置：

int leftChild(ParTree *tree, int p) {
    if (tree->nodeList[p + 1].parent == p) {
        return p + 1;
    } else {
        return -1;
    }
}

父指针表示法比较节省存储空间，但求某个结点的兄弟运算比较慢。

5.6.2 子表表示法

重要而常用的表示方法。把整棵树表示成一个结点表，而结点表中的每个元素又包含一个表，它记录了这个结点的所有子结点的位置，称为子表。结点表的长度即树中结点的个数们一般用一维数组顺序存储。
子表表示法定义如下：

typedef struct EdgeNode {
    int nodePosition;
    struct EdgeNode *link;
} EdgeNode;

结点表中每个结点定义如下：

typedef struct ChildTreeNode {
    DataType info;
    EdgeNode *children;
} ChildTreeNode;

子表表示的树结构定义如下：

typedef struct ChildTree {
    int MAXNUM;
    int n;
    ChildTreeNode *nodeList; 
} ChildTree;

求右兄弟结点的位置:

int rightSibling(ChildTree *tree, int p) {
    int i;
    EdgeNode *v;
    for (i = 0; i < tree->n; i++) {
        v = tree->nodeList[i].children;
        while (v != NULL) {
            if (v->nodePosition == p) {
                if (v->link == NULL) {
                    return -1;
                } else {
                    return v->link->nodePosition;
                }
            } else {
                v = v->link;
            }
        }
    }
    return -1;
}

求父结点的位置:

int parent(ChildTree *tree, int p) {
    int i;
    EdgeNode *v;
    for (i = 0; i < tree->n; i++) {
        v = tree->nodeList[i].children;

        while (v != NULL) {
            if (v->nodePosition == p) {
                return i;
            } else {
                v = v->link;
            }
        }
    }
    return -1;
}

5.6.3 长子-兄弟表示法

这种表示法是在树中的每个结点中除其信息域，再增加一个纸箱其最左子结点的指针域lChild和指向其右兄弟指针域rSibling
结点定义如下：

typedef struct CSNode {
    DataType info;
    struct CSNode *lchild;
    struct CSNode *rsibing;
} CSNode;

5.6.4 树的其他表示法

除了前面介绍的各种表示方法以外，树还有带右兄弟指针和子结点标记的先根次序表示法、带有右兄弟和子结点双标记的先根次序表示法、带长子指针和右兄弟标记的层次次序表示法以及带度数的后根次序表示法等

5.7 树林

树林是由零个或多个不相交的树所组成的集合。树林中的树也是有序的，彼此称为兄弟。这里的树林可以是一个空集，也可以由一棵树构成。

5.7.1 树林的遍历

先根次序遍历 —— 首先访问树林中第一棵树的根结点，然后先根次序遍历第一棵树除去根结点剩下的所有子树构成的树林，最后先根次序遍历除去第一棵树之后剩下的树林

后根次序遍历 —— 首先后根次序遍历第一棵树的根结点的所有子树构成的树林，然后访问树林中第一棵树的根结点，最后后根次序遍历除去第一棵树之后剩下的树林

5.7.2 树林的存储表示

所有树的表示方法都可以推广到树林的表示。

5.7.3 树林与二叉树的转换

在树林(包括树)与二叉树之间有一个自然的一一对应关系。任何树都唯一地对应到一棵二叉树。反过来也成立。

树林转为二叉树

步骤如下：
首先在所有相邻的兄弟结点之间加一条线
然后对每个非终端结点，只保留它的其最左子结点的连线，删去其他孩子结点之间原有的连线。
最后以根结点为轴心，将整棵树顺时针旋转一定角度，使其层次分明

二叉树转为树林

步骤如下：
(1) 若某结点是其父母的左子结点，则把该结点的右结子结点递归用虚线连起来
(2) 去掉原二叉树中所有父母到右子结点的连线。