数据结构讲义

2022/12/131柳青Email:SchoolofSoftware,YunnanUniversity数据结构(DataStructure)2022/12/132

6.1树的定义和基本术语

6.2二叉树

6.3遍历二叉树和线索二叉树

6.4树和森林

6.5赫夫曼树及其与树的应用第六章树和二叉树6.1树的定义和基本术语线性结构和非线性结构同属于数据结构中的逻辑结构类型线性结构是指该结构中的节点之间存在一对一的关系。其特点是开始节点和终端节点都是唯一的,除了开始节点和终端节点外,其余节点都有且仅有一个直接前驱,有且仅有一个直接后继。此类型的存储结构有：顺序表（数组）、链表、堆栈结构、队列结构等非线性结构的特点是数据元素之间存在一个对多个或多个对多个的关系

包括集合、树形结构、图形结构或网状结构2022/12/1336.1树的定义和基本术语树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。直观角度看，树是以分支关系定义的层次结构。树在计算机领域中得到广泛应用，如文件管理中的目录结构、数据库系统中的信息组织形式等。树结构在客观世界中也广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。2022/12/1346.1树的定义和基本术语到目前为止，我们已经介绍了线性数据结构和表数据结构。这些数据结构一般不适合于描述具有层次结构的数据。在层次化的数据之间可能有祖先-后代、上级-下属、整体-部分以及其他类似的关系。例1[Joe的后代]：上图给出了Joe的后代，并按层次方式组织，其中Joe在最顶层。Joe的孩子（Ann，Mark和John）列在下一层，在父母和孩子间有一条边。在层次表示中，非常容易地找到Ann的兄弟姐妹，Joe的后代，Chris（克里斯）的祖先等。2022/12/1356.1树的定义和基本术语例2：学校的组织结构2022/12/136软件学院教务科院办数字媒体系信息安全系网络工程系实验中心软件工程系研究所后勤处大数据计算室人工智能室娱乐计算室2022/12/1376.1树的定义和基本术语树的定义树是由n(n0)个结点组成的有限集合。如果n=0，称为空树。如果n>0，则

有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；

除根以外的其它结点划分为m(m0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。ABCEFGHIJKLMD2022/12/138ABCEFGHIJKLMDROOTSUBTREE1SUBTREE2SUBTREE36.1树的定义和基本术语2022/12/139结点(node)：包含一个数据元素及指向其子树的分支。结点的度(degree)：结点拥有的子树的个数。树的度(degree)：树中结点的度的最大值。叶子(leaf)结点：度为0的结点。子(child)结点：结点的子树的根。分支(branch)结点：度不为0的结点。6.1树的定义和基本术语6.1树的定义和基本术语2022/12/13102022/12/13116.1树的定义和基本术语双亲(parent)结点：子结点的直接前驱结点。兄弟(sibling)结点：同一双亲的子结点互称兄弟结点。结点的层次(level)：根为第一层；子结点的层次比双亲结点的层次加1。树的深度(depth)：树中结点的最大层次。有序树：子树从左到右有序。无序树：子树无序。森林(forest)：m（m>=0）棵互不相交的树的集合。6.1树的定义和基本术语兄弟（sibling）

如图B、C、D的双亲结点（父节点）均为A，故B、C、D互为兄弟结点的度（degree）结点的子树个数，称为结点的度。如图，A的度为3，B的度为3，C的度为2，最大的度值为3，故树的深度为3。层次（level）层次为结点之特性值，将根结点之层次设为1，其子结点为2，依此类推。如图，层次为1的有结点A,为2的有结点B、C、D，为3的有结点E、F、G、H、I。2022/12/1312ADCBEFGHI6.1树的定义和基本术语如果表示同一棵树，这就叫无序树;如果表示两棵不同的树，就叫有序树。关键在于结点的位置是否对树的构成有关。若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树；否则称为无序树(UnorderedTree)。注意：若不特别指明，一般讨论的树都是有序树。2022/12/1313AABCDBDC6.1树的定义和基本术语祖先（ancestor）

由某结点X到根结点之路径上的所有结点，均称为X之祖先树林（forest）n>=0个树的集合称为树林

若将一树的根结点移去，所剩这恰是一树林.2022/12/1314ADCBEFGHIDCBEFGHIA6.1树的定义和基本术语例1：一般的树1.此树Tree-A共有13个结点,是由三棵子树组成：Tree-B(T1)={B，E，F，K，L}Tree-C(T2)={C，G}Tree-D(T3)={D，H，I，J，M}B、C、D为三棵子树的根，且互不相交2.T1又分为两个互不相交的Tree-E(T11)={E，K，L}和Tree-F(T12)={F}T2又分为一个树Tree-G(T21)={G}T3又分为三棵互不相交的Tree-H(T31)={H，M}Tree-I(T32)={I}和Tree-J(T33)={J}3.T11又分为:Tree-K(T111)和Tree-L(T112)T31又分为:Tree-M(T311)2022/12/1315ADCBKGLEFHIJM6.1树的定义和基本术语例2：不是一棵树因为:子树Tree-H={H，M}子树Tree-I={I，M}出现了交叉，违反树的定义。2022/12/1316ADCBKGLEFHIJM2022/12/13176.2二叉树6.2.1

二叉树的定义

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。6.2二叉树2022/12/13186.2二叉树2022/12/1319二叉树的应用——表示家族的血缘关系外曾祖母曾祖父曾祖母曾祖父曾祖母外曾祖母外曾祖父外曾祖父祖父外祖父祖母外祖母父亲母亲男方外曾祖母曾祖父曾祖母曾祖父曾祖母外曾祖母外曾祖父外曾祖父祖父外祖父祖母外祖母父亲母亲女方家庭1家庭2不能有相同结点，否则为近亲结婚！2022/12/1320DCHEFBA1层：结点个数21-1=20

个2层：结点个数22-1=21

个3层：结点个数23-1=22

个6.2.2

二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点证：

1)k=1时成立;只有一个根结点，显然2i-1=20=1是对的。2)设k=i-1时成立;3)则当k=i时，在二叉树的第i层上至多有2i-1-1*2=2i-1个结点；第i-1层上至多有2i-2个结点，由于二叉树的

