树是数据结构中很重要的一环，更是C/C++高手的挚爱。

     今天就来讨论下数据结构中的树。

      先梳理下关于树一些基本概念。

树的基本概念

（1）树（Tree）的概念：树是一种递归定义的数据结构，是一种重要的非线性数据结构。树可以是一棵空树，它没有任何的结点；也可以是一棵非空树，至少含有一个结点。

（2）根（Root）：有且仅有一个结点的非空树，那个结点就是根。

（3）子树（Subtree）：在一棵非空树中，除根外，其余所有结点可以分为m（m≥0）个互不相交的集合。每个集合本身又是一棵树，称为根的子树。

（4）结点（Node）：表示树中的元素及若干指向其子树的分支。

（5）结点的度（Degree）：一个结点拥有的子树数目称为该结点的度。

（6）叶子结点（Leaf）：度为0的结点。

（7）孩子（Child）：结点子树的根称为该结点的孩子。

（8）双亲（Parents）：孩子结点的上层结点叫该结点的双亲。

（9）兄弟（Sibling）：同一双亲的孩子。

（10）树的度：一棵树中最大的结点度数。

（11）结点的层次（Level）：从根结点开始定义根为第一层，它的孩子为第二层，依此类推。

（12）深度（Depth）：树中结点最大层次的值。

（13）有序树：树中的各子树自左向右有序的称为有序树。

（14）无序树：树中的各子树自左向右无序的称为无序树。

（15）森林（Forest）：是m（m≥0）棵互不相交的树的集合。

（16）祖先：是指从根结点到该结点之间所有的结点。

图解说明

                                            树

如图所示：

A是根结点，A结点的度是3，D结点的度是3；因为3是结点的度的最大值，所以这棵树的度是3；E、G、H、I、K、L和M是叶子结点。A在树的第一层，B、C、D在树的第二层，E、F、G、H、I、J在树的第三层，K、L、M在树的第四层；树的深度是4。树从左往右是有序的，这是一棵有序树；E结点的祖先是A、B。

二叉树（Binary Tree）

      概念：二叉树又叫二分树，它的特点是每个结点最多只有二棵子树，也就是二叉树中没有度大于2的结点。二叉树的子树有左右之分，严格区分左孩子、右孩子，其次序不能颠倒。

二叉树有5种形态：

（1）空二叉树。

（2）只有一个根结点。

（3）只有根结点和左子树。

（4）只有根结点和右子树。

（5）有根结点和左、右子树。

满二叉树

     概念：一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。

完全二叉树

     概念：如果有深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。

二叉树的性质

（1）在二叉树的第i层上至多有2^i-1(i ≥1)。

（2）深度为k的二叉树至多有2^k-1个结点(k≥1)。

（3）对任何一棵二叉树，如果n0、n1、n2分别表示度数为0、1、2的结点树，则有n0=n2+1。

（4）具有n个结点的完全二叉树的深度为log₂n + 1。

（5）如果对一棵有n个结点的完全二叉树，则对任一结点i（1≤i≤n）有：

       <1> 如果i=1，则结点i是二叉树的根结点，无双亲；如果i>1，则双亲PARENT(i)是结点i/2。

       <2> 如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)结点2i。

       <3> 如果2i+1>n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1。

二叉树的存储

（1）顺序存储结构

顺序存储结构仅适用于完全二叉树的存储，就是把完全二叉树从上到下、从左到右的顺序存储到一块连续的存储空间中。一般存储在一维数组中。

上图完全二叉树的顺序存储结构如下：

（2）链式存储结构

链式存储结构有二叉树链表结构各三叉链表存储结构。一般都是使用二叉链表进行存储。

二叉链表结点结构定义如下：

typedef struct bitnode
{
int num;
struct bitnode *lchild;
struct bitnode *rchild;
}TREENODE;

                                                      链式存储结构

二叉树的遍历

（1）先序遍历（先根遍历）

        1. 访问根结点

        2. 先序遍历左子树

        3.  先序遍历右子树

（2）中序遍历（中根遍历）

        1. 中序遍历左子树

        2. 访问根结点

        3.  中序遍历右子树

（3）后序遍历（后根遍历）

        1. 后序遍历左子树

        2. 后序遍历右子树

        3.  访问根结点

对于上图遍历结果：

        先序遍历：ABDECFG

        中序遍历：DBEAFCG

         后序遍历：DEBFGCA

线索二叉树

      线索二叉树的引出：为了解决二叉树遍历问题。对于上面的中序遍历，假如现在已经中序遍历到B结点，问题是，在编程时，怎么知道从B接下来要往哪个结点遍历，即它的直接后驱结点是谁？同时B又是从哪个结点遍历来的，即它的前驱结点是谁？在二叉树的存储结构中，知道二叉树的结点是用二叉链表进行存储的，它有两个指向左右孩子结点的指针。B结点左指针指向D,右指针指向E。但现在已经中序遍历到了B,而B的两个指针已经用了，为了能在B结点指出它的前驱结点和后继结点，需要增加两个标志位，一个指出前驱，一个指出后继结点。而对于E这种拥有空指针域的结点，同时可以用空指针域和标志位来标识前驱后后继结点。

      概念：利用二叉链表中的空指针域存放指向结点在某种遍历次序下的前驱结点和后继结点的指针，这种附加信息的指针称为“线索”，如上图的D、E、F、G有空指针域，可以用来指向前驱结点和后继结点；而A、B、C已经没有了空指针域，这时这要靠增加的两个标志位来说明前驱结点和后继结点。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为为线索二叉树（Threaded Binary Tree）。

typedef struct bitnode
{
int num;
struct bitnode *lchild;
struct bitnode *rchild;
int ltag;    //0表示lchild指向左孩子，1表示lchild指向前驱
    int rtag;    //0表示rchild指向右孩子，1表示rchild指向后继
}TREENODE;

根据线索性质的不同，线索二叉树分为先序二叉树、中序二叉树和后序二叉树。

现在解决上面提到中序遍历到B结点时，此时B->ltag=1，表示左孩子是它的前驱结点，即D结点；B->rtag=1,表示右孩子是它的后继结点，即E结点。

接着假如此时中序遍历到了E，则E->lchild=B,E->ltag=1,表示B是E的前驱结点；            E->rchild=A，E->rtag=1,表示A是E的后继结点。

接着假如此时中序遍历到了A结点，这这里A结点的情况是：它没有空指针域，它的两个指针已经用来指向了两个孩子，而两个孩子都不是它的前驱和后继，所以它的两个标志位都为0。可以看到，对于两个标志位都为0的情况，无法直接找到它的前驱结点和后继结点。这时需要利用中序遍历的规律进行推导：A的前驱结点必定是遍历它的左孩子时的最后一个终端结点，即从左孩子B一直向右，直到找到最后一个右标志位为“1”的结点，即E结点; 同样，A的后继结点必定是遍历它的右孩子时的第一个终端结点，即从右孩子C一直向左，直到找到第一个标志位为“1”的结点，即F结点。

相关文章：

　　•　　C/C++版数据结构之树<一>

 　　•　　C/C++版数据结构之树<二>