数据结构 第六章树和二叉树

数据结构第六章树和二叉树第一页，共六十九页，2022年，8月28日第六章树和二叉树6.1树的定义和基本术语6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构6.3遍历二叉树和线索二叉树6.3.1遍历二叉树6.3.2线索二叉树6.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换6.6赫夫曼树及其应用6.6.1最优二叉树(赫夫曼树)6.6.2赫夫曼编码第二页，共六十九页，2022年，8月28日树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然界中的树。第三页，共六十九页，2022年，8月28日ABCDEFGH树形结构——结点间具有分层次的连接关系HBCDEFGA第四页，共六十九页，2022年，8月28日6.1树的定义和基本术语

树(Tree)是n(n>0)个结点的有限集合T，它满足如下条件：有且仅有一个称为根(Root)的结点。其余结点可划分为m(m>=0)个互不相交的有限集合T1,T2,…,Tm,其中每个集合又是一棵树，并称其为根的子树(SubTree)。这是一个递归定义。有时n=0也称为空树。ACGT2DHI

T3J

MB

E

LKT1F第五页，共六十九页，2022年，8月28日树的表示方法1）树形图法

2）嵌套集合法

3）广义表形式

4）凹入表示法(A(B,C(E,F),D(G)))ABCDEFGABCEFDGABDGEFC第六页，共六十九页，2022年，8月28日线性结构

（一对一关系）

树结构（一对多关系）

第一个数据元素(无前驱)

根结点(无前驱)最后一个数据元素(无后继)

多个终端结点(无后继)其它数据元素

树中其它结点(一个前驱、一个后继)

(一个前驱、多个后继)树形结构和线性结构的比较第七页，共六十九页，2022年，8月28日树结构的基本术语结点(node)——表示树中的元素，包括数据元素及若干指向其子树的分支。结点的度(degree)——结点拥有的子树数。叶子(leaf)或终端结点——度为0的结点。分支结点——度大于零的结点。树的度——树中所有结点的度的最大值。孩子(child)——结点的子树的根。双亲(parents)——孩子结点的上层结点。兄弟(sibling)——同一双亲的孩子。堂兄弟——其双亲在同一层的结点互为堂兄弟。结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层…。深度(depth)——树中结点的最大层次数。森林(forest)——m(m0)棵互不相交的树的集合。ABCDEFGHIJKLM第八页，共六十九页，2022年，8月28日树的抽象数据类型定义：ADTTree｛

数据对象D：D是具有相同特性的数据元素的集合。

数据关系R：若D为空集，则称为空树;若D仅含一个数据元素，则R为空集，否则R＝｛H｝，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D－｛root｝≠Ф，则存在D－｛root｝的一个划分D1,D2,...,Dm（m＞0），对任意j≠k（1≤j,k≤m）有Dj∩Dk=φ，且对任意的i（1≤i≤m），唯一存在数据元素xi∈Di，有<root,xi>∈H;（3）对应于D－｛root｝的划分，H－｛<root,x1>，....，<root,xm>｝有唯一的一个划分H1,H2,...,Hm（m＞0），对任意j≠k（1≤j,k≤m）有Hj∩Hk=Ф，且对任意的i（1≤i≤m），Hi是Di上的二元关系，（Di,{Hi}）是一棵符合本定义的树，称为根root的子树。第九页，共六十九页，2022年，8月28日树的抽象数据类型定义--基本操作（之一）

InitTree(&T)；操作结果：构造空树T。

DestroyTree(&T)；初始条件：树T存在。操作结果：销毁树T。

CreateTree(&T，definition)；初始条件：definition给出树T的定义。操作结果：按definition构造树T。

ClearTree(&T)；初始条件：树T存在。操作结果：将树T清为空树。第十页，共六十九页，2022年，8月28日树的抽象数据类型定义--基本操作（之二）

TreeEmpty(T)

初始条件：树T存在。操作结果：若T为空树，则返回TURE，否则FALSE。

TreeDepth(T)

初始条件：树T存在。操作结果：返回T的深度。

Root(T)

初始条件：树T存在。操作结果：返回T的根。

Value(T,cur_e)；初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。第十一页，共六十九页，2022年，8月28日树的抽象数据类型定义--基本操作（之三）

Assign(T，cur_e，value)

初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值为value。

Parent(T，cur_e)

初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。

LeftChild(T，cur_e)

初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。

RightSibling(T，cur_e)