每个结点度数至多为2，故在第i层上的最大结点数为第i-1

层上的最大结点数的两倍，即2*2i-2=2i-1

原命题成立。6.2二叉树2022/12/1321性质2：深度为K的二叉树至多有2k-1个结点证：利用性质1，将第1层至第k层的最多的结点数进行相加，则：1+2+22+…………+2k-2+2k-1

原命题成立。性质3：二叉树的叶子结点数n0等于度为2的结点数n2+1证：设度为1的结点数为n1，树的分枝总数为B，除根结点外其余结点都有一个分枝进入，则：B=n0+n1+n2-1

又因这些分枝是由度为1和2的结点射出的，故B=n1+2*n2∴n0+n1+n2-1=n1+2*n2∴

n0=n2+1∴

原命题成立。6.2二叉树

2022/12/1322满二叉树：深度为k且有2k-1个结点的二叉树，如下图(a)所示。完全二叉树：如果深度为k、有n个结点的二叉树中每个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树，如下图(b)所示。图(c)、(d)是2棵非完全二叉树。满二叉树是完全二叉树的特例。123456(a)7123456(b)12345(c)61234(d)56.2二叉树完全二叉树所有叶子结点都出现在第k层或k－1层。6.2二叉树2022/12/132312311458912136710141512311458912671012345671234562022/12/1324性质4：具有n个结点的完全二叉树的深度为log2n

＋1。符号x

表示不大于x的最大整数。证：设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－1(上一层最大节点数)<n<=2k-1或2k-1<=n<2k

取对数得到：k－1<=log2n<k

∵

k是整数，∴

k＝log2n

＋1。性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从上到下，从左到右),则对任一结点i（1<=i<=n),有：（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点i/2

