数据结构与程序设计(王丽苹)25二分查找树.ppt
5/27/2023,数据结构与程序设计,1,数据结构与程序设计(25)Chapter10.2 Binary Search Tree,王丽苹,5/27/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.,5/27/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,5/27/2023,数据结构与程序设计,4,Binary Search Trees数据结构,template class Search_tree:public Binary_tree public:Error_code insert(const Record,5/27/2023,数据结构与程序设计,5,Implement of Binary Search Trees10.2.2 Tree search 查找操作,Error_code tree_search(Record 方法：将target与树根节点比较，如果相等则找到，程序结束。如果比根节点大，则进入右子树继续查找。如果比根节点小，则进入左子树继续查找。,5/27/2023,数据结构与程序设计,6,Implement of Binary Search Trees10.2.2 Tree search 查找操作 P447,Example：查找Kim的过程,5/27/2023,数据结构与程序设计,7,Implement of Binary Search TreesTree search 查找操作 实现,#include Binary_tree.cpptemplate class Search_tree:public Binary_tree public:Error_code insert(const Record,5/27/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的指针。,5/27/2023,数据结构与程序设计,9,Implement of Binary Search Trees查找操作 实现,template Error_code Search_tree:tree_search(Record,5/27/2023,数据结构与程序设计,10,Implement of Binary Search Trees查找操作 实现-递归,template Binary_node*Search_tree:search_for_node(Binary_node*sub_root,const Record,5/27/2023,数据结构与程序设计,11,Implement of Binary Search Trees查找操作 实现 非递归,/Nonrecursive version:template Binary_node*Search_tree:search_for_node(Binary_node*sub_root,const Record,5/27/2023,数据结构与程序设计,12,查找操作 实现分析 P449页,需要注意：同样的关键码，可能产生很多不同的查找树结构。图(a)(b)(c)(d)(e)为由七个字母构成的二分查找树的结构。对于查找操作:整棵树越浓密，则查找操作的效率越高。,最好的结构,最常见的结构,5/27/2023,数据结构与程序设计,13,查找操作 实现分析 P449页,最坏的结构,5/27/2023,数据结构与程序设计,14,10.2.3 Insert into a Binary Search Tree 二分查找树的插入操作,向二分查找树中插入节点的过程分析：如果二叉查找树为空，则新结点作为根结点。如果二叉查找树非空，则将新结点的关键码与根结点的关键码比较：若相等表示该结点已在二叉排序树中插入失败；若小于根结点的关键码，则将新结点插入到根结点的左子树中；否则，插入到右子树中。子树中的插入过程和树中的插入过程相同，如此进行下去，直到找到该结点，或者直到左或右子树为空二叉树，新结点插入成为叶子结点为止。,5/27/2023,数据结构与程序设计,15,P451 e,b,d,f,a,g,c逐一插入的过程,5/27/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)的结构,5/27/2023,数据结构与程序设计,17,Implement of Binary Search TreesTree search 插入操作 实现,#include Binary_tree.cpptemplate class Search_tree:public Binary_tree public:Error_code insert(const Record,5/27/2023,数据结构与程序设计,18,Implement of Binary Search Trees插入操作 实现,template Error_code Search_tree:insert(const Record,5/27/2023,数据结构与程序设计,19,Implement of Binary Search Trees插入操作 实现,template Error_code Search_tree:search_and_insert(Binary_node*,5/27/2023,数据结构与程序设计,20,10.2.4 Tree sort,对于一棵二叉查找树，中序遍历的序列即为有序序列。因此，二叉查找树的插入过程也可以看成是排序的过程。即首先，将无序序列逐一插入二叉排序树。然后，对二叉排序树进行中序遍历。完成排序Tree sort比较适合于无序的序列，对于基本有序的序列效率较低,5/27/2023,数据结构与程序设计,21,10.2.5 Removal from a Binary Search Tree 删除操作讨论,（1）删除的节点是叶子结点：replace the link to the removed node by NULL.,5/27/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.,5/27/2023,数据结构与程序设计,23,10.2.5 Removal from a Binary Search Tree 删除操作讨论,（3）删除的节点左右子树都非空：找到被删除节点的中序遍历的前驱（左子树中最右边的孩子），用前驱节点代替被删除点.,5/27/2023,数据结构与程序设计,24,Implement of Binary Search TreesTree search 删除操作 实现,#include Binary_tree.cpptemplate class Search_tree:public Binary_tree public:。Error_code remove(const Record,5/27/2023,数据结构与程序设计,25,Implement of Binary Search TreesTree search 删除操作 实现 P456,Error_code remove_root(Binary_node*,5/27/2023,数据结构与程序设计,26,Implement of Binary Search Trees删除操作 实现 P458,template Error_code Search_tree:remove(const Record,5/27/2023,数据结构与程序设计,27,Implement of Binary Search Trees删除操作 实现 P458,template Error_code Search_tree:search_and_destroy(Binary_node*,5/27/2023,数据结构与程序设计,28,删除操作 实现 P457,template Error_code Search_tree:remove_root(Binary_node*,5/27/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,5/27/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,5/27/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,5/27/2023,数据结构与程序设计,32,Implement of Binary Search Trees,目录Search_tree下例程,5/27/2023,数据结构与程序设计,33,HOMEWORK,BOOK P459E1(b)(e)(i)E2(b)(c)E3(c)(e)(f),