初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。第十二页，共六十九页，2022年，8月28日树的抽象数据类型定义--基本操作（之四）

InsertChild(&T，&p，i，c)；初始条件：树T存在，p指向T中某个结点，1≤i≤p所指结点的度＋1，非空树c与T不相交。操作结果：插入c为T中p指结点的第i棵子树。

DeleteChild(&T，&p，i)；初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点的度。操作结果：删除T中p所指结点的第i棵子树。

TraverseTree(T，Visit())；初始条件：树t存在，Visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数Visit()一次且至多一次。一旦Visit()失败，则操作失败。｝ADTTree第十三页，共六十九页，2022年，8月28日6.2二叉树二叉树的定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。二叉树的特点：每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒第十四页，共六十九页，2022年，8月28日二叉树的五种基本形态：空二叉树只有一个根结点的二叉树右子树为空的二叉树左子树为空的二叉树左、右子树均非空的二叉树注意：二叉树中子树是有左右之分的，即使只有一棵子树，或为左子树，或为右子树这不是二叉树这是二叉树第十五页，共六十九页，2022年，8月28日6.2.2二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。性质2：深度为k的二叉树至多有2k-1个结点(k≥1)。性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。1234567第十六页，共六十九页，2022年，8月28日几种特殊形态的二叉树满二叉树定义：深度为k且有2k-1个结点的二叉树特点：每一层上的结点数都是最大结点数完全二叉树定义：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。特点：①叶子结点只可能在层次最大的两层上出现②对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L或L+1说明：①满二叉树是完全二叉树,反之不成立;

②对于完全二叉树,若某结点无左孩子,则必无右孩子,该结点为叶结点。第十七页，共六十九页，2022年，8月28日1231145891213671014151231145891267101234567123456第十八页，共六十九页，2022年，8月28日性质4：具有n个结点的完全二叉树的深度为log2n+1性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1≤i≤n)，有：

(1)如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2(2)如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i(3)如果2i+1>n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1123114589126710第十九页，共六十九页，2022年，8月28日6.2.3二叉树的存储结构顺序存储结构用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。下标01234567891011ABCDEFGHIJKLABCDEFGHIJKL第二十页，共六十九页，2022年，8月28日对完全二叉树而言，顺序存储结构既简单又节省存储空间。一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。

(最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点的存储空间)ABCDEEØDØCBA第二十一页，共六十九页，2022年，8月28日链式存储结构typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;

rchilddatalchilddataparentlchildrchilddatalchildrchildparent第二十二页，共六十九页，2022年，8月28日链式存储结构示例注意：

①一个二叉链表由根指针root惟一确定。若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的指针为空。

②具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。第二十三页，共六十九页，2022年，8月28日基本操作的函数原型说明(一)StatusCreateBiTree(BiTree&T);//按先序次序输入二叉树中结点的值（一个字符），//空格字符表示空树，//构造二叉链表表示的二叉树T。StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉链表存储结构,Visit是对结点操作的应用函数//先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。//一旦Visit()失败，则操作失败。第二十四页，共六十九页，2022年，8月28日基本操作的函数原型说明(二)

StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉链表存储结构,Visit是对结点操作的应用函数。//中序遍历二叉树T，一旦Visit()失败，则操作失败。StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉链表存储结构,Visit是对结点操作的应用函数。//后序遍历二叉树T，一旦Visit()失败，则操作失败。StatusLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee));//采用二叉链表存储结构,Visit是对结点操作的应用函数。//层序遍历二叉树T，一旦Visit()失败，则操作失败。第二十五页，共六十九页，2022年，8月28日6.3遍历二叉树

按某条搜索路径巡访二叉树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。ABCDGEF第二十六页，共六十九页，2022年，8月28日假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：

DLR——先（根）序遍历，

LDR——中（根）序遍历，

LRD——后（根）序遍历。第二十七页，共六十九页，2022年，8月28日先序遍历二叉树的操作定义若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。

ABCDFEGABCDGEF第二十八页，共六十九页，2022年，8月28日中序遍历二叉树的操作定义若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。

CBDFAGEABCDGEF第二十九页，共六十九页，2022年，8月28日后序遍历二叉树的操作定义若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。

CFDBGEAABCDGEF第三十页，共六十九页，2022年，8月28日例：已知结点的先序序列和中序序列，求整棵二叉树先序序列：ABCDEFG中序序列：CBEDAFGAC