。（2）如果2i>n，则结点i无左孩子；否则其左孩子是结点2i(偶数）。（3）如果2i＋1>n，则结点i无右孩子；否则其右孩子是结点2i＋1

。6.2二叉树6.2二叉树2022/12/1325ACBDFEGIHKJL123456789101112对于E，2*5=10<12,其左孩子为10;2*5+1=11<12其右孩子为1对于F，2*6=12=12,其左孩子为12;2*6+1=13>12，没有右孩子对于J，2*10=20>12，为叶子结点2022/12/1326

可以先证明（2）和（3），然后从（2）和（3）推出（1）。证：1.对于i＝1，由完全二叉树的定义，其左孩子是结点2，若2>n，即不存在结点2，此时结点i无孩子。结点i的右孩子也只能是结点3，若结点3不存在，即3>n，此时结点i无右孩子。

2.对于i>1，可分为两种情况：（1）设第j(1<=j<=log2n

)层的第一个结点的编号为i，由二叉树的性质2和定义知i＝2j-1，结点i的左、右孩子必定为第j＋1层的第一、二个结点，其编号为2j＝2*2j-1＝2i和2i+1。如果2i>n，则无左孩子，如果2i+1>n，则无右孩子。（2）假设第j层上的某个结点编号为i(2j-1<=i<=2j-1),且2i＋1<n，其左孩子为2i，右孩子为2i＋1，则编号为i＋1的结点是编号为i的结点的右兄弟或堂兄弟。若它有左孩子，则其编号必定为2i＋2＝2*(i＋1)；若它有右孩子，则其编号必定为2i＋3＝2*(i＋1)＋1。6.2二叉树2022/12/13273.从（2）和（3）推出（1）当i=1时，结点是根，因此无双亲。当i>1时，设其双亲结点编号为p，如果i为左孩子，即i=2p，则p=i/2=i/2；如果i为右孩子，i=2p+1,p=(i-1)/2=i/2

。证毕。6.2二叉树i/2ii+12i2i+12i+22i+3i+12i+22i+3i2i2i+1(a)i和i+1结点在同一层(b)i和i+1结点不在同一层…………2022/12/13286.2.3二叉树的存储结构1.顺序存储结构用一组连续的存储单元存储二叉树的数据元素。必须把二叉树的所有结点按层序编号，结点的序号反映出结点之间的逻辑关系。LKJIHGFEDCBA1234567891011126.2二叉树DCGEFBAHKIJL1211109876543212022/12/1329HØGØØØFEDCBA123456789101112

顺序存储缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为h且只有h个结点的右单支树却需要2h-1个结点存储空间。6.2二叉树DCØEFBAØØØGH121110987654321DCEFBAGH2022/12/1330typedefstructBiTNode{TELemType data;structBiTNode*lchild;structBiTNode*rchild;}BitTNode,*BiTree; 二叉链表2链式存储结构：6.2二叉树datalchildrchildtypedefstructBiTNode{TELemType data;structBiTNode*lchild;structBiTNode*rchild;structBiTNode*parent;}BitTNode,*BiTree; 三叉链表datalchildrchildparent注：在含有n个结点的二叉链表中有n+1个空链域（2*n0+n1)。n0=n2+12*n0+n1=n0+n2+1+n1n=n0+n1+n22022/12/13316.2二叉树2022/12/13326.2二叉树ABDGEFHJIC#defineMAX_SIZE10typedefstructBiTNode{TELemTypedata;intlchild;intrchild;}BitTNode；typedefBiTNodeSqBiTree[MAX_SIZE];datalchildrchild12345678910ABCDEFGHIJ2306008900045700010003静态链式存储结构：

静态链式结构适用于二叉树上的结点个数已知，或不支持动态存储分配的高级语言。练习2022/12/13331．已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（）A．7 B．8

C．9 D．102．若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（）A．10 B．11C．12 D．不确定的已知一棵二叉树的顺序存储序列为：aebфfcd，则：1）e的左孩子是哪个结点？右孩子是哪个结点？2）d的双亲是哪个结点？

答案：B答案：A答案：1）没有左孩子；右孩子是f；2）b；在二叉树的第i层上至多有2i-1个结点26=64K=727=128k=8第七层全部排满（64个节点）

第八层只有一个节点

n0=n2+1练习2022/12/133．假设一棵二叉树的顺序存储结构如图所示，请回答下列问题：（1）哪个结点是根结点？（2）哪些结点是叶子结点？（3）哪些结点是H的祖先？（4）哪些结点是B的兄弟？（5）树的深度是多少？A

BCфDE

ф

ф

ф

ф

ф

фH123456789

