数据结构课件

第六章树和二叉树定义：树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；（2）其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。6.1树的定义和基本术语.树定义T1T2T3ACBGFEHIJDMKLA.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的子树。

基本操作P：}ADTTree.

基本操作：查找插入删除.

Root(T)//求树的根结点查找类：Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历.InitTree(&T)//初始化置空树插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树.

ClearTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树.树的其它表示方式凹入表示嵌套集合广义表.基本术语1.结点

指树中的一个数据元素，一般用一个字母表示。

2.度

一个结点包含子树的数目，称为该结点的度。

3.树叶（叶子）

度为0的结点，称为叶子结点或树叶，也叫终端结点。

4.孩子结点

若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6-1（c）中A的孩子为B，C，D。

5.双亲结点

若结点X有子女Y，则X为Y的双亲结点。.6.祖先结点

从根结点到该结点所经过分支上的所有结点为该结点的祖先。

7.子孙结点

某一结点的子女及子女的子女都为该结点子孙。

8.兄弟结点

具有同一个双亲的结点，称为兄弟结点。

9.分支结点

除叶子结点外的所有结点，为分枝结点，也叫非终端结点。

10．层数

根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。

.11.树的高度（深度）

树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度1。

12.树的度

树中结点度的最大值称为树的度。

13.有序树

若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。

14.无序树

若一棵树中所有子树的次序无关紧要，则称为无序树。

15．森林（树林）

若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)

根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)对比树型结构和线性结构的结构特点.二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树6.2二叉树6.2.1二叉树的定义.二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树.二叉树的抽象数据类型ADTBinaryTree{

数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=

，则R=

，称二叉树为空二叉树；若D

，则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}

,则存在D-{root}={D1,Dr},且

D1

Dr

；（3）若D1

，则D1中存在唯一的元素x1,<root,x1>

H,且存在D1上的关系H1

H；若Dr

,则Dr中存在唯一的元素xr,<root,xr>

H,且存在Dr上的关系Hr

H；H={<root,x1>,<root,xr>,H1,Hr};（4）（D1，{H1}）是一棵符合本定义的二叉树，称为根的左子树，（Dr，{Hr}）是一棵符合本定义的二叉树，称为根的右子树。基本操作：}ADTBinaryTree.性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)用归纳法证明：

归纳基：

归纳假设：

归纳证明：i=1

层时，只有一个根结点：

2i-1=20=1；假设对j，1<=j<i，命题成立2j-1

；证明j=i时命题也成立，由归纳假设，第i-1层至多有2i-2个结点，二叉树上每个结点至多有两棵子树，故第i层时结点数最多=2i-2

2=2i-1

。6.2.2二叉树的性质.性质2：

深度为k的二叉树上至多含2k-1个结点（k≥1）。证明：基于上一条性质，深度为k的二叉树上的结点数至多为

20+21++2k-1=2k-1。.

性质3：

对任何一棵二叉树，若它含有n0个叶子结点、n2

个度为2的结点，则必存在关系式：n0=n2+1。证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。.两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。123456789101112131415abcdefghij.

性质4：具有n

个结点的完全二叉树的深度为

log2n

+1

。证明：设完全二叉树的深度为k

则根据第二条性质得2k-1≤n<2k即k-1≤log2n<k

因为k只能是整数，因此，k=log2n

+1。.性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：

(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为

i/2

的结点为其双亲结点；

(2)若2i>n，则该结点无左孩子，

否则，编号为2i的结点为其左孩子结点；

(3)若2i+1>n，则该结点无右孩子结点，

否则，编号为2i+1的结点为其右孩子结点。.示意图2i2i+1i2i+22i+3i+1

i/2

j层j+1层2j-12j2j+1.示意图2i+22i+3i+12i2i+1i......2i2i+1i2i+22i+3i+1LCHILD(i)LCHILD(i+1)RCHILD(i)RCHILD(i+1)….6.2.3二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示.一、二叉树的顺序存储结构整个二叉树可以按照从上到下，从左到右的顺序排序，做标号；对于满/完全二叉树，可以从根结点开始按序号存放对于一般的二叉树，可以参照满二叉树的编码方法进行编码，位置空的结点空置。.#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;二叉树的顺序存储表示.1234567891018910452673完全二叉树.ABCDEF

ABDCEF

0123456789101112131401326.ABC非完全二叉树ABCØØØØABØØØØC.二、二叉树的链式存储表示1.二叉链表2．三叉链表3．线索链表…….ADEBCF

rootlchilddatarchild1.二叉链表datalchildrchild.typedefstructBiTNode{//结点结构TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:C语言的类型描述如下:.2．三叉链表A∧∧∧BCDEF∧∧∧∧∧lchilddatarchildparentdatalchildrchildparent.

typedefstructTriTNode{//结点结构TElemTypedata;

structTriTNode*lchild,*rchild;//左右孩子指针

structTriTNode

*parent;//双亲指针

}TriTNode,*TriTree;lchilddataparentrchild结点结构:C语言的类型描述如下:.假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有：DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。6.3遍历二叉树和线索二叉树6.3.1遍历二叉树.前序遍历二叉树中序遍历二叉树后序遍历二叉树访问根结点；前序遍历左子树；前序遍历右子树；中序遍历左子树；访问根结点；中序遍历右子树；后序遍历左子树；后序遍历右子树；访问根结点；.遍历图例ACFEDB中序序列为：前序序列为：后序序列为：DBEACFABDECFDEBFCA.二叉树表达式(a+b*(c-d)-e/f)遍历此二叉树其先序序列为：-+a*b-cd/ef

按中序遍历,其中序序列为：a+b*c-d-e/f按后序遍历,其后序序列为：abcd-*+ef/-－＋*a/b-dcfe.图例ab*c-ba*-cab*c-－×abcacb×--*abca*b-cab*c-.先（根）序的遍历算法的递归描述voidPreorderTraverse(BiTreeT,status(*visit)(TElemType&e)){

//先序遍历二叉树

if(T){

if(Visit(T->data))

if(PreOrderTraverse(T->lchild，Visit))

if(PreOrderTraverse(T->rchild，Visit))

returnOK;

returnERROR；

}elsereturnOK；}p129.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)；

}

}//While

