大话数据结构--树

串

• 总目录
• 前言
• 六、树
• 6.1 树的定义

• 6.1.1基本术语
• 6.1.2结点间的关系
• 6.1.3树的其他相关概念

• 6.2树的抽象数据类型
• 6.3树的存储结构

• 6.3.1双亲表示法
• 6.3.2孩子表示法
• 6.3.3孩子兄弟表示法

• 6.4 二叉树的定义

• 6.4.1 二叉树特点
• 6.4.2 特殊二叉树

• 1.斜树
• 2.满二叉树
• 3.完全二叉树

• 6.5 二叉树的性质
• 6.5.1二叉树性质
• 6.6 二叉树的存储结构

• 6.6.1二叉树的顺序存储
• 6.6.2 二叉链表

• 6.7遍历二叉树

• 6.7.1 二叉树遍历原理
• 6.7.2二叉树的遍历方法

• 1.前序遍历
• 2.中序遍历
• 3.后序遍历
• 4.层序遍历

• 6.7.3前序遍历算法
• 6.7.4中序遍历算法
• 6.7.5后序遍历算法
• 6.7.6推导遍历结果

• 6.8二叉树的建立
• 6.9线索二叉树

• 6.9.1线索二叉树原理
• 6.9.2线索二叉树结构实现

• 6.10树、森林与二叉树的转换

• 6.10.1树转换为二叉树
• 6.10.2森林转换为二叉树
• 6.10.3二叉树转换为树
• 6.10.4 二叉树转换为森林
• 6.10.5树与森林的遍历

• 6.11哈夫曼树及其应用

• 6.11.1哈夫曼树的基本概念

• 路径长度
• 权
• 结点的带权路径长度
• 树的带权路径长度
• 哈夫曼树:最优树
• 哈夫曼树:最优二叉树

• 6.11.2哈夫曼树的构造
• 6.11.3哈夫曼编码

• 6.12总结

• （1）概念回顾
• （2）遍历的方式
• （3）树、森林
• （4）二叉树的应用

总目录

​​一、数据结构概述​​二、算法概述
三、线性表
四、栈与队列
五、串
六、树
七、图
八、查找
九、排序

​​数据结构与算法基础（青岛大学-王卓）​​

前言

​

提升编程基础能力
数据结构、操作系统、计租、网络
陆续会慢慢更新！

资料获取

六、树

6.1 树的定义

**树(Tree)是n (n≥0)个结点的有限集。n=0时称为空树。**在任意一棵非空，树中:

(1) 有且仅有一个特定的称为根(Root) 的结点;

(2) 当n>1时，其余结点可分为m (m>0)个互不相交的有限集T1、 T2、… Tn, 其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。

树的定义其实就是我们在讲解栈时提到的递归的方法。也就是在树的定义之中还用到了栈的概念，这是一种比较新的定义方法。下图中的子树T1和子树T2就是根结点A的子树。当然，D、G、H、I组成的树又是B为结点的子树，E、J组成的树是C为结点的子树。

对于树的定义还需要强调两点:

1. n>0时根结点是唯一的，不可能存在多个根结点，别和现实中的大树混在一起，现实中的树有很多根须，那是真实的树，数据结构中的树是只能有一个根结点。
2. m>0时，子树的个数没有限制，但它们一定是 互不相交的。像下面的两个结构就不符合树的定义，因为它们都有相交的子树。

下面这张图就是不符合要求的树定义

6.1.1基本术语

根节点：非空树中无前驱结点的结点

结点的度：结点拥有的子树数

树的度：树内各节点的度的最大值

叶子：度为0，没有分支了，也叫终端结点

分支结点：度不为0的点，根结点以外的分支结点称为内部结点

除了根结点以外，其他的结点都称为内部结点

6.1.2结点间的关系

结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。

为啥叫双亲呢？因为就一个结点，对结点来说其父母同体所以只能把它称为双亲

同一个双亲的孩子之间互称兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。所以对于H来说，D、B、A都是它的祖先。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。B的子孙有D、G、H、I

6.1.3树的其他相关概念

