第C++詳解數(shù)據(jù)結(jié)構(gòu)中的搜索二叉樹目錄定義查找某個元素構(gòu)造搜索二叉樹往搜索二叉樹中插入元素搜索二叉樹刪除節(jié)點

定義

搜索二叉樹，也稱有序二叉樹，排序二叉樹，是指一棵空樹或者具有下列性質(zhì)的二叉樹：

1、若任意節(jié)點的左子樹不空，則左子樹上的所有節(jié)點的值均小于它的根節(jié)點的值

2、若任意節(jié)點的右子樹不空，則右子樹上的所有節(jié)點的值均大于它的根節(jié)點的值

3、任意節(jié)點的左右子樹也稱為二叉查找樹。

4、沒有鍵值相等的節(jié)點。

5、搜索二叉樹中序遍歷為有序數(shù)組。

結(jié)構(gòu)代碼實現(xiàn)

templateclassK

structBSTreeNode

BSTreeNodeK*_left;

BSTreeNodeK*_right;

K_key;

BSTreeNode(constKkey)

:_left(left)

,_right(right)

,_key(key)

};

查找某個元素

在搜索二叉樹b中查找x的過程

若樹是一個空樹，則搜索失敗，否則：若x等于b的根節(jié)點的鍵值，則查找成功；否則：若x小于b的根節(jié)點的鍵值，則搜索左子樹；否則：若x大于b的根節(jié)點的鍵值，則搜索右子樹。

非遞歸實現(xiàn)

typrdefBSTreeNodeKNode;

Node*find(constKkey)

Node*cur=_root;

while(cur)

if(cur-_keykey)

cur=cur-right;

elseif(cur-_keykey)

cur=cur-left;

else

returncur;

returnnullptr;

}

遞歸實現(xiàn)

typrdefBSTreeNodeKNode;

Node*_findr(Node*root,constKkey)

if(root==nullptr)

returnnullptr;

if(root-_keykey)

return_findr(root-_right);

elseif(root-_keykey)

return_findr(root-_left);

else

returnroot;

}

構(gòu)造搜索二叉樹

若樹為空樹，則直接插入；否則若插入值大于根節(jié)點的鍵值，則插入到右子樹中，以此遞歸；否則若插入值小于根節(jié)點的鍵值，則插入到左子樹中

非遞歸實現(xiàn)：

boolinsert(constKkey)

if(_root==nullptr)

_root=newNode(key);

returntrue;

Node*parent=nullptr;

Node*cur=_root;

while(cur)

if(cur-_keykey)

parent=cur;

cur=cur-_right;

elseif(cur-_keykey)

parent=cur;

cur=cur-_left;

else

returnfalse;

cur=newNode(key);

if(parent-_keykey)

parent-_right=cur;

else

parent-_left=cur;

returntrue;

}

遞歸實現(xiàn)：

bool_insertR(Node*root,constKkey)

if(root==NULL)

root=newNode(key);

returntrue;

if(root-_keykey)

return_insertR(root-_right,key);

elseif(root-_keykey)

return_insertR(root-_left,key);

else

returnfalse;

}

往搜索二叉樹中插入元素

向一個二叉搜索樹b中插入一個節(jié)點s的算法，過程為：

若b是空樹，則將s所指結(jié)點作為根節(jié)點插入，否則：若s-data等于b的根節(jié)點的數(shù)據(jù)域之值，則返回，否則：若s-data小于b的根節(jié)點的數(shù)據(jù)域之值，則把s所指節(jié)點插入到左子樹中，否則：把s所指節(jié)點插入到右子樹中。（新插入節(jié)點總是葉子節(jié)點）

搜索二叉樹刪除節(jié)點

重難點

二叉搜索樹的結(jié)點刪除比插入較為復雜，總體來說，結(jié)點的刪除可歸結(jié)為三種情況：

如果結(jié)點z沒有孩子節(jié)點，那么只需簡單地將其刪除，并修改父節(jié)點，用NULL來替換z；如果結(jié)點z只有一個孩子，那么將這個孩子節(jié)點提升到z的位置，并修改z的父節(jié)點，用z的孩子替換z；如果結(jié)點z有2個孩子，那么查找z的后繼y，此外后繼一定在z的右子樹中，然后讓y替換z

非遞歸實現(xiàn)

boolErase(constKkey)

Node*parent=nullptr;

Node*cur=_root;

while(cur)

if(cur-_keykey)

parent=cur;

cur=cur-_right;

elseif(cur-_keykey)

parent=cur;

cur=cur-left;

else

//找到了，開始刪除

if(cur-_left==nullptr)

if(cur==_root)

_root=cur-_right;

else

if(parent-_left==cur)

parent-_left=cur-_right;

else

parent-_right=cur-_right;

deletecur;

elseif(cur-_right==nullptr)

if(cur==_root)

_root=cur-_left;

else

if(parent-_left==cur)

parent-_left=cur-_left;

else

parent-_right=cur-_right;

else//左右都不為空

Node*minRight=cur-_right;

while(minRight-_left)

minRight=minRight-_left;

kmin=minRight-_key;

this-Erase(min);

cur-_key=min;

returntrue;

returnfalse;

}

遞歸實現(xiàn)

//如果樹中不存在key，返回false

//存在，刪除后，返回true

bool_EraseR(Node*root,constKkey)

if(root==nullptr)

returnfalse;

if(root-_keykey)

return_EraseR(root-_right,key);

elseif(root-_keykey)

return_EraseR(root-_left,key);

else

//找到了，root就是要刪除的節(jié)點

if(root-_left==nullptr)

Node*del=root;

root=root-_right;

deletedel;

elseif(root-_right==nullptr)

Node*del=root;

root=root-_left;

deletedel;

else

Node*minRight=root