6.5线索二叉树
6.5.1 线索二叉树的基本概念
在线索二叉树中，为了正确区分指向左右孩子的指针和指向前驱后驱的指针，将结点结构改为5个域，原二又链表中的左孩子域、数据域和右孩子域依战保持不变,增加左标志域Ltag和右标志域它们是两个布尔型的数据城。
线索二叉树的结点结构如下 ：
LChild Ltag Data Rtarg RChild
①若结点有左子树,则LChild城仍指向其左孩子；否则，LChild域指向其遍历序列中的直接前驱结点
②若结点有右子树,则RChild域仍指向其右孩子；否则，RChild域指向其遍历序列中的直接后继结点
③ Lag和Rtag的定义如下:
{ 0 LChild域指示结点的左孩子 Ltag = { { 1 LChild域指示结点的遍历前驱 { 0 RChild域指示结点的右孩子 Rtag = { { 1 RChid域指示结点的遍历后继
在上述存储结构中,指向前驱和后继结点的指针称为“线索”,对二叉树以某种次序进行遍历并且将空指针改为线索的过程叫做“线索化”,经过线索化的一叉树称为“线索二叉树”;以上述结点结构存储的含有线索的二叉链表称为“线索链表”
依据二叉树遍历策略的不同,存在三种不同的线索二叉树。依据二叉树的先序、中序、后序 遍历策略,分别对应有先序线索二叉树、中序线索二叉树和后序线索二叉树。
6.5.2 二叉树的线索化
略
6.5.3 线索二叉树的遍历
略
6.6 树和森林
6.6.1 树的存储
1.双亲表示法
双亲表示法的存储结构定义如下。
define MAX 100 typedef struct TNode{ /*顺序表结点结构定义。/ DataType data; int parent; }TNode; typedef struct{ /*树的定义*/ TNode tree[MAX]; int root; /*树的根结点在表中的位置*/ int num; /*树的结点个数*/ }PTree;
2.孩子表示法
孩子表示法的存储结构定义如下。
typedef struct ChildNode{ //孩子链表结点结构定义 int Child; Struct ChildNode * next; }ChildNode; typedef struct{ //顺序表结点结构定义 DataType data; ChildNode w FirstChild; | DataNode; typedef struct{ //树的定义 DataNode nodes[ MAX]; int root; //树的根结点在顺序表中的位置 int num; //树的结点个数 | CTree;
3.孩子兄弟表示法
孩子兄弟表示法的存储结构定义如下。
typedef struet CSNode{ DataType data; /*结点信息*/ Struct CSNode * FirstChild; /*第一个孩子指针*/ Struct CSNode * NextSibling; /*右兄弟指针*/ }CSNode.* CSTree;
6.6.2 树、森林与二叉树的转换
略
6.6.3 树和森林的遍历
| 二叉树 | 树 | 森林 |
| 先序 | 先根 | 先序 |
| 中序 | 后根 | 中序 |
| 中序 | \ | 中序 |
6.7哈夫曼树及其应用
哈夫曼(Hufman)树,又称最优二叉树,是带权路径长度最短的树，来构造最优编码,用于信息传输、数据压缩等方面,是一种应用广泛的二叉树。
6.7.1哈夫曼树
在介绍哈夫量树之前,先介绍几个与哈夫曼树相关的基本概念
路径;树中个结点到另一个结点之间的分支序列构成两个结点间的路径,
路径长度:路径上分支的条数称为“路径长度”。
树的路径长度:从树根到每个结点的路径长度之和称为“树的路径长度”。
6.3节介绍的完全二叉树,是结点数给定的情况下路径长度最短的二叉树。
带权路径长度:结点到树根间的路径长度与结点的权的乘积,称为该结点的“带机
结点的权:给树中结点赋予一个数值,该数值称为“结点的权”。
树的带权路径长度:树中所有叶子结点的带权路径长度之和,称为“树的带权路径长度"，常记为WPL:
WPL = ∑nk=1 Wkx,Lk
其中,n为叶子数,Wk为第k个叶子的权值,Lk为第k个叶子到树根的路径长度。
最优二叉树:在叶子个数n以及各叶子的权值W,确定的条件下,树的带权路径长度W 最小的二叉树称为“最优二叉树”。
1.哈夫曼树的建立
略
2.哈夫曼算法的实现
相关代码请看配套资源
int main(){ HuffmanTree ht; int w[6]={0,5,7,3,2,8}; int n=5; CrHuffmanTree(ht,w,n); int m=2*n-1; int i; printf("输出哈夫曼树\n"); for (i=1;i<=m;i++){ printf("%d %d %d %d\n",ht[i].Weight,ht[i].Parent,ht[i].Lchild,ht[i].Rchild); } HuffmanCode hc; CrtHuffmanCode1(ht,hc,n); printf("输出哈夫曼编码\n"); for (i=1;i<=n;i++){ printf("%d:",ht[i].Weight); char * cd=hc[i]; puts(cd); } /* 5--01 7--10 3--001 2--000 8--11 */ char str[13]={'0','1','1','0','0','0','1','0','0','0','1','1'}; printf("输出译码\n"); decondind(ht,str,n); }
运行结果如下
6.7.2哈夫曼编译码
1.哈夫曼编码的概念
信息压缩达到最短的前缀编码
2.哈夫曼编码的算法实现
相关代码请看配套资源
运行结果如下
3.哈夫曼编码的译码
相关代码请看配套资源
运行结果如下
数据结构C 语言哈夫曼编译码基本实现 haffman.c 完整代码中有
6.8 实例分析与实现
6.8.1表达式树
略
6.8.2树与等价类的划分
略
6.8.3回溯法与N皇后问题
略
上机实验【数据结构】
6.9 算法总结
略
习题
1.单项选择题
(1)树最适合用来表示的结构是B。
A.元素间的有序结构
B.元素间具有分支及层次关系的结构
C.元素间的无序结构
D.元素间无联系的结构
(2)设一棵二叉树的结点个数为18,则它的高度至少为B
A.4
B.5
C.6
D.18
(3)任意一棵二叉树的叶子结点在其先序、中序、后序序列中的相对位置C
A.肯定发生变化
B.有时发生变化
C.肯定不发生变化
D.无法确定
4)判断线索二叉树中某结点P有左孩子的条件是C
A. p!=NULL
B.p->lchild!=NULL
C.p->LTag=0
D.p->LTag=1
(5)二叉树在线索化后,仍不能有效求解的问题是C
A.先序线索二叉树中求后继
B.中序线索二叉树中求后继
C.中序线索二叉树中求前驱
D.后序线索二叉树中求后继
(6)设森林T中有4棵树,其结点个数分别为n、nz、ng、ng,那么当森林T转换成一棵二叉树后,则根结点 的右子树上有 D 个结点。
A.n1-1
B.n1
C.n1+n2+n3
D.n2+n3+n4
(7)由权值分别为925.7的4个叶子结点构造一棵哈夫曼树,则该树的带权路径长度WPL为C
A.23
B.37
C.44
D.46
(8)设T是一棵哈夫曼树,有8个叶结点,则树T的高度最高可以是C
A.4
B.6
C.8
D.10
3.完成题
3完成题
(1)已知一棵二叉树的后序序列为ABCDEFG,中序序列为ACBCEDF。试完成下列操作。
①画出该二叉树的树形图。
G(C(A,B),F(E(^,D),^))
②给出该二叉树的先序序列。
GCABFED
③画出该二叉树的顺序存储结构示意图。
0 1 2 3 4 5 6 ... 13 ... G C F A B E D
(2)已知一棵树的双亲表示法如下所示,试完成下列操作。
①画出该树的树形图。
A---------------------------------- B---------------------------------- E---------------------------------- K-------------------------- F---------------------------------- C-------------------------- M-------------------------- C-------------------------- G-------------------------- N-------------------------- H-------------------------- O-------------------------- D-------------------------- I-------------------------- J--------------------------
②画出该树的孩子兄弟二叉链表存储结构示意图。
A B ^ E C K F G D ^ ^ C ^ N H I ^ ^ M ^ ^ O ^ ^ J ^ ^ ^ ^
③画出对应二叉树的中序线索二叉树。
中序：KELMFBNGOHCIJDA
(3)假设某通信报文的字符集由A、B、C、D、E、F共6个字符组成,它们在报文中出现的次数分别为16、12、9、30、3、6。试构造一棵哈夫曼树,并完成如下操作。
（76） 30 （46） （18） （28） （9） 9 12 16 3 6
①计算哈夫曼树的带权路径长度。
177
②写出各叶子结点对应字符的哈夫曼编码。
A B C D E F 111 110 101 0 1000 1001
4.算法设计题
（1）编写算法,在以二叉链表存储的二叉树中,求度为2的结点的个数。
int Node2(BiTree T){ if(!T){ return 0; }else if(T->LChild&&T->RChild){ return Node2(T->LChild)+Node2(T->RChild)+1; }else{ return Node2(T->LChild)+Node2(T->RChild); } }
（2）编写算法,在以二叉链表存储的二叉树中,交换二叉树各结点的左右子树。
struct TreeNode* invertTree(struct TreeNode *root){ struct TreeNode* temp=NULL; if(root==NULL){ return NULL; } temp=root->left; root->left=root->right; root->right=temp; invertTree(root->left); invertTree(root->right); return root; }