结点的层次(Level) 从根开始定义起，根为第一层,根的孩子为第二层。若某结点在第1层，则其子树的根就在第l+1层。**其双亲在同一层的结点互为堂兄弟。**图中D、E、F是堂兄弟，而G、H、I、J也是。

树中结点的最大层次称为树的深度(Depth) 或高度，当前树的深度为4。

如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

森林(Forest) 是m (m≥0)棵互不相交的树的集合

把根节点删除，树就变成了森林

两棵子树其实就可以理解为森林。

给森林中的各子树加上一个双亲结点，森林就变成了树

对比线性表与树的结构，它们有很大的不同

线性结构

第一个数据元素:无前驱

中间元素：一个前驱一 个后继

最后一个数据元素:无后继

树结构

根结点:无双亲，唯一

叶结点:无孩子，可以多个

中间结点:一个双亲多个孩子

6.2树的抽象数据类型

ADT树(tree)
Data
    树是由一个根结点和若干棵子树构成。树中结点具有相同数据类型及层次关系。
Operation
    InitTree (*T) :构造空树T。
    DestroyTree(*T) :销毁树T。
    CreateTree ( *T, definition) :按definition中給出树的定义来构造树。
    ClearTree (*T) :若树T存在，则将树T清为空树。
    TreeEmpty (T) :若T为空树，返回true,否则返回false。
    TreeDepth(T):返回T的深度。
    Root (T) :返回T的根结点。
    Value (T,cur e) : cur_ e是树T中一个结点，返回此结点的值。
    Assign (T, cur_ e,value) :给树T的结点cur_ e赋值为value。
    Parent (T,cur e):若cur_ e是树T的非根结点，则返回它的双亲，否则返回空。
    LeftChild (T,cur_ e) :若cur_ e是树T的非叶结点，则返回它的最左孩子，否则返回空。
    RightSibling (T,cur _e) :若cur_ e有右兄弟，则返回它的右兄弟，否则返回空。
    InsertChild(*T, *p,i,c) :其中p指向树T的某个结点，i为所指结点p的度加上1,
    非空树c与T不相交，操作结果为插入C为树T中p指结点的第i棵子树。
    DeleteChild (*T,*p,i) :其中p指向树T的某个结点，i为所指结点p的度，操作
    结果为删除T中P所指结点的第i棵子树。
endADT

6.3树的存储结构

说到存储结构，就会想到顺序存储和链式存储两种结构。

先来看看顺序存储结构，用一段地址连续的存储单元依次存储线性表的数据元素。这对于线性表来说是很自然的，对于树这样一多对的结构呢?

简单的顺序存储结构是不能满足树的实现要求的。

6.3.1双亲表示法

每个结点，它不一定有孩子，但是一定有且仅有一个双亲。

我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里。

其中data是数据域，存储结点的数据信息。而parent是指针域，存储该结点的双亲在数组中的下标。

代码表示

/*树的双亲表示法结点结构定义*/
#define MAX TREE SIZE 100
typedef int TElemType;  /* 树结点的数据类型，目前暂定为整型*/
typedef struct PTNode   /*结点结构*/
{
    TElemType data; /*结点数据*/
    int parent; /*双亲位置*/
} PTNode ;

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

有了这样的结构定义，我们就可以来实现双亲表示法了。由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1,这也就意味着,我们所有的结点都存有它双亲的位置。

这样的存储结构，我们可以根据结点的parent指针很容易找到它的双亲结点，所用的时间复杂度为O(1),直到parent为-1时，表示找到了树结点的根。可如果我们要知道结点的孩子是什么，对不起，请遍历整个结构才行。

我们只需要进行一点改进，增加一个结点最左边孩子的域,不妨叫它长子域，这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1

对于有0个或1个孩子结点来说，这样的结构是解决了要找结点孩子的问题了。甚至是有2个孩子，知道了长子是谁，另一个当然就是次子了。另外一个问题场景，我们很关注各兄弟之间的关系，双亲表示法无法体现这样的关系，那我们怎么办?嗯，可以增加一个右兄弟域来体现兄弟关系，也就是说，每一个结点如果它存在右兄弟，则记录下右兄弟的下标。同样的，如果右兄弟不存在，则赋值为-1

