第三学期-2课件数据结构7-chap

1第五章树5.1

树的概念5.2

二叉树5.3二叉树的遍历5.4二叉树其它运算5.7树的 结构和运算退出5.1树的概念5.1.1

树的定义树的递归定义：（1）树由具有相同特性的数据元素（称为结点）组成，结点个数为0时，称为空树；

（2）在一棵非空树中有且仅有一个根root结点，除根结点外，其余结点可分为m(m≥0)个互不相交的子集，每个子集也是一棵树，称为子树SubTree。2AXBE

F

GA的第1棵子树CHI

JA的第3棵子树

A的第2棵子树树(逻辑上)的特点有且仅有一个结点没有前驱结点,该结点为树的根结点。除了根结点外,每个结点有且仅有一个直接前驱结点。包括根结点在内，每个结点可以有多个后继结点。35.1.3基本名词术语4结点的度：树的度：叶结点：分支结点:层次的定义:树的深度:

树林(森林):树的有序性:5.2二叉树55.2.1

二叉树的定义二叉树为度为2的有序树。递归定义：或者是一棵空树，或者是一棵由根结点和两棵互不相交的左、右子树组成的非空树。左、右子树同样也是二叉树。左孩子leftchild，左子树的根结点。右孩子right

child，右子树的根结点。两种特殊形态的二叉树满二叉树若一棵二叉树中的结点,或者为叶结点， 或者具有两棵非空子树,

并且叶结点都集中在二叉树的最下面一层.

这样的二叉树为满二叉树.完全二叉树若一棵二叉树中只有最下面两层的结点的度可以小于2,并且最下面一层的结点(叶结点)都依次排列在该层从左至右的位置上。这样的二叉树为6

完全二叉树.一棵非空二叉树的第i

层最多有2i–1个结点(i1)。5.2.2二叉树的性质深度为h

的非空二叉树最多有2h

-1个结点.若非空二叉树有n0个叶结点,

有n2个度为2的结点,则

n0=n2+17具有n个结点的完全二叉树的深度h=log2n+1.若对具有n个结点的完全二叉树按照层次从上到下,每层从左到右的顺序进行

,

则 为i

的结点具有以下性质:(1)

若 为i的结点有左孩子,则左孩子结点的若 为i

的结点有右孩子,则右孩子结点的为2i;为2i+1.(2)除树根结点外,若一个结点的标号为i,则它的双亲结点的为i/2,为i/2,也就是说,当i为偶数时,其双亲结点的它是双亲结点的左孩子,当i为奇数时,其双亲结点的为(i-1)/2,它是双亲结点的右孩子.若i≦|_n/2_|,即2i

≦

n

,

则

为i

的结点为分支结点,否则为叶子结点.若n为奇数,则每个分支结点都既有左孩子,又有右孩子;若n为偶数,则 最大的分支结点( 为n/2)只有左孩子,没有右孩子,其余分支结点左、右孩子都有.895.2.3

二叉树的抽象数据类型ADT

BinaryTreeData：

类型BTreeType，用BT标识符表示Operations：void

InitBTree(BTreeType

&BT);//初始化一棵二叉树，即置为空树void

CreateBTree(BTreeType&

BT,

char*

a);//根据字符串a建立一棵二叉树int

BTreeEmpty(BTreeType

BT);//判断一棵二叉树是否为空树voidTraverseBTree(BTreeType

BT);//按照一定次序遍历二叉树int

BTreeDepth(BTreeType

BT);//求一棵二叉树的深度void

PrintBTree(BTreeType

BT);//按照一种表示方法输出二叉树void

ClearBTree(BTreeType&

BT);//清除二叉树中所有结点，使之为空树end

BinaryTree5.2.4二叉树的 结构一.顺序 结构二.链式 结构10115.3

二叉树遍历DLR前序(根)遍历

LDR中序(根)遍历

LRD后序(根)遍历层次遍历如何由遍历序列恢复二叉树？规律(

前,

中):

规律(

中,

后):序序列中找根;到中序序列中分左右。在后序序列中找根;到中序序列中分左右。125.4二叉树的其它运算初始化二叉树建立二叉树判断一棵二叉树是否为空树求二叉树的深度查找二叉树中值为x的结点输出二叉树清除二叉树,使之变为一棵空树135.5

树的

结构和运算树的顺序

结构树的

结构1、标准形式2、广义标准形式3、二叉树表示形式14156.1二叉排序/搜索树6.1.1

二叉排序/搜索树的定义二叉排序树Binary

Sort

