树

一、容易模糊的概念

子树：通常会说某个树的子树，这个子树我的概括就是摘掉这个树的根之后得到的互不相交的树。

度：结点的度——结点拥有子树的个数；树的度——树中各结点读的最大值。

叶子结点：终端结点，度为0的结点。与之相反的就是非终端结点。

祖先：从根到某个结点的路径上的所有结点，即包括该结点的双亲、双亲的双亲.....

堂兄弟：和兄弟不一样哦，就是“你双亲的兄弟的孩子”，属于二代血缘关系，兄弟是一代血缘。

子孙：一个结点的子孙就是以这个结点为根的子树中的所有结点。是所有喔！

层次：根为第1层，以此类推下去......

树的高度/深度：树中结点的最大层次。

结点的深度：定义根结点的深度为1，结点深度是从根结点开始算起。

结点的高度：定义最底层的叶子结点的高度为1，结点高度是从最底层的叶子结点算起。

二叉树：每个结点最多只有2棵子树且子树有左右之分。

满二叉树：一棵深度为n且有(2^n)-1个结点的二叉树。

完全二叉树：在满二叉树的基础上来记忆——从右到左去掉满二叉树的最下面一层的叶子结点，但是最少要留下最左边那一个，结构图形脑补10s。

二、常用性质和规律归纳：主要是二叉树的，适用于一般树的规律会另外说明。

①深度为n的二叉树的最大结点数计算：2ⁿ-1，等比数列的前n项和。

②二叉树的第i层的最大结点数：2^n-1，等比数列的第i项表达式。

③二叉树中，终端结点数为n₀，度为1的结点数为n₁，度为2的结点数为n₂，总结点数为n，他们之间的关系是：

按结点类型来统计：n=n₀+n₁+n₂

按分支类型来统计：n=n₁+2n₂+1（这里的1是假想根结点有一个分支进入，这样每一个结点都只且只有一个进入的分支，因此树的分支总数等于结点总数，除了根结点假想的进入分支以外，其他分支总数等于每一个结点射出的分支总数，度为1的结点射出1个分支，度为2的结点射出2个分支）

通常联立上边2个方程得：n₀=n₂+1

推广到普通的树中：总结点数为n，终端结点数为n₀，度为1的结点数为n₁，度为2的结点数为n₂，度为3的结点数为n₃，......一样列方程组：

n=n₀+n₁+n₂+n₃+......

n=1+n₁+2n₂+3n₃+......

④有n个结点的完全二叉树

深度等于：[log₂n]+1,其中“[ ]”表示取整。

按层序编号：i=1，结点i是二叉树的根结点；i>1，结点i的双亲的编号为[i÷2]取整。

根据结点编号i判断左右孩子：

2i>n，无左孩子；否则，左孩子的编号为2i。

2i+1>n，无右孩子；否则，右孩子的编号为2i+1。

⑤遍历二叉树：是一种操作。按照某种搜索路径访问树中的每一个结点，每个结点都只被访问一次。

规定先访问左子树，后访问右子树，以访问“根”的先后进行分类：先(根)序遍历、中(根)序遍历、后(根)序遍历，习惯省略“根”不读。

 1 typedef struct BTNode{
 2     char data;
 3     struct BTNode *lchild;
 4     struct BTNode *rchild;
 5 }BTNode;
 6 
 7 void visit(BTNode *p)
 8 {
 9     //访问结点的操作程序
10 }
11 /* 先序遍历 */
12 void preorder(BTNode *p)
13 {
14     if(p != NULL)
15     {
16         visit(p);
17         preorder(p->lchild);
18         preorder(p->rchild);
19     }
20 }
21 
22 /* 中序遍历 */
23 void inorder(BTNode *p)
24 {
25     if(p != NULL)
26     {
27         preorder(p->lchild);
28         visit(p);
29         preorder(p->rchild);
30     }
31 }
32 
33 /* 后序遍历 */
34 void inorder(BTNode *p)
35 {
36     if(p != NULL)
37     {
38         preorder(p->lchild);
39         preorder(p->rchild);
40         visit(p);
41     }
42 }

3种遍历编程模型

以这3种方式遍历下图(a)中的二叉树：

结点访问顺序：是访问，不是路过！

先序遍历：a->b->d->e->c

中序遍历：d->b->e->a->c

后序遍历：d->e->b->c->a

分析：从上边的编程模型中可以知道，树的遍历是靠函数的递归调用来实现的，对于每一个结点最少不止一次经过，这就好像我们平时从A地出发去C地办事，途径B地，刚好要在B地买一东西，我们可以在去的时候买也可以在回来的时候买，从A出发再回到A所走的路线是一样的，只是在某些地方停留“访问”的先后顺序问题。同样二叉树的遍历也一样，暂且忽略掉访问函数，三种方法所走过的路线是一样的。

含有n个结点的二叉树的三种遍历的时间复杂度都是O(n)，遍历过程中使用到的栈的开销就是数的深度，最坏的情况就是树的深度和结点数相等时空间复杂度也是O(n)。

⑥线索二叉树：二叉树通常以二叉链表的形式存储，每一个结点只有左右孩子的信息，这种指向“孩子”的链会在叶子结点形成“断点”。在上边二叉树的遍历过程中我们知道叶子结点有它对应的下一个结点，如何将这种动态信息保存起来？首先人们想到在结点中增加分别指向该节点的前驱和后继的指针，由于明显增大内存的开销就没有得到应用，天才的前辈们想到使用叶子结点的“空链域”。具体实现接着往下看。