但如果结点的孩子很多，超过了2个。我们又关注结点的双亲、又关注结点的孩子、还关注结点的兄弟，而且对时间遍历要求还比较高，那么我们还可以把此结构扩展为有双亲域、长子域、再有右兄弟域。存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理，取决于基于该存储结构的运算是否适合、是否方便，时间复杂度好不好等。注意也不是越多越好，有需要时再设计相应的结构。就像再好听的音乐，不停反复听上千遍也会腻味，再好看的电影，一段时间反复看上百遍，也会无趣，你们说是吧?

牛！！！多读几遍就能看懂了！

6.3.2孩子表示法

换一种完全不同的考虑方法。由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每**个指针指向一棵子树的根结点,我们把这种方法叫做多重链表表示法。**不过，树的每个结点的度，也就是它的孩子个数是不同的。所以可以设计两种方案来解决。

方案一：

一种是指针域的个数就等于树的度，复习一下，树的度是树各个结点度的最大值

[data|child|child1|…|childn]

其中data是数据域，child1到childn是指针域，用来指向该结点的孩子结点

用图来说明一下吧

这种方法显然是很浪费空间的，因为有很多结点，它的指针域都是空的

第二种方案

每个结点指针域的个数等于该结点的度，专门取一个位置来存储结点指针域的个数

如下

data为数据域，degree为度域，也就是存储该结点的孩子结点的个数，child1到childn为指针域，指向该结点的各个孩子的结点

实现如图所示

这种方法克服了浪费空间的缺点，对空间利用率提高了很多，但是各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗

能不能有既可以减少空指针的浪费又能使结点结构相同。

我们为了要便利整棵树，把每个结点放到一个顺序存储结构的数组中是合理的，但，每个结点的孩子有多少是不确定的，所以我们再对每个结点的孩子建立一个单链表来体现它们的关系

这就是孩子表示法。具体办法是，把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中

如下图：

图中：

data firstchild是表示表头结点，其中data是数据域，存储某结点的数据信息。firstchild是头指针域，存储该结点的孩子链表的头指针

child next中child是数据域，用来存储某个结点在表头数组中的下标。next是指针域，用来指向某结点的下一个孩子结点的指针

代码实现如下：

/*树的孩子表示法结构定义*/
#define MAX TREE SIZE 100
typedef struct CTNode/* 孩子结点*/
{
    int child;
    struct CTNode *next;
}
typedef struct  //表头结构
{
    TelemType data;
    ChildPty firstchild;
}CTBox;

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

**这样的结构对于我们要查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。**对于遍历整棵树也是很方便的，对头结点的数组循环即可。

6.3.3孩子兄弟表示法

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

如图

其中data是数据域，firstchild 为指针域，存储该结点的第一个孩子结点的存储地址，rightsib 是指针域，存储该结点的右兄弟结点的存储地址。

代码实现：

/*树的孩子兄弟表示法结构定义*/
typedef struct CSNode
{
TElemType data;
struct CSNodeZ* firstchild, *rightsib;
} CSNode, *CSTree;

实现效果：

这种表示法，给查找某个结点的某个孩子带来了方便

通过fistchild 找到此结点的长子，

然后再通过长子结点的rightsib 找到它的二弟，

接着一直下去，直到找到具体的孩子。

当然，如果想找某个结点的双亲，这个表示法也是有缺陷的

在来个指针就可以了对吧！~~

上述这种孩子兄弟表示法最大的好处是它把一颗复杂的树变成了一颗二叉树

如下所示

好，开始学二叉树喽~~~

6.4 二叉树的定义

二叉树( Binary Tree) 是n(n≥0)个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的叉树组成。

看一个不是二叉树的情况

D结点不满足二叉树，因为它有三个子树

6.4.1 二叉树特点

1.每个结点最多有两颗子树，所以二叉树中不存在大于2的结点。不是只有两颗子树，而是最多有。没有子树或者一颗子树的也是可以的！

2.左子树和右子树是有顺序的，次序不能任意颠倒