1011121314AD,HA,C,EC42022/12/13356.3遍历二叉树和线索二叉树6.3.1

遍历二叉树1

定义：按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且只被访问一次。线性表的遍历（1）顺序表的遍历：

for(i=1;i<=v.last;i++)visit(v.elem[i]);

（2）链表的遍历：

for(p=L->next;p!=NULL;p=p->next)visit(p->data);

二叉树的遍历：非线性关系，需确定先后次序。通常按对根结点的处理次序分为：

先序（DLR）、中序（LDR）、后序（LRD）。DRL根结点左子树右子树cDcLcR根节点（缩写为D，并不是RootNode）与Right区分6.3遍历二叉树和线索二叉树2022/12/1336先序遍历（Preordertraversal）是先遍历根结点，再遍历左子树，最后遍历右子树，若一棵二叉树如右图，则先序遍历的顺序为：DLR,也就是说每当遍历一个结点就先处理该结点，之后先向左方前进，直到无法前进才往右方走。左图中从根结点A开始，先往左子树B再到D，由于D没有左子树，故转向右子树G；再回到B，因为B没有右子树，所以此时A的左子树均遍历完毕，则转向A的右子树，再往左边继续遍历。依此类推，其前序遍历为：ABDGCEHIF。ADCBGEFHIDRL根结点左子树右子树cDcLcRcAcIcHcGcFcEcDcCcB6.3遍历二叉树和线索二叉树2022/12/1337先序遍历二叉树的步骤如下：if二叉树为空then遍历结束else

（1）访问当前结点（2）先序访问左子树（3）先序访问右子树6.3遍历二叉树和线索二叉树2022/12/1338中序遍历（Inordertraversal）是先遍历左子树，再根结点，最后才遍历右子树，若一棵二叉树如右图，则中序遍历的顺序为：LDR，也就是说一开始先往左方前进，直到无法前进才处理结点，之后再往右方前进。ADCBGEFHI左图中从根结点A开始，一直往左走到D无法再前进，则处理D，再往D之右方到G。此时，已遍历完B之左子树，接着处理B，再往B的右方向前进。由于B没有右子树，故A之左子树遍历完毕，再往A之右子树前进。依此类推，其中序遍历为：DGBAHEICF。DRL根结点左子树右子树cDcLcRcAcIcHcGcFcEcDcCcB6.3遍历二叉树和线索二叉树2022/12/1339中序遍历二叉树的步骤如下：if二叉树为空then遍历结束else

（1）中序访问左子树（2）访问当前结点（3）中序访问右子树6.3遍历二叉树和线索二叉树2022/12/1340后序遍历（Postordertraversal）是先遍历左子树，再遍历右子树，最后才遍历根结点，若一棵二叉树如右图，则后序遍历的顺序为：LRD，也就是说一开始先往左方前进，直到无法前进才处再往右方前进，最后才处理结点。左图中从根结点A开始，一直往左走到D无法再前进，则往D之右方前进到G，由于G没有左、右子树，故处理结点G。之后由于D之右子树处理完毕，故进而处理D，而B之左子树也相应完成。且结点B没有右子树，故可接着处理B。此时A之左子树已遍历完毕，再往A之右子树C前进。依此类推，其后序遍历为：GDBHIEFCA。ADCBGEFHIDRL根结点左子树右子树cDcLcRcAcIcHcGcFcEcDcCcB6.3遍历二叉树和线索二叉树2022/12/1341后序遍历二叉树的步骤如下：if二叉树为空then遍历结束else

（1）后序访问左子树（2）后序访问右子树（3）访问当前结点2022/12/1342先序遍历二叉树(DLR)的操作定义:(1)访问根结点;(2)先序遍历左子树(3)先序遍历右子树中序遍历二叉树(LDR)的操作定义:(1)中序遍历左子树;(2)访问根结点;(3)中序遍历右子树;后序遍历二叉树(LRD)的操作定义:(1)后序遍历左子树;(2)后遍历右子树;(3)访问根结点;DCFEBA先序：ABDCEF中序：DBAECF后序：DBEFCA6.3遍历二叉树和线索二叉树6.3遍历二叉树和线索二叉树2022/12/1343

A

