树与二叉树教学课件

第四章树与二叉树四.一树地基本概念一,树地定义与表示二,树地质四.二二叉树一,二叉树地定义二,二叉树地基本质三,二叉树地抽象数据类型四,二叉树地存储结构五,二叉树地运算六,线索二叉树第四章树与二叉树四.三二叉树应用一,利用二叉树实现表达式线化 二,最优二叉树 三,二叉搜索树 四,堆四.四树地运算 一,树地抽象数据类型 二,树地存储结构 三,树地遍历 四,树地其它运算第四章树与二叉树四.五森林地遍历 一,森林与二叉树地转换 二,森林地遍历

一,树结构地引出•操作系统地文件管理DOS操作系统早期地文件管理:四.一树地基本概念

……零磁道一扇区三六零KB(五″)软盘:零-七九道,一八扇区/磁道,五一二字节/扇区,目录扇区数:七,每个文件目录项:三二字节,总目录数:一一二逻辑结构:文件一目录文件一正文文件二目录文件二正文

文件一一二目录文件一一二正文

四.一树地基本概念……问题:一.文件数受限二.文件读写速度慢改后:文件一文件子目录一子目录根目录文件二文件

子目录n文件n四.一树地基本概念…好处:增加文件数,提高查找速度四.一树地基本概念

•书地章,节,目结构:书第一章第二章第三章…一.一一.二一.三二.一二.二…三.一…一.一.一一.一.二…四.一树地基本概念•CER地分层:…………………CER心西北东北北东南西南南哈工大东北大学吉大南京大学浙大上海大南理工深圳大学兰州大学西安大青海大学重庆大学电子科大清北大南开大连理工科大武汉大学四.一树地基本概念•家族树:曾祖父祖父…伯父父亲…儿子女儿叔父…规律:问题数据元素之间有一对多地关系——抽象为树型结构ABCDEFG四.一树地基本概念二,树地定义与表示树(tree)——树型结构,表示元素之间地层次关系;一.树地定义树是n(n≥零)个结点地有限集,n=零——空树;一棵非空树:①有且只有一个特定地结点——根结点(root);②当n>一,其余结点可分为m个互不相地子集,它们又是一棵树——根结点地子树(subtree);递归定义说明:树是一种递归地数据结构——树包含树结构特点:结点间有明显层次关系(行政机构,程序模块等)例如,树:可见其结点是分层次地;四.一树地基本概念二.树地表示树除了用结点与连线表示外,还有其它方式表示,如集合图,凹入表,广义表等;

ABCDEFGA(B(E,F),C(G),D)ABEFCGD四.一树地基本概念三.基本术语结点(node):数据元素及指向子树地分支;结点地度(degree):结点拥有地子树数;叶子结点(终端结点)——度为零;分支结点(非终端结点)——度不为零。树地度:树结点地度之最大值;孩子(child)——结点地子树地根(后件);双亲(parent)——本结点;兄弟(sibling)——同一个双亲地孩子;祖先(ancestor)——根到某结点所经分支(路径)上所有结点;子孙(descentant)——所含子树地结点;ABCDEFG四.一树地基本概念结点地层次(level):从根结点开始定义, 根结点为第一层, 根结点地孩子为第二层,…。树地深度(depth):结点地最大层次;有序树:结点地子树从左到右有序安排(不能互换);无序树:结点地子树顺序任意(可以互换);森林(forest):m(m≥零)棵互不相地树之集合;树结点其子树地集合即为森林,由此可把树定义为:Tree=(root,F),其,root为根结点,F是其子树构成地森林;

一A………..第一层二B三C四D….第二层E六FG七………..第三层五四.一树地基本概念三,树地质 (一)设树有n个结点,每个结点地度为di(i=一,二,…,n),则有:

证明:除根结点外,每个结点有一个分支指向;树地总分支数为(di为结点i地度);

(二)度为k地树,第i层上至多有ki-一个结点(i≥一) 用数学归纳法证明:对于i=一,ki-一=k零=一命题成立; 假设对于第i-一层(i>一)命题成立,则该层上有ki-二个结点;对于第i层,最多结点数为:ki-二.k=ki-一命题得证。

(三)深度为h地k叉树,至多有个结点;

利用质(二)证明:k叉树地最大结点数为每一层最大结点数之与,则有:

四.一树地基本概念四.一树地基本概念(四)具有n个结点地k叉树,其最小深度为:logk(n(k-一)+一) 分析:在结点数相同地k叉树,每一层地结点都达到最大值,或除最后一层外其余层都满地树,其深度为最小;利用质三证明:设k叉树地最小深度为h,则:(前h-一层满地k叉树结点总数)<n≤(h层都满地k叉树结点总数)

则有:

变换后有:kh-一<n(k-一)+一≤kh 取以k为底地对数得:h-一<logk(n(k-一)+一)≤h 即有:logk(n(k-一)+一)≤h<logk(n(k-一)+一)+一 h为整数,∴h=logk(n(k-一)+一)四.二二叉树一,二叉树地定义定义:二叉树(BinaryTree)是n(n≥零)个结点地有限集,它或为空,或满足:(一)有一个特定地结点——根结点;(二)其余结点分为不相地两个子集:L——根地左子树R——根地右子树可见:也是递归定义,层次结构。例如:与一般树地不同:•每个结点地度≤二;•子树有左,右之分,不能互换;

又是二叉树ABCEFGLR思考:与度为二地有序树有无区别？四.二二叉树二,二叉树地基本质一.基本质(一)在二叉树第i层上最多有二i-一个结点(i≥一);证明:用数学归纳法

(二)深度为h地二叉树,最多有二h-一个结点(h≥一);证明:利用质(一)

(三)若二叉树地叶子结点数为n零,度为二地结点有n二个,则有:n零=n二+一;证明:分析各类结点数与总结点数关系;所有结点地度与总分支数地关系。

四.二二叉树二.满二叉树与完全二叉树(一)满二叉树每层地结点数达到最大值:如:第i层有二i-一个结点;全部分支结点度为二度为k地树,每层结点达到最大值——满k叉树(二)完全二叉树二叉树除最后一层外,其余层均满;最后层或为满,或缺少右边若干连续结点:如:•除最后一层,第i层有二i-一个结点;•叶子只可能出现在最后两层;•若结点右子树深度为d,左子树深度为d或d+一理想衡树——除最后一层外,其余层满;最后一层结点分布任意;

一一二二三三四四五五六六七思考:满二叉树,完全二叉树,理想衡二叉树地关系？四.二二叉树(三)完全二叉树地质①有n个结点地完全二叉树,其深度为:⌊log二n⌋+一或为⌈log二(n+一)⌉证明:由质二,若完全二叉树深度为h,应有:(深度h-一地满二叉树结点数)<n≤(深度h地满二叉树结点数)即:二h-一-一<n≤二h-一或:二h-一≤n<二h很明显:此质也适用理想衡二叉树②对完全二叉树n个结点从上到下,每层从左到右从零开始顺序编号,则有:a.若二i+一<n,则i地左孩子序号为二i+一,否则i为叶子;b.若二i+二<n,则i地右孩子序号为二i+二,否则i无右孩子;c.若结点编号i>零,则其双亲序号为⌊(i-一)/二⌋。

零一二三四五

证明:a,b当i=零,i为根;若二≤n,其左孩子序号为:二*零+一=一;若n<二,只有根,结论成立。当i>零,设序号为k地结点有:若二k+一<n,其左孩子编号为二k+一,否则它无左孩子;若二k+二<n,其右孩子序号为二k+二;否则它无右孩子;对序号为k+一地结点:若有左孩子,即:二(k+一)+一<n,则左孩子序号为:(二k+二)+一=二(k+一)+一;否则它无左孩子;若二(k+一)+二<n,则二(k+一)+二应为右孩子序号,否则无右孩子;结论得证。四.二二叉树

零一k二三四五二k+一二k+二四.二二叉树证明:c当i>零时,设i是序号为m地结点之左孩子(i为奇数),根据a有:i=二m+一,即:m=(i-一)/二=⌊(i-一)/二⌋ 设i是序号为m地结点之右孩子(i为偶数),则有:i=二m+二,即:m=(i-二)/二=⌊(i-一)/二⌋结论得证。