3.即使树中某结点只有一棵子树，也要区分它是左子树还是右子树

二叉树具有五种基本形态:

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

5个结点的树有5中二叉树的形态

6.4.2 特殊二叉树

1.斜树

顾名思义，斜树一定要是斜的，但是往哪斜还是有讲究。所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树

上面的树2就是左斜树，树5就是右斜树

其实线性表结构就可以理解为是树的一种极其特殊的表现形式

2.满二叉树

人有悲欢离合，月有阴晴圆缺，此事古难全

理想是完美的，不完美才是人生

完美的二叉树就叫满二叉树

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

满二叉树的特点有：

(1)叶子只能出现在最下一-层。出现在其他层就不可能达成平衡。
(2)非叶子结点的度一-定是2。否则就是“缺胳膊少腿”了。
(3)在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

3.完全二叉树

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

满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树

只能最后一层右边缺，其他地方缺都必须是连续的，不连续就不是完全二叉树

如下图所示

完全二叉树的特点：

1.叶子结点只能出现在最下两层

2.最下层的叶子一定集中在左部连续位置

3.倒数二层，若有叶子结点，一定都在右部连续位置。

4.如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况

5.同样结点数的二叉树，完全二叉树的深度最小

6.5 二叉树的性质

6.5.1二叉树性质

性质1:在二叉树的第i层上至多有2^（i-1）个结点(i≥1)。(带入即可理解)

性质2:深度为k的二叉树至多有2^k - 1个结点(k>1)。

如果有一层，至多有1 = 2 的 0次方 - 1 个结点

如果有二层，至多有1 + 2 = 3 = 2 的平方 - 1 个结点

…

性质3:对任何一棵二叉树T,如果其终端结点数为No,度为2的结点数为n2,则No = N2 + 1

性质4:具有n个结点的完全二叉树的深度为[log2n]+1 (Lx]表示不大于x的最大整数)。

这个其实就是性质二的倒数，反过来求k的值的

性质5:如果对一棵有n个结点的完全二叉树(其深度为log2n]+1) 的结点按层序编号(从第1层到第log2n]+1层，每层从左到右)，对任一结点i (1≤i≤n)
有:

1.如果i=1，则结点i是二叉树的根，无双亲;如果i>1,则其双亲是结点li/2」。

2.如果2i>n，则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i。

3.如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1。

如下图

对于第一条来说是很显然的，i=1 时就是根结点。i>1 时，比如结点7,它的双亲就是l7/2]=3,结点9,它的双亲就是[9/2]=4

第二条，比如结点6,因为2X6=12超过了结点总数10,所以结点6无左孩子，它是叶子结点。同样，而结点5,因为2X5=10正好是结点总数10,所以它的左孩子是结点10

第三条，比如结点5,因为2X5+1=11,大于结点总数10,所以它无右孩子。而结点3，因为2X3+1=7小于10,所以它的右孩子是结点7

6.6 二叉树的存储结构

6.6.1二叉树的顺序存储

如果有一颗深度为k的右斜树，它有k个结点，却要分配2的k次方减1个存储单元，他会很浪费如下图，所以顺序存储结构一般用于完全二叉树

6.6.2 二叉链表

既然顺序存储适用性不强，我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表

结构如图所示：

代码实现如下：

/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode /* 结点结构*/
{
  TElemType data;   /*结点数据*/
  struct BiTNode *1child, *rchild; /*左右孩子指针*/
} BiTNode, *BiTree;

结构下图：

如果有需要，还可以增加一个指向其双亲的指针域，那样就称之为三叉链表，很灵活要学会自己变通~~~~

6.7遍历二叉树

6.7.1 二叉树遍历原理

二叉树的遍历( traversing binary tree )是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

访问和次序是关键！

6.7.2二叉树的遍历方法

1.前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树,再前序遍历右子树。如下图所示，遍历的顺序为: ABDGHCEIF。

2.中序遍历

规则是若树为空，则空操作返回，否则**从根结点开始(注意并不是先访问根结点)，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。**如图所示、谝历的顺序为: GDHBAEICF。

3.后序遍历