B∧E∧∧D∧∧C∧ABCDEACBDCEAABDECEBD先序：ABDEC中序：DBEAC后序：DEBCA练习2022/12/1344ADCBGFIJEH先序：ABDGEHCFIJ中序：DGBEHACIFJ后序：GDHEBIJFCA练习2022/12/1345已知某二叉树的先序序列为:abdgcefh，中序序列为:dgbaechf，求其后序序列先序abdgcefh中序dgbaechfa

bdgcefha

b

dgc

e

fhdgb

aechfabcedgba

e

chf根右根根左左左右根根根右左dfghgdbehfca练习2022/12/1346已知某二叉树的后序序列为:gdbehfca，中序序列为:dgbaechf，求其先序序列后序gdbehfca中序dgbaechfgdbehfc

agd

b

ehf

c

adgb

aechfabcedgba

e

chf根右根根左左左右根根根右左dfghabdgcefh2022/12/1347如右图的二叉树表示表达式：

a+b*(c–

d)–

e/f先序遍历该二叉树得:–+a*b–cd/ef即前缀表示（波兰式）。中序遍历该二叉树得:a+b*c–d–e/f即中缀表示。后序遍历该二叉树得:

abcd–*+ef/–即后缀表示（逆波兰式）。a/fe+－6.3遍历二叉树和线索二叉树dc－b*2022/12/13481

遍历算法（先序）递归算法：voidinorder(BiTreeT){if(T!=NULL)

{printf(T->data);if(T->lchild!=NULL) inorder(T->lchild);if(T->rchild!=NULL) inorder(T->rchild);}}voidinorder(BiTreeT){InitStack(S);p=T;

while (p||!SatckEmpty(S)){if(p){Push(S,p);printf(p->data); p=p->lchild;}else{Pop(S,p); p=p->rchild; }}}非递归算法：6.3遍历二叉树和线索二叉树6.3遍历二叉树和线索二叉树先序堆栈遍历算法思想：1、节点指针非空时，或堆栈非空时，进入下面步骤：如果节点指针非空,首先访问"根"节点,转(2)节点指针为空时，转(3)；

2、然后将访问过得节点指针(一个"根"的指针)进栈，再将指针指向访问过得节点的左子树的根，转(1)；3、堆栈非空时，退栈，指针指向退栈节点的右子树节点，转(1)。节点指针为空且堆栈为空时，结束算法，完成遍历。2022/12/13492022/12/13502

遍历算法（中序）递归算法：voidinorder(BiTreeT){if(T!=NULL)

{if(T->lchild!=NULL) inorder(T->lchild);printf(T->data); if(T->rchild!=NULL) inorder(T->rchild);}}voidinorder(BiTreeT){InitStack(S);p=T;

while (p||!SatckEmpty(S)){if(p){Push(S,p); p=p->lchild;}else{Pop(S,p);printf(p->data); p=p->rchild; }}}非递归算法：6.3遍历二叉树和线索二叉树6.3遍历二叉树和线索二叉树中序堆栈遍历算法思想：

1、首先节点指针(一个"根"的指针)进栈，然后将节点指针指向进栈节点的左子树的根，重复(1)，直到指针指向空(最后一个进栈的是最左子树)，转(2)；2、堆栈非空时，从堆栈中退出一个节点的指针，访问该节点，转(3)，堆栈为空时，结束算法；3、然后将指针指向的访问过的节点的右子树的根，转(1)。2022/12/13512022/12/13523

遍历算法（后序）递归算法：voidinorder(BiTreeT){if(T!=NULL)

{if(T->lchild!=NULL) inorder(T->lchild)if(T->rchild!=NULL) inorder(T->rchild);printf(T->data);}}voidinorder(BiTreeT){InitStack(S);InitStack(Q);p=T;

while (p||!SatckEmpty(S)){if(p){Push(S,p);Push(Q,p); p=p->rchild;}else{Pop(S,p); p=p->lchild; }}while(!SatckEmpty(Q))Pop(Q,p);printf(p->data);}非递归算法：6.3遍历二叉树和线索二叉树6.3遍历二叉树和线索二叉树后序堆栈遍历算法思想：先序的访问顺序是root,left,right假设将先序左右对调，则变成root,right,left，称之为“逆序”。后序遍历的访问顺序为left,right,root，刚好是“逆序”结果的逆向输出于是方法如下：1、将先序遍历代码中的left和right对调。数据存在堆栈S中。2、在先序遍历过程中，每次Push节点后紧接着print结点。对应的，在后序遍历时，将print结点改为把当前结点PUSH到堆栈Q中。3、遍历完成后，将堆栈Q中的结果pop并print，即为“逆序”结果的逆向，也就是后序遍历的结果。缺点是堆栈Q的深度等于数的结点数，空间占用较大。2022/12/13532022/12/13543

