二叉查找樹的拔出,刪除,查找。本站提示廣大學習愛好者：（二叉查找樹的拔出,刪除,查找）文章只能為提供參考，不一定能成為您想要的結果。以下是二叉查找樹的拔出,刪除,查找正文
二叉查找樹是知足以下前提的二叉樹：
1、左子樹上的一切節點值均小於根節點值，
2、右子樹上的一切節點值均不小於根節點值，
3、閣下子樹也知足上述兩個前提。
二叉查找樹的拔出進程以下：
1.若以後的二叉查找樹為空，則拔出的元素為根節點，
2.若拔出的元素值小於根節點值，則將元素拔出到左子樹中，
3.若拔出的元素值不小於根節點值，則將元素拔出到右子樹中。
二叉查找樹的刪除，分三種情形停止處置：
1.p為葉子節點，直接刪除該節點，再修正其父節點的指針（留意分是根節點和不是根節點），如圖a。
2.p為單支節點（即只要左子樹或右子樹）。讓p的子樹與p的父親節點相連，刪除p便可；（留意分是根節點和不是根節點）；如圖b。
3.p的左子樹和右子樹均不空。找到p的後繼y，由於y必定沒有左子樹，所以可以刪除y，並讓y的父親節點成為y的右子樹的父親節點，並用y的值取代p的值；或許辦法二是找到p的先驅x，x必定沒有右子樹，所以可以刪除x，並讓x的父親節點成為y的左子樹的父親節點。如圖c。
拔出節點的代碼：
struct node
{
int val;
pnode lchild;
pnode rchild;
};
pnode BT = NULL;
//遞歸辦法拔出節點
pnode insert(pnode root, int x)
{
pnode p = (pnode)malloc(LEN);
p->val = x;
p->lchild = NULL;
p->rchild = NULL;
if(root == NULL){
root = p;
}
else if(x < root->val){
root->lchild = insert(root->lchild, x);
}
else{
root->rchild = insert(root->rchild, x);
}
return root;
}
//非遞歸辦法拔出節點
void insert_BST(pnode q, int x)
{
pnode p = (pnode)malloc(LEN);
p->val = x;
p->lchild = NULL;
p->rchild = NULL;
if(q == NULL){
BT = p;
return ;
}
while(q->lchild != p && q->rchild != p){
if(x < q->val){
if(q->lchild){
q = q->lchild;
}
else{
q->lchild = p;
}
}
else{
if(q->rchild){
q = q->rchild;
}
else{
q->rchild = p;
}
}
}
return;
}
查找節點的代碼：
pnode search_BST(pnode p, int x)
{
bool solve = false;
while(p && !solve){
if(x == p->val){
solve = true;
}
else if(x < p->val){
p = p->lchild;
}
else{
p = p->rchild;
}
}
if(p == NULL){
cout << "沒有找到" << x << endl;
}
return p;
}
刪除節點的代碼
bool delete_BST(pnode p, int x) //前往一個標記，表現能否找到被刪元素
{
bool find = false;
pnode q;
p = BT;
while(p && !find){ //尋覓被刪元素
if(x == p->val){ //找到被刪元素
find = true;
}
else if(x < p->val){ //沿左子樹找
q = p;
p = p->lchild;
}
else{ //沿右子樹找
q = p;
p = p->rchild;
}
}
if(p == NULL){ //沒找到
cout << "沒有找到" << x << endl;
}
if(p->lchild == NULL && p->rchild == NULL){ //p為葉子節點
if(p == BT){ //p為根節點
BT = NULL;
}
else if(q->lchild == p){
q->lchild = NULL;
}
else{
q->rchild = NULL;
}
free(p); //釋放節點p
}
else if(p->lchild == NULL || p->rchild == NULL){ //p為單支子樹
if(p == BT){ //p為根節點
if(p->lchild == NULL){
BT = p->rchild;
}
else{
BT = p->lchild;
}
}
else{
if(q->lchild == p && p->lchild){ //p是q的左子樹且p有左子樹
q->lchild = p->lchild; //將p的左子樹鏈接到q的左指針上
}
else if(q->lchild == p && p->rchild){
q->lchild = p->rchild;
}
else if(q->rchild == p && p->lchild){
q->rchild = p->lchild;
}
else{
q->rchild = p->rchild;
}
}
free(p);
}
else{ //p的閣下子樹均不為空
pnode t = p;
pnode s = p->lchild; //從p的左子節點開端
while(s->rchild){ //找到p的先驅，即p左子樹中值最年夜的節點
t = s;
s = s->rchild;
}
p->val = s->val; //把節點s的值賦給p
if(t == p){
p->lchild = s->lchild;
}
else{
t->rchild = s->lchild;
}
free(s);
}
return find;
}