规则是若树为空，则空操作返回，否则**从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。**如图所示，遍历的顺序为: GHDBIEFCA.

4.层序遍历

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

6.7.3前序遍历算法

二叉树的定义是递归的方式，所以实现算法也可以递归

/*二叉树的前序遍历递归算法*/
void PreOrderTraverse ( BiTree T )
{
    if( T==NULL)
        return;
    printf ( "&c",T->data) ;/*显示结点数据，可以更改为其他对结点操作*/
    PreOrderTraverse (T->lchild) ; /*先序遍历左子树*/
    PreOrderTraverse (T->rchild) ; /*最后先序遍历右子树*/
}

可以简单的看个例子

一颗这样的二叉树T，如果要遍历它的话

1.调用PreOrderTraverse (T), T根结点不为null, 所以执行printf, 打印字母A

2.调用PreOrderTraverse (T->lchild) ;访问了A结点的左孩子，不为null,执行
printf显示字母B

3.不断的递归调用PreOrderTraverse (T->lchild)到H，此时为H结点无左孩子，所以T==null, 返回此函数，此时递归调用PreOrderTraverse (T->rchild) ;访问了H结点的右孩子，printf 显示字母K,

后面的话会不断的向前向左向右遍历

6.7.4中序遍历算法

/*二叉树的前序遍历递归算法*/
void PreOrderTraverse ( BiTree T )
{
    if( T==NULL)
        return;
    
    InOrderTraverse (T->lchild) ; /*中遍历左子树*/
    printf ( "&c",T->data) ;/*显示结点数据，可以更改为其他对结点操作*/

    InOrderTraverse (T->rchild) ; /*最后中序遍历右子树*/
}

流传和上类似，都是不断的递归

6.7.5后序遍历算法

/*二叉树的前序遍历递归算法*/
void PreOrderTraverse ( BiTree T )
{
    if( T==NULL)
        return;
    
    InOrderTraverse (T->lchild) ; /*中遍历左子树*/
    InOrderTraverse (T->rchild) ; /*最后中序遍历右子树*/
    printf ( "&c",T->data) ;/*显示结点数据，可以更改为其他对结点操作*/
}

6.7.6推导遍历结果

已知一棵二叉树的前序遍历序列为ABCDEF,中序遍历序列为CBAEDF，请问这棵二叉树的后序遍历结果是多少?（已知前中求后）

前序遍历是先打印在递归左跟右，所以前序遍历序列为ABCDEF，A就位根结点的数据。再由中序遍历序列CBAEDF可以CB是A的左子树，EDF是A的右子树

然后我们看前序中的C和B,它的顺序是ABCDEF,是先打印B后打印C,所以B应该是A的左孩子，而C就只能是B的孩子,此时是左还是右孩子还不确定。再看中序序列是CBAEDF, C是在B的前面打印，这就说明C是B的左孩子，否则就是右孩子了

再看前序中的E、D、F,它的顺序是ABCDEF,那就意味着D是A结点的右孩子，E和F是D的子孙，注意，它们中有一个不一定是孩子，还有可能是孙子的。再来看中序序列是CBAEDF，由于E在D的左侧，而F在右侧，所以可以确定E是D的左孩子，F是D的右孩子。因此最终得到的二叉树

得到了二叉树，结果就是CBDEFDA

为刚才判断了A结点是根结点，那么它在后序序列中，一定是最后一个。刚才推导出C是B的左孩子，而B是A的左孩子，那就意味着后序序列的前两位一定是CB。同样的办法也可以得到EFD这样的后序顺序，最终就自然的得到CBEFDA这样的序列，不用在草稿上画树状图了。

​ 反过来**，二叉树的中序序列是ABCDEFG,后序序列是**
BDCAFGE,求前序序列。（已知中后求前）

由后序的BDCAFGE,得到E是根结点，因此前序首字母是E

于是根据中序序列分为两棵树ABCD和FG,由后序序列的BDCAFGE,知道A是E的左孩子，前序序列目前分析为EA

再由中序序列的ABCDEFG, 知道BCD是A结点的右子孙，再由后序序列的BDCAFGE知道C结点是A结点的右孩子，前序序列目前分析得到EAC。