二叉树算法举例:voidCreatebiTree(BiTree&T)（先序）{//在先序遍历二叉树过程中输入结点字符，建立二叉链表

//指针T指向所建二叉树的根结点

cin>>ch；

if(ch=='#')T=NULL;//建空树

else{T=newBiTNode;//"访问"操作为生成根结点

T->data=ch;CreateBiTree(T->lchild);//递归建(遍历)左子树

CreateBiTree(T->rchild);//递归建(遍历)右子树

}//else}//CreateBiTreeAB#DE###C##6.3遍历二叉树和线索二叉树ABCED2022/12/1355voidBiTreeDepth(BiTreeT,inth,int&depth)（先序）{//h为T指向结点所在层次，T指向根，则h的初值为1，

//depth为当前求得的最大层次,其初值为0

if(T){if(h>depth)depth=h;BiTreeDepth(T->lchild,h+1,depth);BiTreeDepth(T->rchild,h+1,depth);}//if}//BiTreeDepth

最初的调用语句为：

d=0;BiTreeDepth(r,1,d);6.3遍历二叉树和线索二叉树2022/12/1356D=0H=1D=1H=1D=2H=2D=3H=3D=3H=2D=4H=4D=4H=4D=4H=3фффффффффD=3H=3D=4D:depthH:h6.3遍历二叉树和线索二叉树6.3遍历二叉树和线索二叉树2022/12/1357intTreeEqual(BiTreeT1,BiTreeT2)//判断相等//如果两树相等，返回1，否则返回0（先序）{if(!T1&&!T2)return(1);elseif(T1&&T2)

{if(T1->data==T2->data) if(TreeEqual(T1->lchild,T2->lchild)) return(TreeEqual(T1->rchild,T2->rchild));}return(0);}2022/12/1358BiTreeTreeCopy(BiTreeT)//二叉树复制（先序）{if(T)

{p=(BiTree)malloc(sizeof(BiTNode)); p->data=T->data;p->lchild=TreeCopy(T->lchild);//递归调用

p->rchild=TreeCopy(T->rchild);//递归调用

return(p); }elsereturn(NULL);}6.3遍历二叉树和线索二叉树2022/12/13596.3遍历二叉树和线索二叉树6.3.2

线索二叉树1.

什么是线索二叉树遍历的实质是对非线性结构的二叉树进行线性化处理。（将二叉树的节点排列成一个线性序列）遍历序列中某结点的前驱、后继的位置只能在遍历的动态过程中得到。（二叉链表存储时，只能找到结点的左右孩子信息，不能直接得到其在任一序列的直接前驱和后继）

n个结点的二叉链表中有n+1个空链域，可以存放其前驱和后继的指针。（能否利用其加快遍历速度呢？）结点结构：2022/12/13606.3遍历二叉树和线索二叉树typedefstructBiThrNode{TELemTypedata;structBiThrNode*lchild;structBiThrNode*rchild;unsignedltag;unsigned rtag;}BitThrNode,*BiThrTree;ltag=0，lchild指向左子结点ltag=1，lchild指向前驱结点rtag=0，rchild指向右子结点rtag=1，rchild指向后继结点

以这种结点结构构成的二叉链表作为二叉树的存储结构,称为线索链表,其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称为线索二叉树

(ThreadedBinaryTree)。2022/12/1361DCFEBA无前驱结点无后继结点00000011111111ABDECFThrt新增头结点6.3遍历二叉树和线索二叉树注：本小节中的前驱和后继指遍历序列中线性化逻辑关系中某结点的前驱和后继，不是其父子结点。中序线索二叉树建立一个头结点，其lchild域指向二叉树根结点，其rchild域指向中序遍历时访问的最后一个结点；中序遍历时第一个结点的lchild域指向头结点；中序遍历时最后一个节点的rchild域指向头结点；好比建立了一个双向线索链表2022/12/13626.3遍历二叉树和线索二叉树2022/12/13632.