B

E

DFGABCDEFGABCFDEG第三十一页，共六十九页，2022年，8月28日先序遍历二叉树的递归算法StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}//PreOrderTraverse第三十二页，共六十九页，2022年，8月28日作业分别写出中序遍历二叉树和后序遍历二叉树的递归算法已知一棵二叉树的中序和后序序列如下，画出此二叉树并写出该二叉树的先序遍历序列。中序序列：A,B,C,D,J,E,F,H,G,I

后序序列：B,C,J,D,A,H,I,G,F,E第三十三页，共六十九页，2022年，8月28日中序遍历二叉树的非递归算法基本思想

中序遍历一棵非空树t时，首先应该进入t的左子树访问，此时由于t的根结点及右子树尚未访问，因此必须将t保存起来，放入栈中，以便访问完其左子树后，从栈中取出t，进行其根结点及右子树的访问；对t的左子树和右子树的遍历也是如此。主要步棸先将根结点入栈；将栈顶元素的所有左孩子依次入栈；出栈一个结点，访问之；若该结点的右孩子不空，入栈，重复2)，3)步；如果栈不空，重复3)，4)步，否则结束。第三十四页，共六十九页，2022年，8月28日StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采用二叉链表存储结构，中序遍历二叉树的非递归算法。

InitStack(S);Push(S,T); //根指针进栈

while(!StackEmpty(S)){while(GetTop(S,p)&&p)Push(S,p->lchild);//向左走到尽头

Pop(S,p); //空指针退栈

if(!StackEmpty(S)){ //访问结点，向右一步

Pop(S,p);if(!Visit(p->data))returnERROR; Push(S,p->rchild);

}//if }//whilereturnOK;}//InOrderTraverse算法6.2第三十五页，共六十九页，2022年，8月28日算法6.3StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}//根指针进栈，遍历左子树

else{//根指针退栈，访问根结点，遍历右子树

Pop(S,p);if(!Visit(p->data))returnERROR;p=p->rchild;}//else}//whilereturnOK;}//InOrderTraverse第三十六页，共六十九页，2022年，8月28日6.3.2线索二叉树n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为“线索”）这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded

BinaryTree)。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。第三十七页，共六十九页，2022年，8月28日线索二叉树结点的结构:其中，ltag和rtag是增加的两个标志域，用来区分结点的左、右指针域是指向其左、右孩子的指针，还是指向其前趋或后继的线索。

0lchild域指示其左孩子ltag={1lchild域指示其前驱

0rchild域指示其右孩子rtag={1rchild域指示其后继datalchildrchildrtagltag第三十八页，共六十九页，2022年，8月28日中序线索二叉树的表示第三十九页，共六十九页，2022年，8月28日注意：

图中的实线表示指针，虚线表示线索。

结点C的左线索为空，表示C是中序序列的开始结点，无前趋；

结点E的右线索为空，表示E是中序序列的终端结点，无后继。

线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1。

第四十页，共六十九页，2022年，8月28日6.4树和森林树的存储结构双亲表示法（静态链表存储）：以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在(静态)链表中的位置

第四十一页，共六十九页，2022年，8月28日双亲表示法举例RADEFCBGKHR-1A0B0C0D1E1F3G6H6K60123456789数组下标:第四十二页，共六十九页，2022年，8月28日#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intparent;//双亲位置域

}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//结点数

}PTree;*便于涉及双亲的操作；*求结点的孩子时需要遍历整棵树。第四十三页，共六十九页，2022年，8月28日孩子链表存储表示举例RADEFCBGKH0123456789数组下标:RAB∧

CD∧

E∧

FG∧

H∧

K∧123∧

45∧

6∧

789∧

第四十四页，共六十九页，2022年，8月28日6.4.1树的存储结构孩子表示法（链式存储）