Tree：或者为一棵空树，或者为具有下列特性的非空树：1、若其左子树非空，则左子树上的所有结点的关键字值均小于根结点关键字值；2、若其右子树非空，则右子树上的所有结点的关键字值均大于等于根结点关键字值；3、其左、右子树分别为二叉排序树。16对它进行中序遍历：12，15，18，23，26，30，52，63，74得到有序序列17二叉搜索树的建立(逐点

法)若二叉树为空,则ki

作为该二叉树的根结点；若二叉树非空,

则将ki

与该二叉树的根结点的值进行比较,

若ki

小于根结点的值,

则将ki到根结点的左子树中;

否则,

将ki

到根结点的右子树中。18例1

K

=

(

50,

35,

70,

40,

50,

65,

20,

80

)4070355050

50

5035

35

7040

507035506540

507035506520

40

507035506520

40

50

80703550193090^

100

^T50^10^70

^^

60

^p^80^p^80^item=80206.1.2

二叉搜索树的抽象数据类型ADT

BinaryTreeData：一棵二叉搜索树，结点的类型BTreeNode，指向二叉排序树的树根结点的指针为BSTOperations：查找、更新、

和删除end

BinaryTreestruct

BTreeNode{ElemType

data;BTreeNode

*left,

*right;};21int

Find(BTreeNode*

BST,

ElemType&

item);//查找关键字值等于item.key的数据元素，成功返回真//并由item返回元素值。int

Update(BTreeNode*

BST,

cons emType&

item);//查找关键字值等于item.key的数据元素，成功返回真//并用item重写数据元素值。void

Insert(BTreeNode*

&BST,

cons emType&

item);//根据关键字值item.key向二叉排序树

数据元素。int

Delete(BTreeNode*

&BST,

cons emType&

item);//删除关键字值为item.key的第一个数据元素。226.1.3

二叉搜索树的运算1查找2更新34删除23241二叉搜索树的查找查找关键字值等于item.key的数据元素，成功返回真，并由item返回元素值。int

Find(BTreeNode*

BST,

ElemType&

item){//递归算法

if(BST==NULL)return

0;else

{if(item.key==BST->data.key){item=BST->data;return

1;

}else

if(item.key<BST->data.key)return

Find(BST->left,item);elsereturn

Find(BST->right,item);}}算法的空间和时间复杂度为O(log2n)~O(n)，平均为O(log2n)int

Find(BTreeNode*

BST,

ElemType&

item){//非递归算法while(BST!=NULL){if(item.key==BST->data.key){item=BST->data;return

1;}else

if(item.key<BST->data.key)BST=BST->left;elseBST=BST->right;}return

0;}算法的时间复杂度同递归算法O(log2n)~O(n)，空间复杂度为O(1)。25262二叉搜索树的更新查找关键字值等于item.key的数据元素，成功返回真，并用item重写数据元素值。int

Update(BTreeNode*

BST,

cons{if(BST==NULL)

return

0;else

{emType

item)if(item.key==BST->data.key){BST->data=item; return

1;}else

if(item.key<BST->data.key)return

Update(BST->left,item);elsereturn

Update(BST->right,item);

}}3

二叉搜索树的根据关键字值item.key向二叉排序树 数据元素。void

Insert(BTreeNode*&

BST,

cons{if(BST==NULL){emType&

item)BTreeNode*

p=new

BTreeNode;p->data=item;p->left=p->right=NULL;BST=p;}else

if(item.key<BST->data.key)Insert(BST->left,item);elseInsert(BST->right,item);}算法的时间复杂度同查找操作。27void

Insert(BTreeNode*&

BST,

cons emType&

item){ //非递归算法BTreeNode*

t=BST,*parent=NULL;//指针t指向待比较的结点while(t!=NULL){ //指针parent为t的双亲结点parent=t;if(item.key<t->data.key)t=t->left;elset=t->right;}//建立新结点pBTreeNode*

p=new

BTreeNode;p->data=item;p->left=p->right=NULL;if(parent==NULL)BST=p;else

if(item.key<parent->data.key)parent->left=p;elseparent->right=p;28}29生成一棵具有n个结点的二叉搜索树的算法void

CreateBSTree(BSTree

*&

BST,

ElemType

a[],

int

n){BST=NULL;for

(inti=0;

i<n;

i++)Insert(BST,

a[i]);}一般而言，时间复杂度为O(n*log2

n)4

二叉搜索树的删除(本小节作为 内容)1、删除的结点为叶子结点；2、删除的结点为单支结点；3、删除的结点为双支结点：查找待删除结点的中序前驱结点；将前驱结点的值赋予待删除结点；用前驱结点的左子树根结点代替前驱结点。30调用二叉搜索树算法的程序举例void