前驱与后继的查找BiThrNode*priornode(BiThrNode*p){BiThrNode*pre=p->lchild;if(!p->Ltag) //查找左子树的最右结点

while(!pre->Rtag)pre=pre->rchild;return(pre);//Ltag=1时可直接返左链域}BiThrNode*nextnode(BiThrNode*p){BiThrNode*next=p->rchild;if(!p->Rtag) //查找右子树的最左结点

while(!next->Ltag)next=next->lchild;return(next);//Ltag=1时可直接返右链域}6.3遍历二叉树和线索二叉树2022/12/13646400000011111111ABDECFThrt新增头结点6.3遍历二叉树和线索二叉树2022/12/13653.

线索二叉树的遍历为方便起见，为线索二叉树增加一个头结点(Thrt)，使之类似一个双向循环线索链表。算法1：P134算法6.5算法2：利用nextnode函数Voidinorder_thr(BiThrTreeT){p=T->lchild;//p指向根结点while(p!=T&&!p->Ltag) //查找最左结点

p=p->lchild;while(p!=T){printf(p->data);p=nextnode(p);}}6.3遍历二叉树和线索二叉树6.3遍历二叉树和线索二叉树思考：如何将一个二叉树线索化？实际上线索化是将二叉链表中的空指针改为其直接前驱或后继节点的线索，而直接前驱和后继只能在遍历时得到，因此线索化的过程实际上就是在遍历的过程中修改空指针的过程。在这个过程中设定一个指针pre指向刚刚访问过的节点，设定指针p指向当前访问的节点，那么修改空指针的过程就迎刃而解了。2022/12/13662022/12/13674

二叉树的线索化P134-135算法6.6和6.7voidinorderthreading(BiThrTree&Thrt,BiThrTreeT)//

设线索化前T中每个结点的Ltag和Rtag域均为0.{BiThrNode*pre,*p; *S[MAX];

//pre指向上次处理过的结点，p指向当前处理的结点//S为顺序结构的栈

inti=0; //i为栈顶位置

Thrt=(BiThrNode*)malloc(sizeof(BiThrNode));Thrt->Ltag=0;Thrt->Rtag=1;Thrt->rchild=Thrt;//先回指if(!T)Thrt->lchild=Thrt;//空树6.3遍历二叉树和线索二叉树ltag=0，lchild指向左子结点ltag=1，lchild指向前驱结点rtag=0，rchild指向右子结点rtag=1，rchild指向后继结点2022/12/1368else{Thrt->lchild=T;pre=Thrt;p=T;do{while(p){S[i++]=p;p=p->lchild;}

//找寻p结点的左子树中的最左结点

if(i>0){p=S[--i];if(!p->lchild){p->Ltag=1;p->lchild=pre;}if(!pre->rchild){pre->Rtag=1;pre->rchild=p;}pre=p; //pre为上次循环中处理过的结点

p=p->rchild; //p为本次循环中处理的结点

}}while(i!=0||p)pre->Rtag=1;pre->rchild=Thrt;Thrt->rchild=pre;}}6.3遍历二叉树和线索二叉树voidinorder(BiTreeT){InitStack(S);p=T;

while (p||!SatckEmpty(S)){if(p){Push(S,p); p=p->lchild;}else{Pop(S,p);printf(p->data); p=p->rchild; }}}2022/12/1369本节课后作业

“数据结构题集（C语言版）”

