数据结构树与二叉树详细解析课件

树的概念

二叉树二叉树遍历

线索化二叉树

树与森林

Huffman树第4章树与二叉树1树的概念第4章树与二叉树12内蒙古大学理工学院计算机学院生命科学学院外国语学院人文学院数学系物理系电子系计算机系计算中心网络中心汉语系历史系哲学系生物系环境系动物中心生物工程中心资源所英语系日语系行政机构树形结构是一种非线性结构，应用十分广泛。如：行政机构、磁盘目录、家谱等2内蒙古大学理工学院计算机学院生命科学学院外国语学院人文学院3磁盘目录3磁盘目录树和森林的概念树的定义

树是由

n(n

≥0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；除根以外的其他结点划分为m(m

≥0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树。4树和森林的概念树的定义4树的特点每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。ACGBDEFKLHMIJ5树的特点每棵子树的根结点有且仅有一个直接前驱，但可以有0个或6例5.1:Tree=(D,R)D={Book,C1,C2,C3,S1.1,S1.2,S2.1,S2.2,S2.3,S2.1.1,S2.1.2}R={<Book,C1>,<Book,C2>,<Book,C3>,<C1,S1.1>,<C1,S1.2>,<C2,S2.1>,<C2,S2.2>,<C2,S2.3>,<S2.1,S2.1.1>,<S2.1,S2.1.2>}BookC1C2C3S1.1S1.2S2.1S2.2S2.3S2.1.1S2.1.2ChapterSectionSection树是一种层次结构（hierarchystructure）6例5.1:Tree=(D,R)BookC1C27基本术语：主要来源于家谱和树双亲、子女（parent,child）：若<a,b>

R，则称a是b的双亲，b是a的子女(孩子);结点度（degree）：结点所拥有的子女数；叶（leaf）：度为0的结点；分枝结点（branchnode）：度大于0的结点；树的度：树中最大的结点度；ABCDEFGHIJMKL7基本术语：主要来源于家谱和树ABCDEFGHIJMKL8结点所在的层次（level）：根在第1层，其它任一结点所在的层是其双亲的层加1；深度或高（depth）：结点所在的层次的最大层数；兄弟（sibling)：具有同一双亲的结点互称兄弟；堂兄弟（cousin）：双亲在同层的非兄弟结点互称堂兄弟；423ABCDEFGHIJMKL18结点所在的层次（level）：423ABCDEFGHIJM9ABCACB无序有序祖先、子孙（ancestor）：一个结点是它所有子树中的结点的祖先,这些结点是它的子孙;路径（path）：是一结点序列n1,n2,n3,…,nk，并且前1个结点是后1个结点的双亲；它的长度是k-1;有序树（orderedtree）：每个结点的子女由左到右是有次序的；否则是无序树；423ABCDEFGHIJMKL19ABCACB无序有序祖先、子孙（ancestor）：42310ABCDEFGHIJKLM结点A、B、C的度分别为：3、2、1叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：0结点M的层次：3树的深度：3结点F，G为堂兄弟结点A是结点F，G的祖先10ABCDEFGHIJKLM结点A、B、C的度分别为：叶子11森林（Forest）:m(m≥0)棵互不相交的树的集合.ArootBCDEFGHIJMKLF11森林（Forest）:m(m≥0)棵互不相交的树的集二叉树

(BinaryTree)二叉树的五种不同形态二叉树的定义

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。LRLR12二叉树(BinaryTree)二叉树的五种不同形态二叉树性质1

若二叉树的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i

≥1)

[证明用数学归纳法]性质2

深度为k

的二叉树最多有2k-1个结点。(h

≥1)

[证明用求等比级数前k项和的公式]

20+21+…+2k-1=2k-1二叉树的性质13性质1若二叉树的层次从1开始,则在二叉树的第i层最性质3

对任何一棵二叉树,如果其叶结点有n0个,度为2的非叶结点有n2个,则有

n0＝n2＋1证明：若设度为1的结点有n1

个，总结点个数为n，总边数为e，则根据二叉树的定义，

n=n0+n1+n2

e=2n2+n1=n

-1因此，有

2n2+n1

=n0+n1+n2

-1

n2=n0

-1

n0=n2+1

14性质3对任何一棵二叉树,如果其叶结点有n0个,度定义1

满二叉树(FullBinaryTree)

定义2

完全二叉树(CompleteBinaryTree)