typedefstructCTNode{//孩子结点结构

intchild;structCTNode*next;}*ChildPtr;typedefstruct{ //双亲结点结构

TElemTypedata;ChildPtrfirstchild;//孩子链表头指针

}CTBox;typedefstruct{ //树结构

CTBoxnodes[MAX_TREE_SIZE];intn,r;//结点数和根的位置

}CTree;*便于涉及孩子的操作；*求结点的双亲时不方便。第四十五页，共六十九页，2022年，8月28日6.4.1树的存储结构孩子兄弟表示法：又称二叉树表示法，或二叉链表表示法。记以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域。typedefstructCSNode{

ELemTypedata;

structCSNode*firstchild,*nextsibling;

}CSNode,*CSTree;第四十六页，共六十九页，2022年，8月28日RADEFCBGKHR^A^DE^^C^H^F^G^B^K^^孩子兄弟表示法示例：*易于实现找结点孩子的操作；第四十七页，共六十九页，2022年，8月28日6.4.2森林与二叉树的转换将树转换成二叉树的步骤：将所有兄弟结点用边连接起来对每个结点，除了保留与其长子的边外，去掉该结点与其它孩子的边abcefd转换abcefd整理abcefd说明：根结点没有右孩子第四十八页，共六十九页，2022年，8月28日6.4.2森林与二叉树的转换将森林转换成二叉树的步骤将森林中的每棵树转换成二叉树将每个二叉树的根结点看成兄弟用边连起来bacdefghi转换abcdefghi整理abcdefghi第四十九页，共六十九页，2022年，8月28日6.4.2森林与二叉树的转换将二叉树转换成树(森林)的步骤如果根有右子树，将根的右子树分开，得到几棵二叉树根据得到的二叉树往回转换。(若结点X是双亲y的左孩子，则把X的右孩子，右孩子的右孩子,…,都与y用连线连起来，最后去掉所有X到右孩子的连线。)abcdefghijk转换feabcdjkghi去边整理feabcdjkghi第五十页，共六十九页，2022年，8月28日6.4.3树和森林的遍历树的两种遍历方法：先根遍历：访问树的根结点；依次先根遍历每棵子树。RADEBCFGHK后根遍历：依次后根遍历每棵子树；访问树的根结点。DEABGHKFCRRADEFCBGKH第五十一页，共六十九页，2022年，8月28日6.4.3树和森林的遍历森林的两种遍历方法：先序遍历森林：若森林非空，则访问森林中第一棵树的根结点；先序遍历第一棵树的根结点的子树森林；先序遍历除去第一棵树之后剩余的树构成的的森林。中序遍历森林：若森林非空，则中序遍历第一棵树的根结点的子树森林；访问森林中第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成的的森林。第五十二页，共六十九页，2022年，8月28日先序遍历：ABCDEFGHIJ中序遍历：BCDAFEHJIGABCDEFGH

IJ第五十三页，共六十九页，2022年，8月28日先序遍历：ABCDEFGHIJ中序遍历：BCDAFEHJIGABCDEFGH

IJ第五十四页，共六十九页，2022年，8月28日说明先序遍历森林等同于先序遍历该森林对应的二叉树中序遍历森林等同于中序遍历该森林对应的二叉树当用二叉链表作树和森林的存储结构时，树和森林的先序遍历和后序遍历，可用二叉树的先序遍历和中序遍历算法来实现。第五十五页，共六十九页，2022年，8月28日6.6赫夫曼树及其应用路径长度：

从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称做路径长度。树的路径长度：从树根到每一结点的路径长度之和。结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。通常记作：nWPL=∑ωkιkk=1

第五十六页，共六十九页，2022年，8月28日6.6.1最优二叉树（赫夫曼树）定义：假设有n个权值{ω1,ω2,

…,ωn}，试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为ωi,则其中：带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。第五十七页，共六十九页，2022年，8月28日[例]：下面三棵二叉树的四个叶子结点a,b,c,d的权值为7、5、2、4abcd7524abcd7524cdab7524(a)WPL=7×2+5×2+2×2+4×2=36(b)WPL=7×3+5×3+2×1+4×2=46(c)WPL=7×1+5×2+2×2+4×2=35第五十八页，共六十九页，2022年，8月28日赫夫曼算法的基本思想根据给定的n个权值{ω1,ω2,…,ωn}构成n棵二叉树的集合F={T1,T2,…,Tn}其中每棵二叉树Ti中只有一个带权为ωi的根结点,其左右子树均空。在F中选取两棵根结点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复上述两个步骤，直到F只含一棵树为止。这棵树便是赫夫曼树。第五十九页，共六十九页，2022年，8月28日构造赫夫曼树举例cdab7524abc2d457abc6d57abcd117第六十页，共六十九页，2022年，8月28日6.2.2赫夫曼编码在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样发送的二进制编码尽可能地短第六十一页，共六十九页，2022年，8月28日编码方式等长编码：将给定字符集C中每个字符的码长相同【例】设待压缩的数据文件共有1000