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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构与程序设计,*,数据结构与程序设计(25)Chapter10.2 Binary Search Tree,王丽苹,10/8/2024,1,数据结构与程序设计,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.,10/8/2024,2,数据结构与程序设计,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,10/8/2024,3,数据结构与程序设计,Binary Search Trees数据结构,template,class Search_tree:,public Binary_tree,public:,Error_code,insert,(const Record,Error_code,remove,(const Record,Error_code,tree_search,(Record,private:/Add auxiliary function prototypes here.,;,10/8/2024,4,数据结构与程序设计,Implement of Binary Search Trees10.2.2 Tree search 查找操作,Error_code tree_search(Record,方法：,将target与树根节点比较，如果相等则找到，程序结束。,如果比根节点大，则进入右子树继续查找。,如果比根节点小，则进入左子树继续查找。,10/8/2024,5,数据结构与程序设计,Implement of Binary Search Trees10.2.2 Tree search 查找操作 P447,Example：查找Kim的过程,10/8/2024,6,数据结构与程序设计,Implement of Binary Search TreesTree search 查找操作 实现,#include Binary_tree.cpp,template,class Search_tree:public Binary_tree,public:,Error_code insert(const Record,Error_code remove(const Record,Error_code tree_search(Record,/查找成功，target的内容为查找树种节点的信息。返回success。,/查找失败，返回notPresent,private:/Add auxiliary function prototypes here.,Binary_node*search_for_node(Binary_node*sub_root,const Record P448,;,10/8/2024,7,数据结构与程序设计,Tree search 查找操作 实现,Binary_node*search_for_node(Binary_node*sub_root,const Record P448,search_for_node是一个查找子函数。,Sub_root:为空或者指向一棵子树。,Postcondition:当target不在子树sub_root中存在时，返回NULL，当找到target时返回指向target的指针。,10/8/2024,8,数据结构与程序设计,Implement of Binary Search Trees,查找操作 实现,template,Error_code Search_tree:tree_search(Record&target)const,Error_code result=success;,Binary_node*found=search_for_node(root,target);,if(found=NULL),result=not_present;,else,target=found-data;,return result;,10/8/2024,9,数据结构与程序设计,Implement of Binary Search Trees,查找操作 实现-递归,template,Binary_node*Search_tree:search_for_node(,Binary_node*sub_root,const Record&target)const,if(sub_root=NULL|sub_root-data=target),return sub_root;,else if(sub_root-data right,target);,else return search_for_node(sub_root-left,target);,10/8/2024,10,数据结构与程序设计,Implement of Binary Search Trees,查找操作 实现 非递归,/Nonrecursive version:,template,Binary_node*Search_tree:search_for_node(,Binary_node*sub_root,const Record&target)const,while(sub_root!=NULL&sub_root-data!=target),if(sub_root-data right;,else sub_root=sub_root-left;,return sub_root;,10/8/2024,11,数据结构与程序设计,查找操作 实现分析 P449页,需要注意：同样的关键码，可能产生很多不同的查找树结构。图(a)(b)(c)(d)(e)为由七个字母构成的二分查找树的结构。,对于查找操作:整棵树越浓密，则查找操作的效率越高。,最好的结构,最常见的结构,10/8/2024,12,数据结构与程序设计,查找操作 实现分析 P449页,最坏的结构,10/8/2024,13,数据结构与程序设计,10.2.3 Insert into a Binary Search Tree 二分查找树的插入操作,向二分查找树中插入节点的过程分析：,如果二叉查找树为空，则新结点作为根结点。,如果二叉查找树非空，则将新结点的关键码与根结点的关键码比较：,若相等表示该结点已在二叉排序树中插入失败；,若小于根结点的关键码，则将新结点插入到根结点的左子树中；,否则，插入到右子树中。,子树中的插入过程和树中的插入过程相同，如此进行下去，直到找到该结点，或者直到左或右子树为空二叉树，新结点插入成为叶子结点为止。,10/8/2024,14,数据结构与程序设计,P451 e,b,d,f,a,g,c逐一插入的过程,10/8/2024,15,数据结构与程序设计,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)的结构,10/8/2024,16,数据结构与程序设计,Implement of Binary Search TreesTree search 插入操作 实现,#include Binary_tree.cpp,template,class Search_tree:public Binary_tree,public:,Error_code insert(const Record,Error_code remove(const Record,Error_code tree_search(Record,private:/Add auxiliary function prototypes here.,Error_code search_and_insert(Binary_node*&sub_root,const Record&new_data),;,10/8/2024,17,数据结构与程序设计,Implement of Binary Search Trees,插入操作 实现,template,Error_code Search_tree:insert(,const Record&new_data),/插入成功返回 success,/插入失败返回,duplicate_error,Error_code result=search_and_insert(root,new_data);,if(result=success)count+;,return result;,10/8/2024,18,数据结构与程序设计,Implement of Binary Search Trees,插入操作 实现,template,Error_code Search_tree:search_and_insert(,Binary_node*,&,sub_root,/*inout*/,const Record&new_data,/*in*/,),if(sub_root=NULL),sub_root=new Binary_node(new_data);,return success;,else if(new_data data),return search_and_insert(sub_root-left,new_data);,else if(new_data sub_root-data),return search_and_insert(sub_root-right,new_data);,else return duplicate_error;,10/8/2024,19,数据结构与程序设计,10.2.4 Tree sort,对于一棵二叉查找树，中序遍历的序列即为有序序列。,因此，二叉查找树的插入过程也可以看成是排序的过程。即,首先，将无序序列逐一插入二叉排序树。,然后，对二叉排序树进行中序遍历。完成排序,Tree sort比较适合于无序的序列，对于基本有序的序列效率较低,10/8/2024,20,数据结构与程序设计,10.2.5 Removal from a Binary Search Tree,删除操作讨论,（1）删除的节点是叶子结点：replace the link to the removed node by NULL.,10/8/2024,21,数据结构与程序设计,10.2.5 Removal from a Binary Search Tree,删除操作讨论,（2）删除的节点只有一棵非空子树：A