线索二叉树的结点结构：
lchild	LTag	data	RTag	rchild

LTag和RTag的值表示lchild和rchild指向的是前驱、后继还是左右孩子。

线索数：LTag和RTag为值“1”的总数。

求：n个结点的线索二叉树上线索数x.

解：x=2n₀+n₁; n=n₀+n₁+n₂ ; n₀=n₂+1 得：x=n+1

线索二叉树分为前序、中序和后序线索二叉树。线索化的过程就是在原来树的基础上建立头结点，然后在遍历过程中填写叶子结点的空链域使其指向前驱和后继。

 1 typedef struct BiThrNode{  
 2     Element data;  
 3     struct Node* left;  
 4     struct Node* right;  
 5     PointTag Ltag;  
 6     PointTag Rtag;  
 7 }BiThrNodeType;  
 8 
 9 void InThreading(BiThrNodeType *p);//声明中序遍历线索化函数
10 BiThrNodeType  *pre;          //用来指向刚刚访问过的结点
11 
12 /*中序遍历二叉树T，并将其中序线索化，pre为全局变量*/
13 BiThrNodeType *InOrderThr(BiThrNodeType *T)
14 {    
15     /* 1.线索二叉树的头结点，指向根结点 */
16     BiThrNodeType *head;
17     head=(BitThrNodeType *)malloc(sizeof(BitThrNodeType));//设申请头结点成功
18     head->ltag=0;head->rtag=1;//建立头结点
19     head->rchild=head;//右指针回指
20     if(!T)
21         head->lchild=head;/*若二叉树为空，则左指针回指*/
22     else
23     {
24         head->lchild=T;
25         pre=head;
26         /* 2.开始进行中序线索化 */
27         InThreading(T);
28         pre->rchild=head;
29         pre->rtag=1; /*最后一个结点线索化*/
30         head->rchild=pre;
31     }
32     return head;
33 }
34 
35 /* 通过中序遍历进行中序线索化:算法## */
36 void InThreading(BiThrNodeType *p)
37 {    
38     if(p)
39     {
40         //------------------------------------------
41         InThreading(p->lchild); //左子树线索化
42         //------------------------------------------
43         if(p->lchild==NULL)/*前驱线索*/
44         {
45             p->ltag=1;
46             p->lchild=pre;
47         }
48         else
49             p->ltag=0;
50         if(p->rchild==NULL)
51             p->rtag=1;/*后驱线索*/
52         else
53             p->rtag=0;
54         if(pre!=NULL&&pre->rtag==1)
55             pre->rchild=p;
56         pre=p;
57         //------------------------------------------
58         InThreading(p->rchild); //右子树线索化
59         //------------------------------------------
60     }
61 }

例子：中序线索化实现

二叉树线索化之后，怎么使用它，继续以中序线索化为例，即如何通过得到的线索二叉树来快速访问一个结点的前驱和后继？明显，如果该结点刚好为叶子结点，那么他的两个指针域分别就指向前驱和后继，如果是非叶子结点，就需要经过计算获得：该结点的前驱是以该结点为根的左子树上按中序遍历的最后一个结点，后继是以该结点为根的右子树上按中序遍历的第一个结点。注意：先序和后序的这种情况的解决方法又不一样了。看一道选择题：

答案：D。二叉树能够以先序、中序、后序进行线索化，但这不意味着其中的任何一种线索化之后就可以直接求得任何一个结点的前驱或后继。
这个题目只要假设一个简单的例子，写出三种方式的遍历就可以知道答案了。

答案与分析

⑦树(一般的)和森林的遍历：根据前辈们的探索发现树的“孩子兄弟存储结构”方便将树转换成二叉树后进行遍历。

树转化成二叉树方法：

加虚线其实就是要形成“孩子兄弟存储”关系。转换成二叉树之后对树的遍历就变成对二叉树进行遍历了。树的遍历分为先根遍历和后根遍历，对应转换成二叉树的先序遍历和中序遍历。原理不再累述。

森林转化成二叉树方法：

森林的遍历分为先序遍历和中序遍历，分别对应二叉树的先序遍历和中序遍历。

⑧赫夫曼树：又叫最优树，带权路径长度最短的树，我们常说的赫夫曼树是叫最优二叉树，其实它不单单指二叉树，可以是多叉树，比如度为m的赫夫曼树，叫最优m叉树(严格m叉树)。若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为：[(n-1)/(m-1)]。对于最优二叉树，叶结点个数为n时，非叶子结点个数为：n-1。

应用场合：例如我们有5个仓库，距离生产车间有些比较近有些比较远，如果生产一种产品需要5个仓库中的材料，但是用量有些明显要比较多，这时候我们就会想到把用量最大的材料放在距离生产车间最近的那个仓库，以此类推下去，这样就可以最节省路费了。赫夫曼树就是可以实现这样的“效果”。

构造赫夫曼树的步骤：

一定要注意的就是：新产生的权值和已有的权值中最小的权值之和大于权值集合中其他两个权值的和时，需要“另起炉灶”，把这集合中最小的两个权值作为新的起点，和原来的并列生长。

三、经典例题

题目1.使用一种遍历方法实现交换二叉树中所有结点的左右孩子的位置。

分析1.“交换”这种操作的实质就是把结点的左右指针域的指向交换，这个工作在访问结点时完成。使用后序遍历就再好不过了。