中序序列ABCDEFG,得到B是C的左孩子，D是C的右孩子,所以前序序列目前分析结果为EACBD。

由后序序列BDCAFGE,得到G是E的右孩子，于是F就是G的孩子，细细分析，根据中序序列ABCDEFG,是可以得出F是G的左孩子。

从这里我们也得到两个二叉树遍历的性质。

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

要注意的是，如果已知前序和后序遍历，是不能确定一颗二叉树的

6.8二叉树的建立

在内存中建立好一颗二叉树我们才能进行遍历

所以，如果我们要在内存中建立一个二叉树

我们建立一个扩展二叉树，什么是扩展二叉树，就是在给普通二叉树的每个结点的空指针引出一个虚结点，并给它赋值（#）

如图所示：

代码实现：

/*按前序输入二叉树中结点的值(一个字符)*//* #表示空树，构造二叉链表表示二叉树T。*/void CreateBiTree (BiTree *T ){    TElemType ch;    scanf ( "%c",&ch) ;    if (ch=='#')      *T=NULL;    else    {   *T= (BiTree) malloc (sizeof(BiTNode)) ;   if(!*T)     exit (OVERFLOW) ;   (*T)->data=ch; /*生成根结点   CreateBiTree (&(*T)->1child);  /*构造左子树*/   CreateBiTree (&(*T)->rchild) ; /*构造右子树*/    }}

6.9线索二叉树

6.9.1线索二叉树原理

为了解决空指针占用内存的问题，把这些空指针的位置利用起来，指向前驱和后继的，它们称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树

我们对二叉树以某种线索遍历使其变为线索二叉树的过程称作是线索化

为了更好的区分，我们这样定义结点的结构

其中:

ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。
rtag为0时指向该结点的右孩子，为1时指向该结点的后继。

如下：

6.9.2线索二叉树结构实现

/*二叉树的二叉线索存储结构定义*/typedef enum {Link, Thread} PointerTag; /* Link=-0 表示指向左右孩子指针*/                   /* Thread==1 表示指向前驱或后继的线索*/typedef struct BiThrNode   /*二叉线索存储结点结构*/{     TElemType data;   /*结点数据*/    struct BiThrNode *lchild, *rchild;  /*左右孩子指针*/    PointerTag LTag;    PointerTag RTag;    /*左右标志*/} BiThrNode, *BiThrTree;

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

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

6.10树、森林与二叉树的转换

树的孩子兄弟法可以将一棵树用二叉链表进行存储，借助儿茶链表，树和二叉树可以相互进行转换。因此，只要我们设定一-定的规则， 用二叉树来表示树，甚至表示森林都是可以的，森林与二叉树也可以互相进行转换。

6.10.1树转换为二叉树

将树转换为二叉树的步骤如下

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

注意点：第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子

实例如图：

其中一棵树经过三个步骤转换为一棵二叉树。图中F、G本都是树结点B的孩子，是结点E的兄弟，因此转换后，F就是二叉树结点E的右孩子，G是二叉树结点F的右孩子。

6.10.2森林转换为二叉树

森林是由若干棵树组成的，所以完全可以理解为,森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作。步骤如下:

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

实例：

6.10.3二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程，就是反过来做

1.加线。若某结点的左孩子结点存在，则将这个左孩子的所有右孩子结点，都与该结点用线连接起来。

2.去线。删除原二叉树中所有结点与其右孩子结点的连线。

3.层次调整。使之结构层次分明。

实例如下：

6.10.4 二叉树转换为森林

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

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

实例如下：

6.10.5树与森林的遍历

树的遍历分为两种方式

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

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

先根遍历为ABCDEFG

后根遍历序列为EFBCGDA

森林的遍历也分为两种方式

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

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

实例

前序遍历结果为ABCDEDGHJI

后序遍历BCDAFEJHIG

6.11哈夫曼树及其应用

将大文档进行压缩可以将其空间减少，简单来说，就是把我们要压缩的文本进行了重新的编码，以减少不必要的空间

赫夫曼编码 —— 一种最基本的压缩编码方法