P386.4P396.13P426.422022/12/13706.4树和森林………ABCDFGHIJEA123-1B45-10C6-1-10D78-10E-1-1-11F-1-1-11G-1-1-12H9-1-13I-1-1-13J-1-1-170123456789用数组（静态链式存储）表示左图的树，-1表示空。缺点：空指针域太多，有(K-1)×n+1个。例:度数K＝3的树6.4.1树的存储结构1孩子(双亲）表示法：由数据域、K个子结点指针域（父结点指针域）组成。datachild1child2childkparents树的度：结点度的最大值k

设度为0,度为1,度为2……度为k-1,度为k的结点数目分别为：n0,n1,n1,……,n(k-1),nk.

总的结点数目：n=n0+n1+n2+……+n(k-1)+nk.①

总的分支数目：n-1=1*n1+2*n2+3*n3+……+(k-1)*n(k-1)+k*nk②

等式左边n-1的由来:除了根节点外所有的其他每个结点都向上有一个分支指向它

等式右边的由来：某个结点所产生的分支数目=这个结点的度

空链域个数：k*n0+（k-1）*n1+(k-2)*n2+……+1*n(k-1)+0*nk③

①式乘以k减去②得到③(k*①-②=③=n*(k-1)+1)

2022/12/13716.4树和森林2022/12/1372ABCDFGHIJEA∧BCD∧F∧∧G∧H

∧I∧∧E∧J∧6.4树和森林2孩子兄弟表示法：由数据域、指向它的第一棵子树树根的指针域、指向它的兄弟结点的指针域组成。实质上是用二叉树表示一棵树。（右子树为空）firstchilddatanextsibling2022/12/1373ABCDFGHIJEABCDFGHIJEABCDFGHIJE6.4树和森林6.4.2树、森林与二叉树的转换1树转换成相对应的二叉树：

1）保留每个结点的最左面的分支，其余分支都被删除。

2）同一父结点下面的结点成为它的左方结点的兄弟。2022/12/1374BCDFGHIJEBCDFGHIJEABCDFGHIJEA6.4树和森林2森林转换成相对应的二叉树：

增加一个虚拟的根结点，它的子结点为各棵树的根。那么，就变成了树转换成二叉树的问题。2022/12/1375NBCDFGHIJEA

T1T2

……T3LR先根：ABEFCGDHJI后根：EFBGCJHIDA6.4树和森林6.4.3树、森林的遍历1树的先根、后根遍历：

1）先根：类似于二叉树的先序遍历（NLR）N:根；L：第一棵子树，R：其余的子树，遍历方向由第二棵子树至最后一棵子树。

2）后根：类似于二叉树的后序遍历（LRN）L：第一棵子树，R：其余的子树，遍历方向由第二棵子树至最后一棵子树，N:根。2022/12/1376先序：BEFCGDHJI后序：EFBGCJHIDBCDFGHIJEABCDFGHIJE2森林的先序、后序遍历：

1）森林的先序遍历类似于树的先序遍历。增加一个虚拟的根结点，它的子结点为各棵树的根。对这棵树进行先根遍历，即得到森林的先序序列（去掉树根结点）。

2）森林的后序遍历类似于树的后序遍历。增加一个虚拟的根结点，它的子结点为各棵树的根。对这棵树进行后根遍历，即得到森林的后序序列（去掉树根结点）。6.4树和森林2022/12/13776.5赫夫曼树及其应用路径长度：结点之间的树枝的总数树的路径长度：从根到每一结点的路径长度之和树的带权路径长度(WPL)：叶子结点的带权路径长度之和最优二叉树或赫夫曼树：树的带权路径长度WPL最小的二叉树EGHLLEHGEGHL777524442255WPL=36WPL=46WPL=356.5.1最优二叉树（赫夫曼树）2022/12/1378分数等级比例0~5960~6970~7980~8990~100EDCBA0.050.150.400.300.10a<60a<70a<80a<90EDCBAYNNNNYYY70≤a<80CBEADYNYYN80≤a<9060≤a<70a<60a<80a<70a<90a<60EDCABNNNNNNYYYY判定树：6.5赫夫曼树及其应用WPL=3.15WPL=2.05WPL=2.22022/12/1379

(1)由给定的n个权值{w0,w1,w2,…,wn-1}，构造具有n棵二叉树的集合F={T0,T1,T2,…,Tn-1}，其中每一棵二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。

(2)重复以下步骤,直到F中仅剩下一棵树为止：

①在F中选取两棵根结点的权值最小的二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。②在F中删去这两棵二叉树。③把新的二叉树加入F。6.5赫夫曼树及其应用赫夫曼算法：赫夫曼树的构造过程2022/12/1381

赫夫曼编码主要用途是实现数据压缩。设给出一段报文：CASTCASTSATATATASA，字