returnOK；

}

p130acb×-.StatusInOrderTraverse(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

}//While

returnOK；

}P131了解.StatusCreateBiTree(BiTree&T){scanf(&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);

T->data=ch;//生成根结点CreateBiTree(T->lchild);//构造左子树CreateBiTree(T->rchild);//构造右子树}returnOK;}//CreateBiTree建立二叉树p131.‘’A‘’‘’ABC‘’‘’‘’DE‘’‘’‘’.6.3.2线索二叉树

n个结点的二叉链表中含有n+1个空指针域，可以利用这些空指针域来存放某结点的前驱和后继的信息。这些附加的指针称为“线索”，加上了线索的二叉链表称为线索链表，加上线索的二叉树就是线索二叉树（ThreadedBinaryTree）。将二叉树变为线索二叉树的过程称为线索化。

lchildltagdata

rtagrchildltag=

rtag=

îíì指向结点前驱指向结点的左孩子lchildlchild:1:0îíì指向结点后继指向结点的右孩子rchildrchild:1:0.中序线索二叉树NULLACFEDBNULLA00E11C01D11F11B00NULLNULL.类型定义typedefstructBinhrNode{TelemTypedata;structBinhrNode*lchild,*rchild;

左、右孩子指针intltag,rtag;

}BinhrNode，

*BinhrTree

.对中序线索化链表的遍历算法

※中序遍历的第一个结点？

※在中序线索化链表中结点的后继？左子树上处于“最左下”（没有左子树）的结点。若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。..StatusInorderTraverse_Thr(BiThrTreeT,status(*visit)(TElemType)){

P=T–>lchild;while(p!=T){

while(p–>LTag==Link)p=p–>lchild;

if(!visit(p–>data))returnerror;while(p–>RTag==Thread&&p

–>rchild!=T){p=p–>rchild;Visit(p–>data);}p=p–>rchild;}

returnOK;}P134.在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。如何建立线索链表？.StatusInorderThreading(BiThrTree&Thrt,BiThrTreeT){if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);Thrt–>LTag=Link;Thrt–>RTag=Thread;Thrt–>rchild=Thrt;if(!T)Thrt–>lchild=Thrt;else{Thrt–>lchild=T;pre=Thrt;

InThrTreading(T);pre–>rchild=Thrt;pre–>RTag=Thread;Thrt–>rchild=pre;}returnOK;}//InorderThreadingP134.VoidInThreading(BiThrTreep){if(p){InThreading(p–>lchild);