若设二叉树的高度为h，则共有h+1层。除第h层外，其它各层(0

h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。(特点)15定义1满二叉树(FullBinaryTree)1叶结点仅在层次最大的两层出现对任一结点，若其右子树的高度为l，则其左子树的高度为l或l+116叶结点仅在层次最大的两层出现16性质4

具有n(n

0)

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

log2(n+1)

-1证明：设完全二叉树的高度为h，则有

2h

-1<n

2h+1

-1变形

2h<n+12h+1

取对数

h<log2(n+1)h+1

有

log2(n+1)

=h+1

h=

log2(n+1)

-1上面h层结点数包括第h层的最大结点数23-124-117性质4具有n(n0)个结点的完全二叉树的高度性质5

如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0,1,2,…,n-1，则有以下关系：

若i=0,则i无双亲若i>0,则i的双亲为

(i-1)/2

若2*i+1<n,则i的左子女为2*i+1，若

2*i+2<n,则i的右子女为2*i+2

若i为偶数,且i!=0,

则其左兄弟为i-1,若

i为奇数,且i!=n-1,

则其右兄弟为i+1结点i所在的层次为

log2(i+1)

012374568918性质5如将一棵有n个结点的完全二叉树自顶向下，同一层自左二叉树的抽象数据类型ADTBinaryTreeis{Data

是有限个结点的集合D。当D非空时，其中有一根结点t，其余结点被分为t的左子树和右子树。OperationsConstructorProcess:建立一棵空二叉树

DeleteProcess:删除二叉树19二叉树的抽象数据类型ADTBinaryTreeis{1920

IsEmpty Process:判断二叉树是否是空Output:若二叉树为空，则返回true,否则返回falseSizeProcess:计算二叉树的结点数sizeOutput:sizeHeightProcess:计算二叉树的高度heightOutput:height

RootProcess:取二叉树根结点值xOutput:根结点值x20IsEmpty 21ParentInput:node是二叉树中的一个结点Process:求node的双亲p，若node是根，则p为空Output:pCreateBinaryTreeInput:二叉树的某种形式的定义definitionProcess:根据此定义definition构造二叉树MakeTreeInput:data是根结点值，left是左子树，right是右子树Process:创建二叉树，data是根结点值，left是其左子树，right是其右子树21Parent22

BreakTreeProcess:拆分二叉树，data是根结点数据，left是左子树，right是右子树Output:data,left,rightPreOrderInput:Visit()是结点访问函数Process:按前序遍历对二叉树中每个结点调用Visit()1次且仅1次Output:根据Visit()，按前序遍历序列得到结果InOrderInput:Visit()是结点访问函数Process:按中序遍历对二叉树中每个结点调用Visit()1次且仅1次Output:根据Visit()，按中序遍历序列得到结果22BreakTree23

PostOrderInput:Visit()是结点访问函数Process:按后序遍历次序对二叉树中每个结点调用Visit()1次且仅1次Output:根据Visit()，按后序遍历序列得到结果LevelOrderInput:Visit()是结点访问函数Process:按层次对二叉树中每个结点调用Visit()1次且仅1次Output:根据Visit()，按层次遍历序列得到结果}//BinaryTree23PostOrder完全二叉树一般二叉树的顺序表示的顺序表示二叉树的顺序表示0123456789012356781113013789456213012653781149101224完全二叉树一般二叉树二叉树的顺序表示00261430极端情形:只有右单支的二叉树0261430250261430极端情形:只有右单支的二叉树02614302二叉树的链表表示leftChilddatarightChilddataleftChildrightChild二叉链表26二叉树的链表表示leftChilddatarig二叉树的链表表示leftChilddataparentrightChildparentdataleftChildrightChild三叉链表27二叉树的链表表示leftChilddatapar二叉树链表表示的示例ABCDFEroot

ABCDFEroot

ABCDFEroot二叉树二叉链表三叉链表28二叉树链表表示的示例ABCDFErootABC29二叉链表中结点定义如下：classBinaryTreeNode{DataTypedata;BinaryTreeNode*leftChild,*rightChild;//左指针,右指针public:BinaryTreeNode(DataType&e,BinaryTreeNode*l=NULL,BinaryTreeNode*r=NULL){data=e;leftChild=l;rightChild=r;}};//BinaryTreeNode

二叉树的链表式实现29二叉链表中结点定义如下：二叉树的链表式实现30classBinaryTree{BinaryTreeNode*root;//根结点指针public:BinaryTree(){root=NULL;} //创建一个空的二叉树boolIsEmpty();

//如果二叉树为空，则返回true，否则返回falseboolRoot(DataType&x);

//置x为根结点值；若操作失败，则返回false，否则返回truevoidCreateBinaryTree(BinaryTreeNode*&t=root);

//通过扩充二叉树的前序遍历序列，创建二叉树二叉链表定义如下：30classBinaryTree{二叉链表定义如下：31voidMakeTree(DataType&data，BinaryTree&left，BinaryTree&right);//创建二叉树，data为根结点值，left作为左子树，right作为右子树voidBreakTree(DataType&data，BinaryTree&left，BinaryTree&right);//拆分二叉树voidPreOrder(voidVisit(BinaryTreeNode*&),BinaryTreeNode*&=root);voidInOrder(voidVisit(BinaryTreeNode*&),BinaryTreeNode*&=root);voidPostOrder(voidVisit(BinaryTreeNode*&),BinaryTreeNode*&=root);voidLevelOrder(voidVisit(BinaryTreeNode*&));//逐层遍历//其中，Visit作为遍历的过程参数，负责对结点的访问。31voidMakeTree(DataType&data32voidDelete(BinaryTreeNode*&=root); //删除一棵二叉树，释放其结点。intSize(BinaryTreeNode*&=root); //返回二叉树中结点数。intHeight(BinaryTreeNode*&=root); //返回二叉树的高度。};//BinaryTree基本操作的实现：boolIsEmpty(){//如果二叉树为空，则返回true，否则返回falsereturn(root?true:false);}32voidDelete(BinaryTreeNode*33boolRoot(DataType&x){//置x为根结点值，如果没有根结点，则返回falseif(root){root->data=x;returntrue;}returnfalse;//没有根结点}voidMakeTree(DataType&data,BinaryTree&left,BinaryTree&right){//用left,right和data构成一棵新树，left,right与当前二叉树必须是不同的对象root=newBinaryTreeNode(data,left.root,right.root); //创建新二叉树}33boolRoot(DataType&x){二叉树遍历

二叉树的遍历是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。

设访问根结点记作

V，

遍历根的左子树记作

L，

遍历根的右子树记作

R，

34二叉树遍历二叉树的遍历是按某种次序访问树中的结点可能的遍历次序前序VLR镜像VRL中序LVR镜像RVL后序LRV镜像RLVVLR12335可能的遍历次序前序VLR镜像前序遍历：若BT非空，则：1.访问根；2.前序遍历左子树；3.前序遍历右子树；中序遍历：若BT非空，则：1.中序遍历左子树；2.访问根3.中序遍历右子树；后序遍历：若BT非空，则：1.后序遍历左子树；2.后序遍历右子树；3.访问根遍历算法36前序遍历：中序遍历：后序遍历：遍历算法36--/+*abcdef遍历结果

中序：

a+b*c

-

d

-

e/f

前序：-+a*b-cd/ef

后序：abcd-*+ef/-37--/+*abcdef遍历结果3738ABCDFHGE练习:给出上述二叉树的前序、中序和后序的遍历序列前序遍历序列：ABDGCEFH中序遍历序列：DGBAECHF后序遍历序列：GDBEHFCA38ABCDFHGE练习:给出上述二叉树的前序、中序和后序的39前序遍历的二叉树递归算法voidBinaryTree::preOrder

(BinaryTreeNode*&root){if(root){cout<<root→data;

preOrder(root→leftChild);

preOrder(root→rightChild);}}39前序遍历的二叉树递归算法40二叉树递归的中序遍历算法voidBinaryTree::InOrder

(BinaryTreeNode*&root){if(root){

InOrder(root→leftChild);cout<<root→data;

InOrder(root→rightChild);}}40二叉树递归的中序遍历算法41二叉树递归的后序遍历算法voidBinaryTree::postOrder

(BinaryTreeNode*&root){if(root){

postOrder(root→leftChild);

postOrder(root→rightChild);cout<<root→data;}}41二叉树递归的后序遍历算法利用二叉树后序遍历计算二叉树结点个数intSize(BinaryTreeNode<Type>*&t){if(!t)return0;elsereturn1+Size(t→leftChild)+Size(t→rightChild);}

应用二叉树遍历的事例42利用二叉树后序遍历计算二叉树结点个数intSize(BiintDepth(BinaryTreeNode<Type>*&t){if(!t)return0;elsereturn1+Max(Depth(t→leftChild),

Depth

(t→rightChild));}利用二叉树后序遍历计算二叉树的高度43intDepth(BinaryTreeNode<Ty以递归方式建立二叉树。递归出口：当遇到@时，是空。建立根结点。建立左子树和右子树。二叉树用根字符序列和左右子树的字符序列表示，空树用空格(或某一字符表示)表示。

例如用“@”或用“-1”表示字符序列或正整数序列空结点。利用二叉树前序遍历建立二叉树44以递归方式建立二叉树。利用二叉树前序遍历建立二叉树44如图所示的二叉树的前序遍历顺序为ABC@@DE@G@@F@@@序列是扩充二叉树的前序遍历序列。@是扩充的叶结点，它代表空指针。ABCDEGF@@@@@@@@45如图所示的二叉树的前序遍历顺序为ABCDEGF@@@@@@@46建立二叉树(二叉链表）算法:voidCreateBinaryTree(BinaryTreeNode*&root){/*按前序序列输入二叉树中结点的值(一个字符)，空格字符表示空树，构造二叉链表表示的二叉树.*/

cin>>ch；

if(ch==‘*’)root=NULL；

else{root=newBinTreeNode(ch);//生成根结点

CreateBinaryTree(root->leftChild);//构造左子树

CreateBinaryTree(root->rightChild);//构造右子树

}cout<<“建立成功”;}／／CreateBinaryTree46建立二叉树(二叉链表）算法:遍历二叉树的非递归算法我们先观察一下三种遍历行走的路线前序遍历ABCEFHGDI*********47遍历二叉树的非递归算法我们先观察一下三种遍历行走的路线ABC#########ABCEFHGDI中序遍历48#########ABCEFHGDI中序遍历48&&&&&&&&&ABCEFHGDI后序遍历49&&&&&&&&&ABCEFHGDI后序遍历49&&&&&&&&&ABCEFHGDI*********#########三种遍历的访问位置对比：三种遍历的路线是完全一样的，每个结点都被经过三次但访问时间是不同的；前序：第一次经过时访问中序：第二次经过时访问后序：第三次经过时访问50&&&&&&&&&ABCEFHGDI*********###算法思想非递归中序遍历BinaryTree建立栈stack；P指向根；当p不空或stack不空时反复做： 若p不空,p入栈;p指向左子女； 否则：出栈顶元素到p中；访问p；p指向右子女；4.结束51算法思想非递归中序遍历BinaryTree5152思考：非递归的前序遍历算法？中序遍历BinaryTree算法思想:建立栈Stack；p指向根；当p不空或Stack不空时反复做： 若p不空，p入栈；p指向左子女； 否则：出栈顶元素到p中；访问p；p指向右子女；4.结束前序遍历BinaryTree的非递归算法思想:建立栈Stack；p指向根；当p不空或Stack不空时反复做： 若p不空，访问p

，p入栈；p指向左子女； 否则：出栈顶元素到p中；p指向右子女；结束52思考：非递归的前序遍历算法？中序遍历BinaryTree53ABCDEFGp(1)例

&Aroot53ABCDEFGp54ABCDEFGp&A&B(2)例54ABCDEFGp&A&B(255ABCDEFGp&A&B&C(3)例55ABCDEFGp&A&B&C(3)例56p=NULLABCDEFG&A&B(4)例&C56p=NULLABCDEFG&A&B(4)例&C57ABCDEFG&A&B访问：C(5)例p57ABCDEFG&A&B访问：C(5)例p58ABCDEFG&A&B访问：C(6)例P=NULL58ABCDEFG&A&B访问：C(6)例P=NULL59pABCDEFG&A访问：CB(7)例59pABCDEFG&A访问：CB(7)例60ABCDEFG&A&D访问：CBp(8)例60ABCDEFG&A&D访问：CBp(8)例61ABCDEFG&A&D&E访问：CBp(9)例61ABCDEFG&A&D&E访问：CBp(9)例62ABCDEFG&A&D&E访问：CBP=NULL(10)例62ABCDEFG&A&D&E访问：CBP=NULL(1063ABCDEFG&A&D访问：CBEp(11)例63ABCDEFG&A&D访问：CBEp(11)例64ABCDEFG&A&D访问：CBEp(12)例&G64ABCDEFG&A&D访问：CBEp(12)例&G65ABCDEFG&A&D&G访问：CBEP=NULL(13)例65ABCDEFG&A&D&G访问：CBEP=NULL(66ABCDEFG&A&D访问：CBEGp(14)例66ABCDEFG&A&D访问：CBEGp(14)例67ABCDEFG&A&D访问：CBEGP=NULL(15)例67ABCDEFG&A&D访问：CBEGP=NULL(68ABCDEFG&A访问：CBEGDp(16)例68ABCDEFG&A访问：CBEGDp(16)例69ABCDEFG&A&F访问：CBEGDp(17)例69ABCDEFG&A&F访问：CBEGDp(17)70ABCDEFG

&A访问：CBEGDp=NULL(18)例&F70ABCDEFG&A访问：CBEGDp=71ABCDEFG&A访问：CBEGDFp(19)例71ABCDEFG&A访问：CBEGDFp(19)72ABCDEFG

&A访问：CBEGDFp=NULL(18)例72ABCDEFG&A访问：CBEGDF73ABCDEFG

访问：CBEGDFAp(20)例73ABCDEFG访问：CBEGDF74ABCDEFG

访问：CBEGDFAp=NULL(21)例74ABCDEFG访问：CBEGDF75前序遍历的非递归算法：voidPreOrder(BinaryTreeNode*＆p=root){

BinaryTreeNode*p;Stackstack;//建立栈

while(p||!stack.IsEmpty()){while(p){stack.Push(p);cout>>p->data;

p=p->leftChild;}//向左走else{p=stack.Pop(); p=p->rightChild;}//向右走

}//while}//InOrder

75前序遍历的非递归算法：算法思想

非递归后序遍历1.建立栈stack；2.P指向根；3.当p不空或stack不空时反复做：

若p不空

：(p,L)入栈;p向左走一步；

否则：出栈顶元到p和tag中；若tag==R:访问p；p置空；否则（p,R）入栈；并

p向右走一步；4.结束后序遍历时，访问一个结点的时间是：第3次经过时；第2次返回时；从右边返回时；如何区分从左还是右返回的呢？P入栈时带一标记:向左走时带L向左走时带R76算法思想非递归后序遍历后序遍历时，访问一个结点的时77voidPostOrder(voidVisit(BinaryTreeNode*＆)){//后序遍历BinaryTreeNode*t=root;Stackstack;//建立栈while(t||!stack.IsEmpty()){if(t){stack.Push((t,‘L’));//(t,L)入栈

t=t->leftChild;//t向左走}后序遍历二叉树非递归算法（基于二叉链表存储结构）77voidPostOrder(voidVisit(Bi78else{e=stack.Pop(); //出栈顶元素到e中t=e.t;tag=e.tag;if(tag==‘R’){t->data;t=NULL;}else{stack.Push((t,’R’)); t=t->rightChild; //t向右走} }//if

}//while}//postOrder

78else{e=stack.Pop(); //出栈79例:BEACroot(A.L)入栈(A.L)(B.L)入栈(A.L)(B.L)(B.L)退栈(A.L)(B.R)入栈(A.L)(B.R)(E.L)入栈(A.L)(B.R)(E.L)(E.L)退栈(A.L)(B.R)(E.R)入栈(A.L)(B.R)(E.R)(E.R)退栈(A.L)(B.R) 访问E(B.R)退栈(A.L) 访问B(A.L)退栈(A.R)入栈(A.R)(C.L)入栈(A.R)(C.L)(C.L)退栈(A.R)(C.R)入栈(A.R)(C.R)(C.R)退栈(A.R) 访问C(A.R)退栈 访问A123456789101112131415161234567891011121314151679例:BEACroot(A.L)入栈(A.80已知二叉树的前序遍历序列和中序遍历序列

或二叉树中序遍历序列和后序遍历序列，如何确定一棵二叉树？例：已知一棵二叉树的前序遍历序列：HDACBGFE

中序遍历序列：ADCBHFEG试画出满足以上序列的二叉树？80已知二叉树的前序遍历序列和中序遍历序列例：已知一棵二叉树81例：已知一棵二叉树的中序遍历序列：ADCBHFEG后序遍历序列：ABCDEFGH试画出满足以上序列的二叉树？课堂练习:前序遍历序列：ABDGHJKECFIM中序遍历序列：GDJHKBEACFMI试画出满足以上序列的二叉树81例：已知一棵二叉树的课堂练习:82考虑层次遍历算法LevelOrder？ABCDFHGE层次遍历序列：ABCDEFGH82考虑层次遍历算法LevelOrder？ABCDFHGE83voidBinaryTree<Type>::LevelOrder(

){

//层次遍历二叉树算法

SeqQueuequ;BinTreeNode*p=root;qu.Enter(p);while(!qu.IsEmpty()){p=qu.Leave();cout<<p->data;if(p->leftChild)qu.Enter(p->leftChild);if(p->rightChild)qu.Leave(p->rightChild);}83voidBinaryTree<Type>::Level线索的目的：利用二叉树的空指针保存遍历序列的前驱、后继信息，遍历二叉树时不需要栈。

n个结点的二叉树，有2n个指针，只用了n-1个，有n+1个是空的。用空的左指针指向遍历序列的前驱用空的右指针指向遍历序列的后继这两种指针称为线索(Thread)。线索化二叉树(ThreadedBinaryTree)线索

(Thread)84线索的目的：利用二叉树的空指针保存遍历序列的前驱、后继信息，85例：

n个结点的二叉链表中，有2n个指针，只用了n-1个指针，有n+1个指针是空的。85例：n个结点的二叉链表中，有2n个指针，只用了n-1个86给二叉树加线索的过程是线索化（穿线）；按前序遍历序列线索化的二叉树是前序线索二叉树；按中序遍历序列线索化的二叉树是中序线索二叉树；按后序遍历序列线索化的二叉树是后序线索二叉树；中序线索二叉树简称线索二叉树；86给二叉树加线索的过程是线索化（穿线）；增加Pred指针和Succ指针的二叉树87增加Pred指针和Succ指针的二叉树8788ABCDE

A

B

D

C

Ethrt前序序列：ABCDE前序线索二叉链表二叉树88ABCDEAB89ABCDE

A

B

D

C

E中序序列：BCAED中序线索二叉链表二叉树thrt89ABCDEAB90ABCDE

A

B

D

C

E后序序列：CBEDA后序线索二叉链表二叉树thrt90ABCDEAB线索化二叉树及其二叉链表表示LTag=0,LeftChild为左子女指针LTag=1,LeftChild为前驱线索RTag=0,RightChild为右子女指针RTag=1,RightChild为后继指针LeftChildRightChilddataLTagRTag91线索化二叉树及其二叉链表表示LTag=0,Left92ABCDE

A

B

D

C

E前序序列：ABCDE前序线索二叉链表0000111111二叉树thrt92ABCDEAB93ABCDE

A

B

D

C

E中序序列：BCAED中序线索二叉链表0000111111二叉树thrt93ABCDEAB94ABCDE

A

B

D

C

E后序序列：CBEDA后序线索二叉链表0000111111二叉树thrt94ABCDEAB95DBFEACNILNIL例：（中序）线索化二叉树中序遍历序列：DBFEAC95DBFEACNILNIL例：（中序）线索化二叉树中序遍历96后序线索二叉树前序线索二叉树后序遍历序列：DBECA前序遍历序列：ABDCE96后序线索二叉树前序线索二叉树后序遍历序列：DBECA前序97classThrBNode{DataTypedata;boollTag,rTag;ThrBNode*leftChild,*rightChild;public:ThrBNode(DataTyped){data=d;leftChild=rightChild=NULL;lTag=rTag=false;}};//ThrBNode中序线索二叉链表的类定义97classThrBNode中序线索二叉链表的类定义98classInThrBTree{//Thread_Binary_treeThrBNode*thrt;//头指针ThrBNode*GetFirstNode(ThrBNode*);ThrBNode*GetNextNode(ThrBNode*);ThrBNode*GetNextNodePre(ThrBNode*);

//求在前序序列中的后继

public:

InThrBTree(){thrt=newThrBNode();}

//创建一个带表头但不带线索的空二叉树voidCreateBTree(ThrBNode*&t=thrt);

//创建一个带表头但不带线索的二叉树98classInThrBTree{//Thre99voidMakeTree(DataType&data,InThrBTree&left,InThrBTree&right);//创建一个带表头但不带线索的二叉树，data为根结点值，left和right是左右子树voidInOrderThreading(ThrBNode*&bt=thrt);//线索化voidInOrder(voidVisit(ThrBNode*));voidPreOrder(voidVisit(ThrBNode*));};//InThrBTree99voidMakeTree(DataType&data中序线索二叉树的线索给我们提供了足够的信息，对其进行中序遍历时，既不需要递归（使用了系统栈）也不需要栈1)找到序列的第一个结点p;2)当p非空时：访问p;

找出p的后继r；

p=r;算法思想：关键问题1沿着根的左链走直到无左子女的结点r，即中序序列中的第一个结点p=root;While(!p->ltag)p=p->lchild;关键问题2，有如下两种情况：P无右子女:则p->rchild是p的后继；P有右子女：则p的右子树的中序序列下第一个结点是p的后继，方法同关键问题1。100中序线索二叉树的线索给我们提供了足够的信息，对其进行中序遍历101ThrBNode*GetFirstNode(ThrBNode*p){

//求中序序列中的第一个结点while(!p->lTag)p=p->leftChild;//沿左链走直到无左子女的结点returnp;}//GetFirstNode中序遍历线索二叉链表中基本操作的实现求中序序列中的第一个结点：沿着根的左链走,直到无左子女的结点p，即中序序列中的第一个结点;101ThrBNode*GetFirstNode(ThrB102ThrBNode*GetNextNode(ThrBNode*p)//求p在中序中的后继{if(p->rTag)returnp->rightChild;//P无右子女

r=p->rightChild; //r指向p的右子树的根

r=GetFirstNode(r); //求右子树的第一个结点

returnr;}求p在中序中的后继：P无右子女：则p->rightChild是p的后继；P有右子女：则p的右子树的中序序列下一个结点是p的后继，。102ThrBNode*GetNextNode(ThrBNo103voidInOrder(voidVisit(ThrBNode*)){p=thrt->leftChild; //取根结点

if(p==thrt)return;p=GetFirstNode(p);while(p!=thrt){Visit(p);p=GetNextNode(p);}}//InOrder103voidInOrder(voidVisit(Thr104找到前序序列中的第一个结点:根就是第一个结点.找出给定结点p在前序序列中的后继结点:有如下3种情况：P有左子女：则p左子女是p的后继；否则P有右子女：则p的右子女是p的后继;否则P是叶：沿着p的右线索走，直到头结点或一个有右子女的结点r为止，若到头结点，则p无后继，否则r的右子女是p的后继。在中序线索二叉树上进行前序遍历的非递归算法：104找到前序序列中的第一个结点:找出给定结点p在前序序列中105ThrBNode*GetNextNodePre(ThrBNode*p){//求p在前序序列中的后继结点

if(!p->lTag)returnp->leftChild;//p有左子女

if(!p->rTag)returnp->rightChild;//p有右子女

r=p->rightChild; //p是叶结点

while(r!=thrt&&r->rTag)r=r->rightChild;if(r!=thrt)returnr->rightChild;elsereturnr;}//GetNextNodePre105ThrBNode*GetNextNodePre(Th106在中序线索二叉树上进行前序遍历的非递归算法：voidPreOrder(voidVisit(ThrBNode*)){

p=thrt->leftChild;while(p!=thrt){Visit(p);p=GetNextNodePre(p);}}//PreOrder106在中序线索二叉树上进行前序遍历的非递归算法：void107ABCDE

A

B

D

C

E二叉树的二叉链表0000000000二叉树00^thrt通过中序遍历建立中序线索化二叉链表的算法:^^^^^^^107ABCDEAB108ABCDE

A

B

D

C

E中序序列：BCAED中序线索二叉链表0000111111二叉树00thrt^108ABCDEAB109中序遍历的非递归算法(回忆)voidInOrder(BinaryTreeNode*＆p=root){

BinaryTreeNode*t=p;Stackstack;//建立栈

while(t||!stack.IsEmpty()){if(t){stack.Push(t);t=t->leftChild;}//t向左走else{t=stack.Pop(); cout>>t->data;t=t->rightChild;}//t向右走

}//while}//InOrder

通过中序遍历建立中序线索化二叉链表:109中序遍历的非递归算法(回忆)通过中序遍历建立中序线索化if(current->rTag==1)

后继为current->rightChildelse

//current->rTag!=1

后继为当前结点右子树的中序下的第一个结点

寻找当前结点在中序下的后继ABDECFHIKGJ110if(current->rTag==1)寻找当前结if(current->lTag==1)

前驱为current->leftChildelse

//current->lTag==0

前驱为当前结点左子树

中序下的最后一个结点

寻找当前结点在中序下的前驱ABDECFHIKGJL111if(current->lTag==1)寻找当112voidInOrderThreading(ThrBNode*&bt=thrt){//采用二叉链表存储结构

Stacks;s.InitStack()；p=bt->leftChild;pre＝bt；通过中序遍历建立中序线索化二叉链表的算法:if(p==bt){pre->leftChild=thrt;pre->lTag=true;pre->rightChild=thrt;pre->rTag=true;return;}112voidInOrderThreading(ThrBN113while(p||!s.IsEmpty()){while(p){s.Push(p)；p=p->leftChild;}//向左走到尽头

if(s.IsEmpty()){//访问结点，向右一步

p=s.Pop()；

if(!p->leftChild){p->leftChild=pre;p->lTag=true;}

if(pre!=bt&&!pre->rightChild){pre->rightChild=p;pre->rTag=true;}pre=p;p=p->rightChild；

}//if}//while

pre->rTag=1;pre->rightChild=bt;}

cout<<p->data；113while(p||!s.IsEmpty()){c0A00B00C00D00E0rootpre==NULLcurrent1140A00B00A0

1B00C00D00E0rootpre==NULLcurrent1150A01B00A0

1B00C0

1D00E0rootprecurrent1160A01B00A0

1B00C0

1D1

0E0rootprecurrent1170A01B00A0

1B00C0

1D1

1E0rootprecurrent1180A01B00A0

1B00C0

1D1

1E1

rootprecurrent1190A01B00A0

1B00C1

1D1

1E1

rootpre后处理1200A01B0

双亲表示ABCDEFGdataparentABCDEFG-10001130123456ABCDEFG121树的存储表示树与森林双亲表示ABCDEFGdataparentABABCDEFGABCDEFG

空链域2n+1个

子女表示法122第一种解决方案等数量的链域

data

child1child2child3childdABCDEFGABCDEFG第二种解决方案

datafirstChildnextSiblingABCDEFGABCDGFE123

左子女-右兄弟表示法第二种解决方案datafirstChildnextSib森林与二叉树的转换森林与二叉树的对应关系T1T2T3AFHBCDGIJEK3

棵树的森林T1T2T3AFBCDEGHIKJ各棵树的二叉树表示ABCEDHIKJFG森林的二叉树表示124森林与二叉树的转换森林与二叉树的对应关系T1(1)森林转化成二叉树的规则

若F

为空，即n=0，则对应的二叉树B

为空二叉树。

若F

不空，则对应二叉树

B

的根

root(B)是

F

中第一棵树T1的根

root(T1)；

其左子树为

B(T11,T12,…,T1m)，其中，T11,T12,…,T1m是root(T1)的子树；

其右子树为

B(T2,T3,…,Tn)，其中，T2,T3,…,Tn

是除T1外其它树构成的森林。125(1)森林转化成二叉树的规则125(2)二叉树转换为森林的规则

如果B

为空，则对应的森林F

也为空。

如果B

非空，则

F

中第一棵树

T1

的根为root；

T1

的根的子树森林{T11,T12,…,T1m}是由

root的左子树

LB

转换而来，F中除了T1之外其余的树组成的森林

{T2,T3,…,Tn}

是由

root

的右子树

RB

转换而成的森林。126(2)二叉树转换为森林的规则126树的二叉树表示树的遍历深度优先遍历

先根次序遍历后根次序遍历广度优先遍历ABCDEFGABCEDGF127树的二叉树表示树的遍历深度优先遍历ABCDEFGABCEDG树的先根次序遍历当树非空时访问根结点；依次先根遍历根的各棵子树。树先根遍历ABEFCDG。对应二叉树前序遍历ABEFCDG。树的先根遍历结果与其对应二叉树表示的前序遍历结果相同。树的先根遍历可以借助对应二叉树的前序遍历算法实现。128树的先根次序遍历当树非空时128树的后根次序遍历当树非空时依次后根遍历根的各棵子树；访问根结点。树后根遍历EFBCGDA。对应二叉树中序遍历EFBCGDA。树的后根遍历结果与其对应二叉树表示的中序遍历结果相同。树的后根遍历可以借助对应二叉树的中序遍历算法实现。129树的后根次序遍历当树非空时129(3)广度优先(层次次序)遍历。按广度优先次序遍历树的结果。

ABCDEFGABCDEFG130(3)广度优先(层次次序)遍历。按广度优先次序遍历树的结果森林的遍历森林的二叉树表示ABCDEFGHIKJ(1)先根次序遍历的规则：

若森林F为空,返回；否则

访问F的第一棵树的根结点；

先根次序遍历第一棵树的子树森林；

先根次序遍历其它树组成的森林。ABCEDHIKJFG131森林的遍历森林的二叉树表示(1)先根次序遍历的规则：ABC森林的二叉树表示EDCBGKJIHFA(2)后根次序遍历的规则：

若森林F为空，返回；否则

后根次序遍历第一棵树的子树森林；

后根次序遍历其它树组成的森林；

访问F的第一棵树的根结点。 ABCEDHIKJFG132森林的二叉树表示(2)后根次序遍历的规则：ABCEDHIK森林的二叉树表示AFHBCDGIJEK(3)广度优先遍历(层次序遍历)：

若森林F为空，返回；否则

依次遍历各棵树的根结点；

依次遍历各棵树根结点的所有子女；

依次遍历这些子女结点的子女结点。ABCEDHIKJFG133森林的二叉树表示(3)广度优先遍历(层次ABCEDHIKJHuffman树路径长度(PathLength)

两个结点之间的路径长度PL

是连接两结点的路径上的分支数。树的外部路径长度是各叶结点(外结点)到根结点的路径长度之和EPL。树的内部路径长度是各非叶结点(内结点)到根结点的路径长度之和

IPL。

树的路径长度是根结点到各结点的路径长度之和PL=EPL+IPL134Huffman树路径长度(PathLength的路径长度PL=0+1*2++2*4+3*1=1312345678树的路径长度PL=0+1*2+2*2++3*2+4*1=1613512345678树的路径长度12345678树的路径长度13

n个结点的二叉树的路径长度不小于下述数列前n项的和，即其路径长度最小者为136n个结点的二叉树的路径长度不小于其路径长度最小者为136带权路径长度

(WeightedPathLength,WPL)树的带权路径长度是树的各叶结点所带的权值与该结点到根的路径长度的乘积的和。扩充二叉树各叶结点带有权值。137带权路径长度(WeightedPathLength,具有不同带权路径长度的扩充二叉树WPL=2*2+4*2+5*2+7*2=3624572457WPL=7*1+5*2+2*3+4*3