6.11.1哈夫曼树的基本概念

路径长度

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

下图中的二叉树a中,根结点到结点D的路径长度就为4

二叉树中根结点到结点D的路径长度为2

树的路径长度就是从树根到每一结点的路径长度之和

二叉树a的树路径长度就为1+1+2+2+3+3+4+4=20

二叉树b的树路径长度就为1+2+3+3+2+1+2+2=16

完全二叉树是路径长度最短的二叉树

权

权(weight):也叫权重，从英文意思即可知道，将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

结点的带权路径长度

从根节点到该节点的路径长度与该节点的权的乘积

树的带权路径长度

树中所有叶子结点的带权路径长度之和。

哈夫曼树:最优树

带权路径长度(WPL)最短的树
"带权路径长度最短”是在"度相同”的树中比较而得的结果，因此有最优二叉树、最优三叉树之称等等。

哈夫曼树:最优二叉树

带权路径长度(WPL)最短的二叉树
因为构造这种树的算法是由哈夫曼教授于1952年提出的，所以被称为哈夫曼树，相应的算法称为哈夫曼算法。

满二叉树不一定是哈夫曼树

具有相同带权结点的哈夫曼树并不唯一

6.11.2哈夫曼树的构造

1.先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列，即: A5,E10，B15，D30， C40。

2.取头两个最小权值的结点作为一个新节点N1的两个子结点，注意相对较小的是左孩子，这里就是A为N1的左孩子，E为N1的右孩子，新结点的权值为两个叶子权值的和5+10=15。

3.将N1当做A与E,插入有序序列中，保持从小到大排列。即: N15, B15

4.重复步骤2。将N1与B作为一个新节点N2的两个子结点N2的权值=15+15=30

5.将N2当做N1与B,插入有序序列中，保持从小到大排列。即: N230，D30，C40

6.重复步骤2。将N2与D作为一个新节点N3的两个子结点。N3的权值=30+30=60

7.将N3当做N2与D,插入有序序列中，保持从小到大排列。即: C40，N360

8.重复步骤2。将C与N3作为一个新节点T的两个子结点由于T即是根结点,完成赫夫曼树的构造。

二叉树的带权路径长度WPL=40x1+30x2+15x3+10x4+5x4=205。与上面的二叉树b的WPL值220相比，还少了15。显然此时构造出来的二叉树才是最优的赫夫曼树。

6.11.3哈夫曼编码

哈夫曼树的左分支代表0，右分支代表1，从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，这就是哈夫曼编码

例题如下：

思路如下：

1、要传输的字符集D = {C，A，S，T，；}

字符出现的频率 w = {2,4,2,3,3}

2、把他们出现的频率作为权重，权重大的离根节点近，小的相反进行构造带权二叉树

3、用哈夫曼编码的思想左分支代表0，右分支代表1，每个子节点都是如此

4、最后从根节点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码

6.12总结

知识点好多啊，连续写了两天

（1）概念回顾

最开始有树的定义，讲到了递归在树定义中的应用。

还有很多概念如：

子树、结点、度、叶子、分支结点、双亲、孩子、层次、深度、森林…理解记忆！！！

在写一遍易忘的概念：

**度：结点所拥有的子树的个数称为该结点的度(Degree); **

树中各结点度的最大值称为该树的度； 称度为m的树为m叉树。

深度：深度是指所有结点中最深的结点所在的层数。

层次：一个结点的层次直观上来说就是其所在的行，其中根结点层次为1（第一行），其子结点层次为2（第二行），以此类推，第1行的结点为1。

森林，指的是由 n（n>=2）棵互不相交的树组成的集合

（2）遍历的方式

遍历是二叉树最重要的一门学问，前序、中序、后序以及层序遍历不过

递归的实现比较高级！

（3）树、森林

树、森林看似复杂，其实它们都可以转化为简单的二叉树来处理，我们提供了树、森林与二叉树的互相转换的办法，这样就使得面对树和森林的数据结构时，编码实现成为了可能。

（4）二叉树的应用

哈夫曼树和哈夫曼编码

哈夫曼树也就是带权路径的二叉树