验证中...
私信发送成功
平衡二叉树操作的演示.cpp
原始数据 复制代码
#include <iostream>
#include <cstdio>
using namespace std;
typedef struct
{
char key;
}ElemType;
typedef struct BSTNode
{
ElemType data;
BSTNode *lchild, *rchild;
}BSTNode, *BSTree;
int n;
BSTree SearchBST(BSTree T,char key) {
//在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
//若查找成功,则返回指向该数据元素结点的指针,否则返回空指针
if((!T)|| key==T->data.key) return T; //查找结束
else if (key<T->data.key) return SearchBST(T->lchild,key); //在左子树中继续查找
else return SearchBST(T->rchild,key); //在右子树中继续查找
} // SearchBST
void InsertBST(BSTree &T, ElemType e)
{ //当二叉排序树T中不存在关键字等于e.key的数据元素时,则插入该元素
if(!T){
BSTree S = new BSTNode;
S->data = e;
S->lchild = S->rchild = NULL; //新结点*S作为叶子结点
T = S;
}else if(e.key < T->data.key)
InsertBST(T->lchild, e);
else if (e.key> T->data.key)
InsertBST(T->rchild, e);
}
void CreateBST(BSTree &T)
{ //依次读入一个关键字为key的结点,将此结点插入二叉排序树T中
T = NULL;
ElemType e;
cin >> e.key;
while(e.key!='#'){ //#作为输入结束标志
n++;
InsertBST(T, e);
cin>>e.key;
}
}
void DeleteBST(BSTree &T, char key)
{//从二叉排序树T中删除关键字等于key的结点
BSTree p = T;
BSTree f = NULL;
BSTree q;
BSTree s;
while(p){
if(p->data.key == key)
break;
f = p; //*f为*p的双亲结点
if(p->data.key > key)
p = p->lchild; //在*p的左子树中继续查找
else
p = p->rchild; //在*p的右子树中继续查找
}
if(!p){
cout<<"并不存在该点"<<endl;
return;
}
if(p->lchild && p->rchild){ //被删结点*p左右子树均不空
q = p;
s = p->lchild;
while(s->rchild){
//向右到尽头
q = s;
s = s->rchild;
}
p->data = s->data; //s指向被删结点的“前驱”
if(q != p){
q->rchild = s->lchild;
}
else{
q->lchild = s->lchild;
}
delete s;
}
else{ //被删结点*p无右子树,只需重接其左子树
if(!p->rchild){
q = p;
p = p->lchild;
}
else if(!p->lchild){ //被删结点*p无左子树,只需重接其右子树
q = p;
p = p->rchild;
}
if(!f)
T = p;
else if(q == f->lchild)
f->lchild = p;
else
f->rchild = p;
delete q;
}
n--;
}
//中序遍历
void InOrderTraverse(BSTree &T)
{
if(T)
{
InOrderTraverse(T->lchild);
cout<<T->data.key;
InOrderTraverse(T->rchild);
}
}
void Print(BSTree &T, int n)
{
int i;
if(T){
Print(T->rchild,n+5);
for(i = 0; i < n; i++){
cout<<(" ");
}
printf("%5c\n",T->data.key);
Print(T->lchild, n+5);
}
}
void menu()
{
cout<<"-------------------平衡二叉树------------------------"<<endl;
cout<<"1.创建平衡二叉树"<<endl;
cout<<"2.查找元素"<<endl;
cout<<"3.删除元素"<<endl;
cout<<"4.退出"<<endl;
}
int main()
{
BSTree T, result;
int sel,flag = 1;
char key;
while(flag){
menu();
cin>>sel;
switch(sel)
{
case 1: cout<<"请输入一行字符,以#结束输入"<<endl;
CreateBST(T);
cout<<"当前有序二叉树中序遍历结果为"<<endl;
InOrderTraverse(T);
cout<<endl;
Print(T, n);
break;
case 2: cout<<"请输入待查找字符"<<endl;
cin>>key;
result=SearchBST(T,key);
if(result)
{cout<<"找到字符"<<key<<endl;}
else
{cout<<"未找到"<<key<<endl;}
break;
case 3: cout<<"请输入待删除的字符"<<endl;
cin>>key;
DeleteBST(T,key);
cout<<"当前有序二叉树中序遍历结果为"<<endl;
InOrderTraverse(T);
cout<<endl;
Print(T, n);
break;
case 4: flag = 0;
break;
}
}
cout<<"谢谢您的使用"<<endl;
return 0;
}

评论列表( 0 )

你可以在登录后,对此项目发表评论

6_float_left_people 6_float_left_close