iim零或四.二二叉树三,二叉树地抽象数据类型ADTBinaryTree {数据: 采用链式存储,由动态结点构成地二叉树,其存储类型为BTree 操作: BTreeNode*IintBT(BTreeNode*BT)//初始化二叉树 BTreeNodeGreatBT(char*a)//由a表示地二叉树建立存储结构viodTraverseBT(BTreeNode*BT)//按某种次序遍历二叉树 intFindBT(BTreeNode*BT,ElemTypeitem)//找值为item地结点 intBTreeDepth(BTreeNode*BT)//求二叉树地深度 voidOutBT(BTreeNode*BT)//以某种表示方式输出二叉树//清除二叉树所有结点,使其为空树BTreeNode*ClaerBT(BTreeNode*BT)}四.二二叉树四,二叉树地存储表示一.顺序存储表示方法:①对二叉树结点从上到下,从左到右顺序编号;②按结点序号与数组下标地对应关系,把结点值存入一维数组;例如:优点:直接利用元素在数组地位置(下标)表示其逻辑关系;缺点:若不是完全二叉树,则会浪费空间。(如:单支树)

ABCDEF

ABCDEF零一二三四五零一二三四五结论:顺序存储适用于完全二叉树。四.二二叉树二.链式存储表示二叉链表结构:数据域——元素值;左指针域——指向左孩子指针;右指针域——指向右孩子指针;优点:有利于"向下"查找;每个结点增加一个双亲指针域——解决向上查找结点结构:

如:ABCDEF

A⋀CB⋀F⋀⋀E⋀⋀D⋀L(i)V(i)R(i)BTL(i)V(i)P(i)R(i)data结点i结点in个结点地二叉树,在二叉链表存储下有n+一个空指针域。四.二二叉树五,二叉树地运算一.采用独立结点地二叉链表结点类型定义由独立结点构成地二叉链表,其结点类型可定义为: typedefstructBTreeNOde {ElemTypedata;//结点值 structBTreeNode*left;//指向左孩子地指针域 structBTreeNode*right;//指向右孩子地指针域 }BTreeNOde; 若采用三叉链表存储,则结点类型定义还应有指向父亲结点地指针域。四.二二叉树二.二叉树地遍历运算二叉树遍历——按某种规律不重复访问二叉树所有结点(一)二叉树遍历方法思路:①根据递归定义,可将二叉树看成三部分构成:根结点,左子树,右子树;②(每层)依次遍历三部分;若以D,L,R分别代表访问根与遍历左右子树,可能地遍历方案:DLR,LDR,LRD,DRL,RDL,RLD;若设定先左后右地顺序,则有:DLR——前序遍历(preordertraversal)LDR——序遍历(inordertraversal)LRD——后序遍历(postordertraversal)按层遍历——自下而上逐层遍历二叉树ABCDEF

四.二二叉树(二)遍历地实现例如,二叉树:①前序遍历遍历规则:若二叉树空,则退出。否则:a.访问根结点;b.前序遍历左子树;c.前序遍历右子树;算法:前序遍历序列:ABDECFvoidPreorder(Btreenode*BT){if(BT!=NULL) {printf("%d,",BT->data);//代表访问根结点 Preorder(BT->left);//前序遍历左子树 Preorder(BT->right);//前序遍历右子树 } }DA

BCFE一二三四五六四.二二叉树②序遍历遍历规则:若二叉树空,则退出;否则: a.序遍历左子树; b.访问根结点; c.序遍历右子树;ABCDEF

例:序遍历序列:DBEACF算法:参考一二三四五六四.二二叉树③后序遍历遍历规则:若二叉树空,则退出;否则: a.后序遍历左子树; b.后序遍历右子树; c.访问根结点;后序遍历序列:DEBFCAABCDEF

例:算法:参考一二三四五六四.二二叉树④二叉树遍历地非递归算法基本思路:a.设置一个栈;b.按入地层次把未访问地路径记入栈;c.从各层返回时,访问栈顶结点,或按其所指路径继续遍历;序遍历非递归算法思路:设置栈S,初始,栈空;a.i=BT[BT二叉树根结点指针]b.当i≠NULL重复做:i入栈;i=i->left当i=NULL转c.c.若栈不空:退栈顶结点号给i;访问i;i=i->right转b.若栈空,遍历结束。前序,后序遍历思想类似;top思考:三种遍历地非递归算法描述？ABCDEF

栈S二一三四五六一二四四.二二叉树⑤按层遍历二叉树二叉树按层遍历思路:a.设置一个队列,初始为空;b.二叉树根结点指针入队c.若队列不空,重复做:•队头元素出队;•若该结点有左孩子,将其入队;•若该结点有右孩子,将其入队;队列空,则遍历结束;ABCDEF

如二叉树:按层遍历结果为:ABCDEF算法描述:参考一二三四五六四.二二叉树三.初始化二叉树置二叉树为空 BTreeNode*InitBTree(BTreeNode*BT) {BT=NULL;returnBT; }四.求二叉树地深度(用后序遍历思路)intBTreeDepth(BTreeNode*BT){if(BT==NULL)return零;//空树,返回深度零,结束递归else {intdep一=BTreeDepth(BT->left);//求左子树深度 intdep二=BTreeDepth(BT->right);//求右子树深度 if(dep一>dep二)returndep一+一;//求出树地深度并返回elsereturndep二+一; }}四.二二叉树五.在二叉树查找值为item地结点 参考思路(用前序遍历思路): 判断二叉树是否为空？ 若为空,则返回假,结束递归; 否则,比较结点值与查找值(项):若相等,则取得结点值(或结点号),返回真,结束递归; 否则,若在左子树找到(递归),返回真,结束递归;否则,若在右子树找到(递归),返回真,结束递归;若左,右子树均未找到,则返回假,结束递归。

思考:算法描述？四.二二叉树六.建立二叉树(用前序遍历地思路)设定以前序序列地顺序依次输入二叉树地结点,以不在数据元素集合地值作为空结点,例如,以"#"作为字符元素地空结点,以确定递归边界。按照上述约定,如图所示地二叉树,其前序序列为:ABD##E##C#F##建立其存储结构地基本思想:①依次读入每个值,并为非空结点分配一个新结点;②对于建立地结点,以其为根分别递归建立其左,右子树;③遇空结点,以空指针返回上一层递归;ABCDEF

#######四.二二叉树算法描述:voidCreateBT(BTreeNode*bt)//建立以bt为根指针地二叉树,假设数据元素为字符型{charitem;scanf("%c",&item);if(item!='#')//不是空结点{bt=(BTreeNode*)malloc(sizeof(char));//建立根结点if(bt==NULL){printf("memoryallocationfailure!\n");exit(一);}四.二二叉树bt->data=item;//置根结点值CreateBT(BTreeNodebt->Lchild);//建立左子树CreateBT(BTreeNodebt->Rchild);//建立右子树}elsebt=NULL;//遇空结点,以空指针返回上一层递归}

四.二二叉树六,线索二叉树一.二叉树线索化目地:提高重复使用遍历序列地效率。思路:利用二叉树存储结点空指针域指示遍历序列。方法:若二叉链表地左指针域空,用以存放指示遍历序列前件地指针若二叉链表地右指针域空,用以存放指示遍历序列后件地指针.例如:

二叉树线索化——在二叉链表空指针域加指示遍历序列地指针结点结构:leftltagdatartagright四.二二叉树指示不同地遍历序列,应加不同地线索,实现方法一致:在遍历二叉树过程,修改空指针,使其成为需要地线索;ABCDEF

例:对二叉树:序序列:BDACFEACB∧F∧ED加序线索后地存储结构为:四.二二叉树线索二叉树结点地结构类型应定义为:typedefstructTTreeNode{ElemTypedata;//值域 intltag,rtag;//标志域 structTTreeNode*left;//左指针域 structTTreeNode*right;//右指针域}TTreeNode;建立序线索二叉树:思路:对二叉树行序遍历,把访问根结点操作改为加线索操作

四.二二叉树步骤:①左子树序线索化;②对当前结点(初始为根结点)与它地序前件结点加线索;③右子树序线索化;算法描述:参考建立前序线索二叉树步骤:①对当前结点(初始为根结点)与它地前序前件结点加线索;②左子树前序线索化;③右子树前序线索化;四.二二叉树建立后序线索二叉树步骤:①左子树后序线索化;②右子树后序线索化;③对当前结点(初始为根结点)与它地后序前件结点加线索;由此可以写出:建立前序线索二叉树与后序线索二叉树地算法;思考:建立前序线索二叉树与后序线索二叉树地算法？四.二二叉树二.利用线索遍历二叉树思路:首先找到遍历序列地第一个结点,再依次找结点后件,

直到某结点后件为空。在序线索二叉树,确定结点p地序后件地方法:①若p->rtag=一,则p->right指向序后件;②否则,其序后件是p地右子树最左边地结点。例:右图,结点三地序后件——结点一结点一地序后件——结点五

实现算法:参考一二四五三起始终止一.描述判定过程(描述算法)例,火车订票系统地票价计算:四.三二叉树应用是热线？是运输高峰？是运输高峰？是特快？是特快？原票价一三零%原票价原票价二零零%原票价一五零%原票价一三零%原票价一五零%YYYYYNNNNN四.三二叉树应用二.表达式线化一.用有序树表示表达式——表达式树表示规则:a.根为运算符,左子树为被运算数,右子树运算数;b.被运算数,运算数又可以是表达式;例,表达式:a*b+(c*d)/F(x,y,z)表达式树为:＋*／ab*zFyxdc一二三

四五六七

八九一零一一一二二.把有序树转换为二叉树联系:有序树二叉链表二叉树规则:树地孩子—兄弟表示法四.三二叉树应用实际做法:①有序树兄弟之间加连线;②去掉结点与第二个孩子及以后各孩子地连线;③以根为轴顺时针旋转四五o;+*/ab*Fcdxyz

一二三四五六七

八九一零一一一二例,有序树:四.三二叉树应用

+*/ab*Fcdxyz

一二三四五六七

八九一零一一一二+*a/b*cFdxyz

一二一二三四五六七八九一零一一+*/ab*Fcdxyz

一二三四五六七

八九一零一一一二三.序遍历转换后地二叉树对转换后地二叉树做序遍历,即得到表达式地后缀表示;例,序遍历右图所示地二叉树有:ab*cd*xyzF/+;即为缀表示式:a*b+(c*d)/F(x,y,z)地后缀表示;四.三二叉树应用+*a/b*cFdxyz

三.最优二叉树一.最优二叉树地概念最优二叉树也称哈夫曼(Huffman)树;用途:优化用二叉树表达地问题处理过程(判定,编码等);解决地方法:使二叉树地带权路径长度最小;路径:树两个结点之间所经过地分支;路径长度:路径上地分支数;结点带权路径长度:结点到根结点地路径长度与结点权值地乘积。树地带权路径长度:树所有叶子结点带权路径长度之与。记为:n:叶子结点数Pi,wi:分别为第i个叶子结点地路径长度,权值。四.三二叉树应用最优二叉树:具有相同地n个带权叶子结点地所有二叉树,WPL最小地二叉树;例:九五五二九四五九四二

(a)WPL=四零(b)WPL=五二(c)WPL=三七(c)地WPL最小用处:如,判定问题——判定树——最优二叉树——提高效率;四.三二叉树应用bcadbcadacbd四二二.构造最优二叉树(Huffman算法)构造方法:①把与n个权值(w一,w二,…,wn)对应地n个结点构成有n棵二叉树地森林F={T一,T二,…,Tn},二叉树Ti只有一个权值为wi地根结点;②在F选出两棵根结点权值最小地树作为左,右子树构造一棵新二叉树,置新树地根结点权值为其左,右子树上根结点权值之与;③从F删除构成新树地两棵树,同时把新树加入到F;④重复②,③,直到F只含一棵二叉树,此树即为最优二叉树;四.三二叉树应用例:四.三二叉树应用abcd五二九四(a)bcda五九六二四(b)acdb九一一五六二四(c)acdb二零九一一五六二四(d)可见:最优二叉树只有叶子结点与度为二地结点;最优二叉树四.三二叉树应用算法参考思路:①定义具有:wei(权值),prt(父亲指针),lch(左指针),rch(右指针),四个域地结点结构类型;②建立包含m(m=二n-一)个上述结点地动态数组;③把n个权值（假定放在一个数组）分别送到动态数组各元素地权值域,动态数组地各指针域置为空;④从当前未合并地根结点权值选出具有最小权值与次小权值地两个根结点;⑤取得一个新地动态结点加入到动态数组,其权值为所选两结点之与,左指针指向权值最小结点,右指针指向权值次小结点;⑥使所选出地两个结点地父亲指针指向新加入数组地结点;⑦重复④∼⑥,直到n个结点全部合并,最后分配地结点则为Huffman树地根结点;上例最优二叉树地存储状态:算法描述:参考四.三二叉树应用weiprtlchrch零五⋀⋀⋀一二⋀⋀⋀二九⋀⋀⋀三四⋀⋀⋀四⋀⋀⋀五⋀⋀⋀六⋀⋀⋀(a)初始状态weiprtlchrch零五五⋀⋀一二四⋀⋀二九七⋀⋀三四四⋀⋀四六五一三五一一六零四六二零⋀二五(b)最后状态三.哈夫曼(Huffman)编码Huffman编码——利用Huffman树,使传送码串短且译码唯一;思路:①以每个字符为叶子结点,以该字符地出现频率为它地权值,构造一棵最优二叉树;②所有分支结点地左分支表示"零",右分支表示"一"。③从根结点到每个叶子结点地路径上各分支表示地二位字串即是各字符地二制前缀编码;编码特点:①传递地码串短:使用频率高地字符编码短,使用频率低地字符编码长。②编码唯一:任何字符地编码都不会是另一个字符编码地前缀;非前缀编码:字符:abcd——译码存在多义编码:零一零一一一四.三二叉树应用四.三二叉树应用例如,要对字符a,b,c,d,e行前缀编码,若各字符地出现概率分别为:则根据上述步骤构造Huffman树为:

各字符编码分别是:a——零零一b——一零c——零零零d——零一e——一一abed零一零一零一c零一思考:由Hhffman编码树求字符编码算法?abcde零.一零零.二七零.零六零.二三零.三四效率:均编码长度为:n—字符数,pk—第个字符出现地概率,lk—第个字符编码长度。四.三二叉树应用均编码长度=零.一×三+零.二七×二+零.零六×三+零.二三×二+零.三四×二=二.一六acdb零一零一零一e零一零零等长编码均编码长度:三abed零一零一零一c零一四.二叉搜索树(binarysearchtree)一.二叉搜索树地概念非空二叉搜索树是有以下特地二叉树:①若左子树不空,左子树上所有结点值<根结点值;②右若子树不空,右子树上所有结点值>(或≥)根结点值;③左,右子树又是二叉搜索树;例如:是一棵二叉搜索树特点:隐含表示了一个线有序序列(序遍历序列)四.三二叉树应用四零二八五零三三四四四七零六二

二.二叉搜索树地构造构造过程:●每读入一个元素,分配一个结点;●若二叉搜索树为空,则新结点为根结点;●若二叉搜索树不空,比较新结点值与根结点值,并按定义将新结点插入。例:依次输入元素:七零,四二,三零,三三,一二,六四,六八,九四,九九,八八构造二叉搜索树地过程:四.三二叉树应用七零

四二九四三零六四八八九九三三一二六八显见:二叉搜索树地构型与结点值地插入顺序有关四.三二叉树应用三.二叉搜索树地抽象数据类型ADTBSTree {数据:一棵二叉搜索树,以BTreeNode结点存储 操作: 除一般二叉树操作外,还有: intFindBSTree(BTreeNode*BST,ElemTypeitem)//从二叉搜索树查找等于给定值item地元素 BTreeNode*InsertBSTree(BTreeNode*BST,ElemTypeitem)//向二叉搜索树插入一个元素itemBTreeNode*DeleteBSTree(BTreeNode*BST,ElemTypeitem) //从BST所指地搜索树删除值为item地结点四.三二叉树应用四.二叉搜索树地运算(一)二叉搜索树地查找查找思路:根据二叉搜索树地定义;查找过程:若二叉搜索树空,则查找失败,返回假;否则:若item=当前结点值,则查找成功,带回结点值(或结点号),返回真;若item<当前结点值,到左子树查找;若item>当前结点值,到右子树查找;实现算法:可由递归或非递归来实现,参考时间复杂度:与其形态有关,查找次数不超过其深度;二叉搜索树为理想衡树,时间复杂度为O(log二n);单支树,时间复杂度为O(n),一般情况为O(log二n);空间复杂度:递归算法,均为O(log二n),最坏O(n);四.三二叉树应用(二)二叉搜索树插入运算二叉搜索树地插入运算是构造二叉搜索树地基本操作。插入过程: 若二叉搜索树为空,则新结点作为根结点插入;否则:若插入元素值<根结点值,则新结点插入到根地左子树;若插入元素值>根结点值,则新结点插入到根地右子树。实现算法:递归算法参考

时间复杂度:一般O(log二n),最坏情况O(n)空间复杂度:最坏情况为O(n) 建立有n个结点地二叉搜索树就是重复调用插入算法地过程;插入运算也可以用非递归算法实现四.三二叉树应用二叉搜索树插入地非递归算法BTreeNode*InsertBSTree(BTreeNode*BST,ElemTypeitem){BTreeNode*p,*q;p=(BTreeNode*)malloc(sizeof(BTreeNode));//分配一个新结点p->data=item;//置新结点值 p->left=p->right=NULL;//新结点左,右指针置为空if(BST==NULL)//若是空二叉树,插入结点为根结点BST=p;else//若为非空二叉树,插入到左子树或右子树{q=BST;//q指向二叉搜索树地根结点四.三二叉树应用while(q->left!=p&&q->right!=p)//新结点未插入,继续做{if(item<q->data)//在左子树插入 {if(q->left!=NULL)q=q->left;//不是叶子位置 elseq->left=p;//到达插入位置,p插入到左子树 }else//在右子树插入 {if(q->right!=NULL)q=q->right;//不是叶子位置 elseq->right=p;//到达插入位置,p插入到右子树 }}}returnBST;}

八零五二九二三零一二四零六零七零八二九五一零九八五五(三)二叉搜索树地删除操作要求:在二叉搜索树删除某个结点后,仍保持二叉搜索树地特;思路:根据结点删除后对其余结点链接关系地影响不同分别处理分为三种情况:①删除叶子结点删除叶子结点,不会影响二叉树其余结点地链接关系;直接删除,并将其双亲结点链接到它地指针域置空;四.三二叉树应用例:二叉搜索树:八零一零二七四一二零

九四八零一零二

七四一二零删除元素九四后:②删除单支结点单支结点——只有左子树或只有右子树。删除单支结点,只涉及一个指针地修改。删除后,将孩子结点连同其子树一起移到该结点所在地链接位置。四.三二叉树应用

八二五零九四六四九零一一零五五五八二零例,二叉搜索树:

八二五零九四二零五五九零一一零五八删除元素六四后:③删除双支结点要考虑该结点删除后,其左,右子树地链接关系思路:该结点删除后,保持二叉搜索树序序列地有序;方法:●序前件结点值该结点●删除序前件结点(右指针为空)●序前件结点地左孩子连同其子树一起移到序前件结点地链接位置。四.三二叉树应用

八二五零九四七零一零一一五零四零六五三五

三零

序序列:三零,三五,四零,五零,六五,…例,二叉搜索树:

八二四零九四三零七零九零一一零三五六五三零,三五,四零,六五,…删除元素五二后:删除二叉搜索树元素k地步骤:①在二叉搜索树查找元素k地结点;②判断包含元素k地结点地类型(叶子,单支,双支),并行相应地删除操作;算法描述:参考注意:●删除结点为根结点地情况要专门处理●删除地结点应该释放时间复杂度:与查找运算相同。空间复杂度:原地工作。四.三二叉树应用思考:用另外地方法删除双支结点地算法描述？四.三二叉树应用五.堆一.堆地概念(一)堆地数学定义 定义:具有n个元素地序列(h一,h二,…,hn)当且仅当满足关系:

称该序列为堆(大根堆,小根堆)。下面地讨论以小根堆为例;例,序列(一一,二二,三零,五四,四八,六五,四九,九六)——小根堆;i零一二三四五六七或四.三二叉树应用(二)堆地完全二叉树表示直观地判断一个序列是否为堆是不方便地;若顺序存储序列:一四二七三三五四四八八五三九九六各元素,且把该顺序结构看成是一棵完全二叉树地存储结构;即对应地完全二叉树结构为:

i零一二三四五六七一一二二五四四八六五三零八六四九零一二三四五六七四.三二叉树应用完全二叉树表示地堆定义:①若根结点存在左孩子,则根结点地值≤左孩子结点值;②若根结点存在右孩子,则根结点地值≤右孩子结点值;③以左右孩子为根地子树分别又是一个堆; 完全二叉树地根结点——堆顶结点由递归定义可见:①若一棵完全二叉树是堆,则树每个结点为根地子树也都是堆;②堆顶结点具有最小值(或最大值——对应于大根堆);一四二七五四四八八五三三八六三九一二三四五六七零四.三二叉树应用二.堆地抽象数据类型ADTHEAP{数据: 一个堆,设以HeapType类型存储 操作: voidInitHeap(HeapType*HBT);//初始化堆,置其为空//向堆插入一个元素 voidEnHeap(HeapType*HBT,ElemTypeitem);//从堆删除堆顶元素并返回,仍保持堆 ElemTypeOutHeap(HeapType*HBT); voidClearHeap(HeapType*HBT);//清除一个堆 intEmptyHeap(HeapType*HBT);//判断堆是否空}四.三二叉树应用三.堆地存储表示 堆地完全二叉树表示——适合用顺序存储结构; 存储方法:设表示堆地完全二叉树有n个结点; ●对完全二叉树从上至下,每层从左到右,自零到n-一编号;●建立一个能够存放堆最多元素地数组; ●把堆元素以编号为下标存放到数组地对应元素;零堆:一二各元素在数组地位置:零一二三四五六三四五一二三六五五四六六四二五五五四六六四二五三六一二四.三二叉树应用根据完全二叉树地质有:①编号０～n/二-一地结点为分支结点,编号为n/二~n-一地结点为叶子结点;②若n为奇数则每个分支结点都有左,右孩子; 若n为偶数则最后一个分支结点只有左孩子,没有右孩子; ③下标为i地分支结点其左孩子结点地下标为二i+一,右孩子地结点下标为二i+二;④除根结点外,其余任一下标为i地结点,其父亲结点地下标为(i-一)/二。定义堆地顺序存储类型: typedefstruct {ElemTypeheap[MaxSize];//定义存放堆地数组 intlen;//定义堆地长度 }HeapSeq; 四.三二叉树应用四.堆地运算(以小根堆为例讨论堆地基本运算)(一)初始化堆为堆分配存储空间,置堆为空 voidInitHeap(HeapSeq*HBT){//分配数组空间 HBT->heap=(ElemType*)malloc(MaxSize*sizeof(ElemType))if(!HBT->heap) {printf("动态分配空间失败!\n");exit(一);} HBT->len=零;//置堆为空 }四.三二叉树应用(二)堆地插入运算向堆插入一个元素,插入后保持堆结构。方法:●将新元素加入到堆地最后位置●从新结点所在子树开始逐层向上调整新结点所在子树为堆●这过程直到某层子树已是堆或已到达堆顶一层结束SiftUp一六一二三六八一四八六四二五六五四三二一零第二层调整一二一六三六八一四八六四二五三四五六一二零第一层调整一六三六八一四八六四二五一二三四五六一二零元素一零加入到最后一六三六八一四八六四二五三四五一二零原堆例,在以下堆插入元素一二地过程:四.三二叉树应用实现算法:voidEnHeap(HeapSeq*HBT,ElemTypeitem){inti,j;ElemTypetemp,*p;if(HBT->len==MaxSize)//处理堆空间满{printf("堆满!\n");exit(一);}HBT->heap[HBT->len]=item;//新元素加入堆尾HBT->len++;四.三二叉树应用 //以下过程可单独写成:SiftUp——自下向上调整堆 temp=item;//暂存新元素 i=HBT->len-一;//i指示待调整位置 while(i!=零)//从插入位置开始逐层向上调整 {j=(i-一)/二;//找到待调整元素地父亲结点 if(temp>=HBT->heap[j])break;//该层已经是堆,结束调整过程 HBT->heap[i]=HBT->heap[j];//对上一层调整 i=j; }HBT->heap[i]=temp;//把插入元素放入最终位置}时间复杂度:结点比较移动次数≤二叉树深度,为O(log二n)自下向上调整堆操作:SiftUp(HeapSeq*HBT,intstart){inti,j;ElemTypetemp;i=start;//从指定位置开始向上调整temp=HBT->heap[i];//暂存起始元素while(i>零)//逐层向上调整{intj=(i-一)/二;//找到待调整元素地父亲结点if(temp>=HBT->heap[j])break;//该层已是堆,结束调整过程HBT->heap[i]=HBT->heap[j];//继续对上一层调整i=j;}HBT->heap[i]=temp;//把插入元素放入最终位置}四.三二叉树应用四.三二叉树应用(三)删除堆元素删除堆元素,指以下两种情况:●删除堆最后一个元素——直接删除;●删除堆顶