main(){student

a[8]={{30,50},{20,70},{25,80},{23,40},{28,50},{15,90},{60,12},{48,60}};BTreeNode*

bst=NULL;student

x={28};student

y={20,37};CreateBSTree(bst,a,8);cout<<"中序遍历："<<endl;Inorder(bst);cout<<endl;cout<<"深度为："<<BTreeDepth(bst)<<endl;if(Find1(bst,x))cout<<“查找成功！得到x为：(”<<x.key<<",“;cout<<x.rest<<')'<<endl;31if(Update1(bst,y)){cout<<"更新成功！"<<endl;Inorder(bst);cout<<endl;}Delete(bst,x);Delete(bst,y);cout<<“删除关键字为28和20的元素后中序遍历为：

”;cout<<endl;Inorder(bst);cout<<endl;cout<<"删除后深度为："<<BTreeDepth(bst)<<endl;}326.2

堆堆（heap）分为小根堆和大根堆两种，对于小根堆，它是具有如下特性的一颗完全二叉树：1、若树根存在左孩子，则根节点的值小于等于左孩子结点的值；2、若树根存在右孩子，则根节点的值小于等于右孩子结点的值；3、以左、右孩子为根的子树又各是一个堆。331826357348

607453422536

352018221、宜采用顺序2、查找最大值或最小值最为方便3、

或删除一个结点的时间复杂度为O(lbn)小根堆大根堆346.3

树6.3.1

基本术语1、结点之间的路径和路径长度从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支的数目即称作这两个结点之间路径长度。2、结点的权和带权路径长度从根结点到结点的路径长度与结点的权的乘积。3、树的带权路径长度树中所有叶子结点的带权路径长度之和，记作nWP

L

wi

lii

135LWPSGAMDF36图6-8

三棵不同的带权二叉树37带权路径长度分别为（a）

WPL

=

7x2+

5x2+2x2

+

4x2=

36（b）

WPL

=

7x3

+

5x3

+2x1

+

4x2=

46（c）

WPL

=

7x1+

5x2+2x3+

4x3=

35可以验证c为 树。384、

树（Huffman）树，又称最优树，是一种带权路径长度WPL最小的二叉树。利用

树可以得到最佳判定算法，例如编制一个将学生成绩百分制转换成五级分制的程序：分数0-5960-6970-7980-8990-100比例数0.050.150.400.300.10假设以5，15，40，30和10为权，构造一棵带有五个叶子结点的

树，则得到图

(b)所示判定过程。39(b)所示判定过程可使大部分数据经过较少的比较次数即可得到结果。406.3.2

构造

树1、根据给定的n个权值{w1，w2，…，wn}，构成n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均为空；2、在F中选取两棵根结点的权值最小的树作为左右子树构成一棵新的二叉树，且设新的二叉树的根结点的权值为其左右子树上根结点的权值之和；3、在F中删除这两棵树，同时将新得到的二叉树加入到F中；4、重复步骤2、3，直到F中只含一棵树为止。此即为树。41426.3.3

编码从根结点到叶子结点所经分支的

0、1编码序列，代表叶子结点字符的编码。等长编码：任一字符的编码长度相同无前缀编码：任一字符的编码都不是其它字符编码的前缀所有的编码都是无前缀编码43树构造的用于通信的二进制编码：利用编码。编码称为用编码传送的电文长度最短：L为电文中字符总个数，wk某一字符在电文中出现次数，lk字符编码长度。nL

WPL

k

1wklk44例、已知某系统在通信联络中只可能出现八种字符，其概率分别为0.05,

0.29,

0.07,

0.08,

0.14,

0.23,

0.03,

0.11设计

编码。设w=(5,29,7,8,14,23,3,11),n=845设w=(5,29,7,8,14,23,3,11),

n=846编码特点1、无前缀编码2、对应的 树不存在度数为1的结点476.44849中序序列：D,

B,

J,

E,

A,

H,F,

I,

C,

G按照某种遍历顺序遍历一棵二叉树，得到的序列可以看作一个线性表。表中结点有确定的前驱和后继，如中序遍历序列中，一个结点有其中序前驱结点，中序后继结点。一.线索二叉树利用二叉链表中空的指针域

结点在遍历序列中的直接前驱和直接后继;

这些指向前驱和后继的指针称为线索,

加了线索的二叉树称为线索二叉树.二.线索二叉树的构造利用链结点的空的左指针域存放该结点的直接前驱的地址,空的右指针域存放该结点直接后继的地址;

而非空的指针域仍然存放结点的左孩子或右孩子的地址.50ABCDEFJITGHABCDEFJITGH中序