词条 | 二叉检索树 |
释义 | 二叉检索树 Copyright 2002 by Zhang Ming, PKUCS 1. 定义及性质 n二叉检索树或者是一颗空树;或者是具 有下列性质的二叉树:对于任何一个结 点,设其值为K,则该结点的左子树(若 不空)的任意一个结点的值都小于K;该 结点的右子树(若不空)的任意一个结点 的值都大于或等于K;而且它的左右子树 也分别为二叉检索树. n二叉检索树的性质: 按照中序周游将各结 点打印出来,将得到按照由小到大的排 列. Copyright 2002 by Zhang Ming, PKUCS BST图示 Copyright 2002 by Zhang Ming, PKUCS 检索 n二叉检索树的效率就在于只需检索二个子树 之一. -从根结点开始,在二叉检索树中检索值K.如果 根结点储存的值为K,则检索结束. -如果K小于根结点的值,则只需检索左子树 -如果K大于根结点的值,就只检索右子树 n这个过程一直持续到K被找到或者我们遇上 了一个树叶. n如果遇上树叶仍没有发现K,那么K就不在该 二叉检索树中. Copyright 2002 by Zhang Ming, PKUCS 2. 二叉检索树类定义 // BSTimplementation for the Dictionary ADT template class BST : public Dictionary { private: BinNode* root; // Root of the BST intnodecount; // Number of nodes in the BST // Private "helper" functions void clearhelp(BinNode*); BinNode* inserthelp(BinNode*, const Elem&); BinNode* deletemin(BinNode*, BinNode*&); BinNode* removehelp(BinNode*, const Key&, BinNode*&); boolfindhelp(BinNode*, const Key&, Elem&) const; void printhelp(BinNode*, int) const; Copyright 2002 by Zhang Ming, PKUCS public: BST() { root = NULL; nodecount= 0; } // Constructor ~BST() { clearhelp(root); } // Destructor void clear() { clearhelp(root); root = NULL; nodecount= 0; } boolinsert(constElem& e) { root = inserthelp(root, e); nodecount++; return true; } boolremove(constKey& K, Elem& e) { BinNode* t = NULL; root = removehelp(root, K, t); if (t == NULL) return false; // Nothing found e = t->val(); nodecount--; delete t; return true; } Copyright 2002 by Zhang Ming, PKUCS boolremoveAny(Elem& e) { // Delete min value if (root == NULL) return false; // Empty tree BinNode* t; root = deletemin(root, t); e = t->val(); delete t; nodecount--; return true; } boolfind(constKey& K, Elem& e) const { return findhelp(root, K, e); } intsize() { return nodecount; } void print() const { if (root == NULL) cout<< "The BST is empty.\"; else printhelp(root, 0); } }; Copyright 2002 by Zhang Ming, PKUCS 3. 二叉检索树的实现 n插入中包含检索(可以重码) boolinsert(constElem& e) { root = inserthelp(root, e); nodecount++; return true; } nInserthelp的实现 template BinNode* BST:: inserthelp(BinNode* subroot, const Elem& val) { if (subroot== NULL) // Empty tree: create node return (new BinNodePtr(val, NULL, NULL)); if (EEComp::lt(val, subroot->val())) // Insert on left subroot->setLeft(inserthelp(subroot->left(), val)); else subroot->setRight(inserthelp(subroot->right(), val)); return subroot; // Return subtreewith node inserted } Copyright 2002 by Zhang Ming, PKUCS BST插入图示 Copyright 2002 by Zhang Ming, PKUCS 检索 template boolBST:: findhelp( BinNode* subroot, const Key& K, Elem& e) const { if (subroot== NULL) return false; // Empty tree else if (KEComp::lt(K, subroot->val())) // Check left return findhelp(subroot->left(), K, e); else if (KEComp::gt(K, subroot->val())) //Check right return findhelp(subroot->right(), K, e); else { e = subroot->val(); return true; } // Found it } Copyright 2002 by Zhang Ming, PKUCS 打印 template void BST:: printhelp(BinNode* subroot, intlevel) const { if (subroot== NULL) return; // Empty tree printhelp(subroot->left(), level+1); //Do left subtree for (inti=0; icout<< " "; cout} Copyright 2002 by Zhang Ming, PKUCS 4. 二叉检索树结点的删除 n对于二叉检索树,删除一个结点,相当 于删除有序序列中的一个记录,要求删 除后能保持二叉检索树的排序特性,并 且树高变化较小. (1)找到值为val的结点rt (2)rt为叶,可以直接删除 (3)rt左空或右空,可以让它的右子树或 左子树直接代替原rt (4)rt左右都不空,可以让右子树中的最 小值代替原rt Copyright 2002 by Zhang Ming, PKUCS 删除子树中最小值图示 Copyright 2002 by Zhang Ming, PKUCS 删除右子树中最小值结点 Copyright 2002 by Zhang Ming, PKUCS 删除rt子树中最小结点 template BinNode* BST:: deletemin(BinNode* subroot, BinNode*& min) { if (subroot->left() == NULL) { // Found min min = subroot; return subroot->right(); } else { // Continue left subroot->setLeft(deletemin(subroot->left(), min)); return subroot; } } Copyright 2002 by Zhang Ming, PKUCS 删除值为val的结点 template BinNode* BST:: removehelp(BinNode* subroot, const Key& K, BinNode*& t) { if (subroot== NULL) return NULL; // Val is not in tree else if (KEComp::lt(K, subroot->val())) // Check left subroot->setLeft(removehelp(subroot->left(), K, t)); else if (KEComp::gt(K, subroot->val())) // Check right subroot->setRight(removehelp(subroot->right(), K, t)); else { // Found it: remove it BinNode* temp; t = subroot; Copyright 2002 by Zhang Ming, PKUCS if (subroot->left() == NULL) // Only a right child subroot= subroot->right(); // so point to right else if (subroot->right() == NULL) // Only a left child subroot= subroot->left(); // so point to left else { // Both children are non-empty subroot->setRight(deletemin(subroot->right(), temp)); Elemte= subroot->val(); subroot->setVal(temp->val()); temp->setVal(te); t = temp; } } return subroot; } Copyright 2002 by Zhang Ming, PKUCS 删除值为val的结点(续) else { // Found it: remove it BinNode* temp = rt; if (rt->left == NULL) rt= rt->right; else if (rt->right == NULL) rt= rt->left; else { temp = deletemin(rt->right); rt->setValue(temp->value()); } delete temp; } } Copyright 2002 by Zhang Ming, PKUCS 讨论 n所有操作都围绕BST的性质,并一定要保 持这个性质 n用非递归算法实现插入,检索,删除 Copyright 2002 by Zhang Ming, PKUCS 讨论(续) n允许有重复关键码 时(右子树) -重复关键码应该有 规律地出现 -插入,检索,删除 都考虑这个特点. 尤其是删除,必须 删右子树中最小( 如果有重复,将是 值与被删根结点相 同的结点,因此能 保持性质) 132 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。