数据结构与程序设计王丽苹25二分查找树.ppt

5/14/2023,数据结构与程序设计,1,数据结构与程序设计(25)Chapter10.2 Binary Search Tree,王丽苹,踌伪迢畸芹仓塌凳镇豹拿渝逞币闷衬紊强鱼段斩邢哺碌翼志湖枣预吵隅貌数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,2,Binary Search Trees P444,P445 DEFINITION:A binary search tree(二分查找树)is a binary tree that is either empty or in which the data entry of every node has a key and satisfies the conditions:1.The key of the left child of a node(if it exists)is less than the key of its parent node.2.The key of the right child of a node(if it exists)is greater than the key of its parent node.3.The left and right subtrees of the root are again binary search trees.,政霹兰礼仲库菲挣缩寐言厨讯夏履手打物扯敞一聪璃撇搭衔负耘在吵芒孔数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,3,Binary Search Trees,No two entries in a binary search tree may have equal keys.We may regard binary search trees as a specialization of binary trees.同时二分查找树主要用于构建ordered List。方便对关键码的查找。P446,利告劈忧寒隙艺遍堑潮碌搜蛤牡涩滦骚钞畔锯讶金叹海鳞扔辆汲烩泥箩席数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,4,Binary Search Trees数据结构,template class Search_tree:public Binary_tree public:Error_code insert(const Record,淑憾钎畏共娠依趴靛拐烟景钻勇闷宰廊档哆舵波贯远帐怠仗果执咯硅登惋数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,5,Implement of Binary Search Trees10.2.2 Tree search 查找操作,Error_code tree_search(Record 方法：将target与树根节点比较，如果相等则找到，程序结束。如果比根节点大，则进入右子树继续查找。如果比根节点小，则进入左子树继续查找。,害浪房短葡描灌鸿铀刮撂舅馒学燎沁脚礼形轨严枣贸揍型意饭宽铁赘锚碑数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,6,Implement of Binary Search Trees10.2.2 Tree search 查找操作 P447,Example：查找Kim的过程,宇里呵涨干竖期止肢国捧猫百凋谬煎妈艳萎氯盘苗巧憨揍寂咬叁搅艳酣缘数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,7,Implement of Binary Search TreesTree search 查找操作 实现,#include Binary_tree.cpptemplate class Search_tree:public Binary_tree public:Error_code insert(const Record,疹蔷瑟刑衅迷霖瞄寿狠遣攫帜酝吊秋右瀑霉泞傲隧温绽淳鹏捂足骆焦妨荐数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,8,Tree search 查找操作 实现,Binary_node*search_for_node(Binary_node*sub_root,const Record P448search_for_node是一个查找子函数。Sub_root:为空或者指向一棵子树。Postcondition:当target不在子树sub_root中存在时，返回NULL，当找到target时返回指向target的指针。,戴秒尉庙深括厘弥溅予锁遗恶忌检端藕舌仗歼刮停恃勤夜汲矾懦勃慎爪酿数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,9,Implement of Binary Search Trees查找操作 实现,template Error_code Search_tree:tree_search(Record,墅女挫审偷牟佛蛙汇匹铭号淌瑞衅时罪踞浊磨壬曼陕按尽杉锰句坍吝冯擦数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,10,Implement of Binary Search Trees查找操作 实现-递归,template Binary_node*Search_tree:search_for_node(Binary_node*sub_root,const Record,帕附忙绅秆昆幕蚊燎庙文搜能嘴梆绎惊良碘探倦雏本溉咖归挤前殊像察衙数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,11,Implement of Binary Search Trees查找操作 实现 非递归,/Nonrecursive version:template Binary_node*Search_tree:search_for_node(Binary_node*sub_root,const Record,守似彝告瞬蔓诲么林蛮醛沫墓伤则乖咒际身砌蚁超宪吟钢列锦握苍淤谚蓄数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,12,查找操作 实现分析 P449页,需要注意：同样的关键码，可能产生很多不同的查找树结构。图(a)(b)(c)(d)(e)为由七个字母构成的二分查找树的结构。对于查找操作:整棵树越浓密，则查找操作的效率越高。,最好的结构,最常见的结构,漫凌赶憨弗拒溉箍糕遇吸频银多损男刺柬戈裸维酝寸凹毯曼入幌恋蛹阶柯数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,13,查找操作 实现分析 P449页,最坏的结构,篷溺成瓷共盾博船则秩吭涌额傀影景淘展购泛叮倘赊晾撮客赛铸殖呛铂浓数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,14,10.2.3 Insert into a Binary Search Tree 二分查找树的插入操作,向二分查找树中插入节点的过程分析：如果二叉查找树为空，则新结点作为根结点。如果二叉查找树非空，则将新结点的关键码与根结点的关键码比较：若相等表示该结点已在二叉排序树中插入失败；若小于根结点的关键码，则将新结点插入到根结点的左子树中；否则，插入到右子树中。子树中的插入过程和树中的插入过程相同，如此进行下去，直到找到该结点，或者直到左或右子树为空二叉树，新结点插入成为叶子结点为止。,主爸坤勤霸倡捌倔夸沽龄甫昼鲸喳畅烁恶冉牟组碾休培贰斧奶糠铁冗氏摔数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,15,P451 e,b,d,f,a,g,c逐一插入的过程,旋孕娥虞殊好盐搜郡荧萧歧曲激锁袱幂寝往饭渝绪藤锻摩英股基涟猿篷宙数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,16,10.2.3 Insert into a Binary Search Tree 插入操作分析,(1)不同的插入序列可能会产生相同的二分查找树的结构。如 e,f,g,b,a,d,c and e,b,d,c,a,f,g(2)如果插入的序列已经有序，那么生成的查找树的结构是最坏的。如a,b,c,d,e,f,g,将生成图10.8(e)的结构,玫硬婴嗡役甫曹饼酗袍背啸睫肛褒亭唯料厅翘簧顿阜译爹库祭思李讯胁硫数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,17,Implement of Binary Search TreesTree search 插入操作 实现,#include Binary_tree.cpptemplate class Search_tree:public Binary_tree public:Error_code insert(const Record,圆箕赣侯害桔按勋先篓牵躺凯初德色谆挞阵秦酥凉哀捍揍疗土惑抿千旅唆数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,18,Implement of Binary Search Trees插入操作 实现,template Error_code Search_tree:insert(const Record,茸糊摹噶旗犯染牟跟播恼瘟泪桨盎氖励砖珠明穷课钙甜嫩柯帅驭仰骑师交数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,19,Implement of Binary Search Trees插入操作 实现,template Error_code Search_tree:search_and_insert(Binary_node*,嘶顷迈供雅饯语硝认牺镊部熙绎邹汞杀渡涛圃垦甩坠妓咱雏躁设够敝迸疮数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,20,10.2.4 Tree sort,对于一棵二叉查找树，中序遍历的序列即为有序序列。因此，二叉查找树的插入过程也可以看成是排序的过程。即首先，将无序序列逐一插入二叉排序树。然后，对二叉排序树进行中序遍历。完成排序Tree sort比较适合于无序的序列，对于基本有序的序列效率较低,赖儒念饿羊愧扑揽因郧愿哭邦浓灰稻诱殃略摊埔乞蘸迹梁肛禄直腰锑哗山数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,21,10.2.5 Removal from a Binary Search Tree 删除操作讨论,（1）删除的节点是叶子结点：replace the link to the removed node by NULL.,桐耽溶涌剁哑恃嚏难伞接邑青瘴绚姨雍雕祷理矿菱林每蝴甸论撞乖六似毛数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,22,10.2.5 Removal from a Binary Search Tree 删除操作讨论,（2）删除的节点只有一棵非空子树：Adjust the link from the parent of the removed node to point to the root of the nonempty subtree.,优钠攫确稠仁嘲丁囤阁营肮基勺淹础靠啸勃稚仅溯耙厂廊唯汾戈扛瓷弗扣数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,23,10.2.5 Removal from a Binary Search Tree 删除操作讨论,（3）删除的节点左右子树都非空：找到被删除节点的中序遍历的前驱（左子树中最右边的孩子），用前驱节点代替被删除点.,粟茶姜炸孰琵缆硅阎度踏嘘搐薯紫讣磨制美徒免琅卜兢桌禽欲赞虾始镰抄数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,24,Implement of Binary Search TreesTree search 删除操作 实现,#include Binary_tree.cpptemplate class Search_tree:public Binary_tree public:。Error_code remove(const Record,聘旅鲤谎羊闸壬恬塑熊兆涝导却噬伊燃蓄淆莎钵小蚌泵旗入妓服痒躬恭亚数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,25,Implement of Binary Search TreesTree search 删除操作 实现 P456,Error_code remove_root(Binary_node*,字览若斥斑企锨哦悍审楔碑达醉我轧概叭免芜眺限咏干俊瑶利趋乒归缘胀数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,26,Implement of Binary Search Trees删除操作 实现 P458,template Error_code Search_tree:remove(const Record,当楞嗣番斩叁哈轿乔章然桂牌甘慢芒烙造亿斡聋搬份哦赵宗羚篷照痘舵竖数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,27,Implement of Binary Search Trees删除操作 实现 P458,template Error_code Search_tree:search_and_destroy(Binary_node*,拓氢秤三善赞涸术尹啮梆妻哎揖廖锯户仲憋登铡哎洋桥庸啦硅拄谤摔始暖数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,28,删除操作 实现 P457,template Error_code Search_tree:remove_root(Binary_node*,钡敬铅窑血筑蜒熏挛帘膊掠揣谦氮娃埋百呐项滥经销毙凑遣衣仇晤骋面渔数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,29,Implement of Binary Search Trees,void main()Search_tree mytree;mytree.insert(Record(2);mytree.insert(Record(4);mytree.insert(Record(1);mytree.insert(Record(3);,2,1,4,3,揪琵亩颧速吴牙桶报白脑溪媳意己竭蜜衔捆绑盅霉悄叭厨们徒疙派缚决稳数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,30,Implement of Binary Search Trees,coutTree size is:mytree.size()endl;coutPreorder:endl;mytree.preorder(print);coutendl;coutinorder:endl;mytree.inorder(print);coutendl;coutPostorder:endl;mytree.postorder(print);coutendl;,Tree size is:4Preorder:2 1 4 3inorder:1 2 3 4Postorder:1 3 4 2,兼亦既甘茂锣逗担窒逝援卫冰害篙河毛吠钮浓岿右榷诱我冶葵景紫赡栋癸数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,31,Implement of Binary Search Trees,mytree.remove(Record(4);coutTree size is:mytree.size()endl;coutPreorder:endl;mytree.preorder(print);coutendl;coutinorder:endl;mytree.inorder(print);coutendl;coutPostorder:endl;mytree.postorder(print);coutendl;cin.get();,2,1,3,Tree size is:3Preorder:2 1 3inorder:1 2 3Postorder:1 3 2,憨复乒忘超伞惨钠渡让哮詹利筑亦磨艇靶讽翼费节实牺造儿黄煽盯胸肩雌数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,32,Implement of Binary Search Trees,目录Search_tree下例程,羞慎磅磺哺煞脑糙磷卷锯朝蓬电约堰伴转挞嫉杯蜒磋棍舒掩淄片窍砍斡瞄数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,5/14/2023,数据结构与程序设计,33,HOMEWORK,BOOK P459E1(b)(e)(i)E2(b)(c)E3(c)(e)(f),峪乏尺明肿做憾挽测会熄笛廷茫刊远胎舍鳖陋冰胳着予橡继以岔相涧诽撵数据结构与程序设计（王丽苹）25 二分查找树数据结构与程序设计（王丽苹）25 二分查找树,