【算法设计-二叉搜索树】二叉查找树的操作与实现

二叉查找树某个结点的左子树的值都比它小，其右子树的值比它大。

要实现的主要操作

代码实现

#include <iostream>  
using namespace std;
// BST的结点  
typedef struct node
{
int key;
struct node *lChild, *rChild,*parent;
}Node, *BST;
BST lvis=NULL;//用来保存父节点的地址
void createBST(BST &p);
void assignmentParent(BST p);//给所有的结点的父节点赋值。
// 在给定的BST中插入结点，其数据域为element, 使之称为新的BST  
bool BSTInsert(Node *&p, int element)
{
if (p == NULL)
{
p = new Node;
p->key = element;
p->lChild = p->rChild = NULL;


}
if (element == p->key)
{
return false;
}
if (element < p->key)
{
BSTInsert(p->lChild, element);
}
else
BSTInsert(p->rChild, element);
return true;
}


void PrintBST(BST &p, int depth)
{
BST &p1=p;
int i;
if (p1->rChild)
PrintBST(p1->rChild, depth + 1);
for (i = 1; i <= depth; i++)
printf("     ");
printf("%d\n", p1->key);
if (p1->lChild)
PrintBST(p1->lChild, depth + 1);
}


BST search(BST p, int key)
{
if (p == NULL)
{
printf("此树为空！\n");
return NULL;
}
else if (key == p->key)
{
printf("查找成功!,%d的地址是%p\n", key, p);
return p;
}
else if (key < p->key)
search(p->lChild, key);
else
search(p->rChild, key);
}
void createBST(BST &p)
{
int t;
int depth = 0;
p = NULL;
printf("\n请输入关键字(以-123结束建立平衡二叉树):");
scanf("%d", &t);
while (t != -123)
{
BSTInsert(p, t);
printf("\n请输入关键字(以-123结束建立平衡二叉树):");
scanf("%d", &t);
}
assignmentParent(p);//这个函数的目的是为了给所有节点的父节点赋值。
printf("\n****************************************************\n");
printf("*******************您创建的二叉树为*******************\n");
if (p)
PrintBST(p, depth);
else
printf("这是一棵空树!\n");
printf("********************二叉树创建完成*********************\n");
}
void Maximum(BST p)
{
BST p1=p;
while(p1->rChild)
{
p1=p1->rChild;
}
printf("Maximum=%d",p1->key);
}
void Minmum(BST p)
{
BST p1=p;
while(p1->lChild)
{
p1=p1->lChild;
}
printf("Minimum=%d",p1->key);
}
bool Insert(BST &p,int element)
{
if (p == NULL)
{
p = new Node;
p->key = element;
p->lChild = p->rChild = NULL;
}
if (element == p->key)
{
return false;
}
if (element < p->key)
{
Insert(p->lChild, element);
}
else
Insert(p->rChild, element);
return true;
}
void get_parent(BST &p)
{
if (p)
{
printf("%d->parent=%p",p->key,p->parent);
get_parent(p->lChild);
get_parent(p->rChild);
}
}
void assignmentParent(BST p)
{
if (p)
{
p->parent=lvis;
lvis=p;
assignmentParent(p->lChild);
lvis=p;
assignmentParent(p->rChild);
}
}
//先序遍历
void preorderBST(BST p)
{
if (p)
{
cout << p->key << " ";
preorderBST(p->lChild);
preorderBST(p->rChild);
}
}
//中序遍历（这个可以做为排序算法
void inorderBST(BST p)
{
if (p)
{
inorderBST(p->lChild);
cout << p->key << " ";
inorderBST(p->rChild);
}
}
//后序遍历
void postrderBST(BST p)
{
if (p)
{
postrderBST(p->lChild);
postrderBST(p->rChild);
cout << p->key << " ";
}
}
void Delete(BST p,int key)
{
BST p1=p;
//删除要分三种情况
while(p1->key!=key)
{
if(key>p1->key)
p1=p1->rChild;
else
p1=p1->lChild;
}
//第一种情况：如果z没有孩子结点，则只是简单的将它删除，并修改它的父节点。用NIL作为孩子来替换z（现在还没有考虑其为根节点）
if(p1->lChild==NULL&&p1->rChild==NULL)
{
if(p1->parent==NULL)
{
printf("已经删除根节点！，此时树为空哦\n");
p=NULL;
return;
}
if(p1->key<p1->parent->key)
p1->parent->lChild=NULL;
else
p1->parent->rChild=NULL;
}
//第二种情况：如果只有一个孩子，则将这个孩子提升到树中z的位置上，并修改z的父节点，用z的孩子来替换z
{
if(p1->lChild!=NULL&&p1->rChild==NULL)
{
if(p1->key<p1->parent->key)
{
p1->parent->lChild=p1->lChild;
p1->lChild->parent=p1->parent;
}
else
{
p1->parent->rChild=p1->lChild;
p1->lChild->parent=p1->parent;
}
}
if(p1->rChild!=NULL&&p1->lChild==NULL)
{
if(p1->key<p1->parent->key)
{
p1->parent->lChild=p1->rChild;
p1->rChild->parent=p1->parent;
}
else
{
p1->parent->rChild=p1->rChild;
p1->rChild->parent=p1->parent;
}
}
//第三种情况
if(p1->lChild!=NULL&&p1->rChild!=NULL)
{
Node *y=p1->rChild->lChild;
while(y!=NULL)
y=y->lChild;
//先用y的右孩子替换y
y->rChild->parent=y->parent;
//用y替换z
y->rChild=p1->rChild;
p1->rChild->parent=y;
y->lChild=p1->lChild;
p1->lChild->parent=y;
y->parent=p1->parent;
if(p1->parent->key>p1->key)
p1->parent->lChild=y;
else
p1->parent->rChild=y;
}
}
}
int main(void)
{
int ch;
BST T;
printf("请写入您要建立的BST树的所有结点值!\n");
createBST(T);
while (1)
{
printf("\n***************************************\n");
printf("*****按下列选项选择您要进行的操作******\n");
printf("*****1前序输出.************************\n");
printf("*****2.中序输出************************\n");
printf("*****3.后序输出************************\n");
printf("*****4.查找****************************\n");
printf("*****5.求最大值************************\n");
printf("*****6.求最小值************************\n");
printf("*****7.插入数值************************\n");
printf("*****8.获得父节点地址******************\n");
printf("*****9.删除数值************************\n");
printf("*****10.打印排序二叉树*****************\n");
printf("*****11.退出***************************\n");
printf("***************************************\n");
scanf("%d", &ch);
switch (ch)
{
case 1:
preorderBST(T); break;
case 2:
inorderBST(T); break;
case 3:
postrderBST(T);break;
case 4:
{
int m;
printf("您要查找的是多少:");
scanf("%d", &m);
search(T, m);
}
break;
case 5:
Maximum(T); break;
case 6:
Minmum(T);break;
case 7:
{
printf("您要插入多少:");
int key;
scanf("%d",&key);
Insert(T,key);
}break;
case 8:
get_parent(T);
break;
case 9:
{
printf("您要删除多少:");
int key;
scanf("%d",&key);
Delete(T,key);
}
break;
case 10:
PrintBST(T,0);
break;
case 11:
return 0; break;
default:
break;
}
}
return 0;
}

删除操作详解