请输入您要查询的百科知识:

 

词条 二叉检索树
释义

二叉检索树

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条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/1/11 9:54:38