if(!p–>lchild){p–>LTag=Thread;p–>lchild=pre;}if(!pre–>rchild){pre–>rchild){pre–>RTag=Thread;pre–>rchild=p;}pre=p;InThreading(p–>rchild);}}P135.6.6树和森林树的三种存储结构一、双亲表示法二、孩子表示法三、树的二叉链表(孩子-兄弟）存储表示法.ABCDEFG0

A

-11

B

02

C

03

D

04

E

2

5

F

26

G

5r=0n=7dataparent一、双亲表示法.

typedefstructPTNode{Elemdata;

intparent;//双亲位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100结点结构:C语言的类型描述:.typedefstruct{

PTNodenodes[MAX_TREE_SIZE];intr,n;//根结点的位置和结点个数}PTree;树结构:.二、孩子表示法①②.③.typedefstructCTNode{intchild;structCTNode*next;}*ChildPtr;孩子结点结构:

childnextC语言的类型描述:.

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子链的头指针}CTBox;

datafirstchild树结构:typedefstruct{

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

1B

2C

3D

4E

5F

6G

r=0n=7datafirstchild123456-1000225.ABCDEFGABCEDFGrootABCEDFG

三、孩子-兄弟表示法(树的二叉链表表示法).typedefstructCSNode{Elemdata;

structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;C语言的类型描述:结点结构:

firstchilddatanextsibling.6.4.2森林和二叉树的转换.若树采用孩子兄弟表示法，二叉树采用二叉链表表示，则从存储结构上看，结点定义完全相同。因此，在使用该存储结构下，树可以转化为二叉树。树和二叉树转化步骤（1）连线：在所有的兄弟结点之间加一条连线。（2）切线：对于每个结点，除了保留与其最左孩子的连线外，去掉该结点与其它孩子之间的连线。（3）旋转：将按（1）、（2）的方法形成的二叉树，沿顺时针方向旋转450,就可以得到一棵形式上更为清楚的二叉树。

.

应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：

左是孩子，右是兄弟。.树和二叉树转化例FGHABCEDFGHABCEDFGHABCEDFHABGCED.森林到二叉树的转换若树采用孩子兄弟表示法，二叉树采用二叉链表表示，则：任一棵树，都可以找到唯一的一棵二叉树和它对应，而且该二叉树没有右子树(因此一棵二叉树，不一定保证能转换为一棵树)若把森林中的第二棵树的根结点，看成是第一棵树的根结点的兄弟结点，则这两棵树可以转换为一棵二叉树。依次类推，可以认为森林和二叉树是一一对应的，从而得到二叉树和森林的转换规则.转换示例ABCDFGHIEABCDFGHIECABDFGHIE.二叉树到森林的转换例IABDFGHKCEJIABDJHCEFGK.6.4.3树和森林的遍历一、树的遍历二、森林的遍历.树的遍历可有三条搜索路径:按层次遍历:先根(次序)遍历:后根(次序)遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。若树不空，则先依次后根遍历各棵子树，然后访问根结点。若树不空，则自上而下自左至右访问树中每个结点。.ABCDEFGHIJK先根遍历时顶点的访问次序：ABEFCDGHIJK后根遍历时顶点的访问次序：EFBCIJKHGDA层次遍历时顶点的访问次序：ABCDEFGHIJK.

BCDEFGHIJK1．森林中第一棵树的根结点；2．森林中第一棵树的子树森林；3．森林中其它树构成的森林。森林由三部分构成：.1.先序遍历森林的遍历若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林；先序遍历森林中(除第一棵树之外)其余树构成的森林。即：依次从左至右对森林中的每一棵树进行先根遍历。.２．中序遍历若森林不空，则中序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍历森林中(除第一棵树之外)其余树构成的森林。.6.6哈夫曼树及其应用

最优树的定义

如何构造最优树

前缀编码

.

一、最优树的定义树的路径长度定义为：树中每个结点的路径长度之和。

结点的路径长度定义为：从根结点到该结点的路径上分支的数目。.结点的带权的路径长度：该结点到根结点之间的路程长度与该结点上权的乘积树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和

WPL(T)=

wklk(对所有叶子结点)。由n个带权值的叶子结点构成的二叉树中，WPL最小的二叉树称为最优二叉树，或Huffman树.27975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954.if(a<60)b=“bad”;elseif(a<70)b=“pass”;elseif(a<80)b=“general”;else…分数0-5960-6970-7980-8990-100比例数0.050.150.400.300.101*0.05+2*0.15+3*0.4+4*0.3+4*0.1=3.1510000个数据需比较31500次.分数0-5960-6970-7980-8990-100比例数0.050.150.400.300.102*0.1+2*0.3+2*0.4+3*0.15+3*0.05=2.2.例如:已知权值W={5,6,2,9,7}9562752769767139527二、如何构造最优树.67139527952716671329.dcba9653ba96358a9614358962314538abcdcbd哈夫曼树.三、哈夫曼编码

数据通讯中，经常采用0、1序列来表示不同的字符。在发送端需要将待发送的字符转化成二进制的0、1序列（编码），在接受端又要把接受的0、1序列转化成对应的字符序列（译码）。字符串：“ABACCDA”,每个字符采用2比特表示，共14比特；考虑到出现频率，A：’0’,C：’1’,B：’00’,D：’01’，则编码为：“000011010”，共9比特。译码有困难：“0000”有多种译法：ABA,AAAA,BB,BAA…….指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。前缀编码利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。.ACBDEF160000111364125736912G0112801A：100B：11C：001D：1011E：1010F：000G：011、利用二叉树编码得到的是二进制前缀编码？2、得到电文总长最短？.哈夫曼编码

设有n种字符，在一个电文中，第i种字符出现的次数为Wi,编码长度为li，使L最小，可以看作是已知n个结点的权wi，求一棵Huffman树的问