二叉查找树（二叉排序树）操作大全C++实现-蒲公英云

// 链式二叉查找树的各种操作.cpp : Defines the entry point for the console application.
//

#include “stdafx.h”
#include
using namespace std;

struct BSTree
{
int data;
BSTree *left;
BSTree *right;
};
//标记在插入时，如果已存在，则为true ，表示不需要插入，否则为false
bool flag = false;
int a[100];
//查找操作
BSTree *search(BSTree *r,int x)
{
if(r==NULL)
return NULL;
else
{
if(r->data==x)
return r;
else if(r->data>x)
return search(r->left,x);
else
return search(r->right,x);
}
}
//返回最小值节点
BSTree *BSTMinNum(BSTree *r)
{
BSTree *s=r;
while(s->left!=NULL)
{
s=s->left;
}
return s;
}
//返回最大值节点
BSTree *BSTMaxNum(BSTree *r)
{
BSTree *s=r;
while(s->right!=NULL)
{
s=s->right;
}
return s;
}
//获得其父节点
BSTree *getFather(BSTree *r, BSTree *s)
{
BSTree *sf;
if(r==NULL||r==s)
sf=NULL;
else
{
if(s==r->left||s==r->right)
sf= r;
else if(s->data > r->data)
sf=getFather(r->right,s);
else
sf=getFather(r->left,s);
}
return sf;
}
//获得节点中序的前趋节点
//此操作不需要遍历树
BSTree *searchPreMidOrder(BSTree *r,int val)
{
BSTree *s = search(r,val);
if(s==NULL)
return NULL;
else
{
//如果左儿子节点非空，则找到左子树的最大值节点
if(s->left!=NULL)
return BSTMaxNum(s->left);
//如果左儿子节点空，则找到第一个有右儿子节点的其祖辈节点
BSTree *p = getFather(r,s);
while(p!=NULL&&s==p->left)
{
s=p;
p=getFather(r,s);
}

return p;
}
}
//获得节点中序的后继节点
//此操作不需要遍历树
BSTree *searchPostMidOrder(BSTree *r,int val)
{
BSTree *s = search(r,val);
if(s==NULL)
return NULL;
else
{
//如果右儿子节点非空，则找到右子树的最小值节点
if(s->right!=NULL)
{
return BSTMinNum(s->right);
}
//如果右儿子节点为空，则找到第一个有左儿子节点的其祖辈节点
BSTree *p = getFather(r,s);
while(p!=NULL&&s==p->right)
{
s=p;
p=getFather(r,s);
}
return p;
}
}
//插入操作
BSTree* insert(BSTree *r,BSTree *s)
{
//首先查找树中是否已存在此节点
BSTree *p = search(r,s->data);
if(p==NULL)
{
flag = false;
if(r==NULL)
{
r=s;
}
else if(s->datadata)
r->left = insert(r->left,s);
else if(s->data>r->data)
r->right = insert(r->right,s);
}
else
flag = true;
return r;
}
//建树
BSTree * createBSTree(BSTree *r,int *a,int n)
{
int i;
BSTree * t;
t = r;
for(i=0;idata=a[i];
s->left=NULL;
s->right=NULL;
t = insert(t,s);
}
return t;
}

//删除操作
BSTree * deleteNode(BSTree *r,BSTree *s)
{
//BSTNODE * temp, * tfather, * pf;
BSTree *temp,*father,*sf;
//pf = getfather(p, r);
sf=getFather(r,s);
//被删除结点是叶子结点, 不是根结点
if(s->left==NULL&&s->right==NULL&&sf!=NULL)
//
if(sf->left==s)
sf->left=NULL;
//
else
sf->right=NULL;
//被删除结点是叶子结点,又是根结点
else if(s->left==NULL&&s->right==NULL&&sf==NULL)
r=NULL;
//被删除结点有右孩子,无左孩子.被删结点是根结点
else if(s->left==NULL&&s->right!=NULL&&sf!=NULL)
if(sf->left==s)
sf->left=s->right;
else
sf->right=s->right;
//被删除结点有右孩子,无左孩子.被删结点是根结点
else if(s->left==NULL&&s->right!=NULL&&sf==NULL)
r=s->right;
//被删结点有左孩子,无右孩子.被删结点不是根结点
else if(s->left!=NULL&&s->right==NULL&&sf!=NULL)
if(sf->left==s)
sf->left=s->left;
else
sf->right=s->left;
//被删结点有左孩子,无右孩子.被删结点是根结点
else if(s->left!=NULL&&s->right==NULL&&sf==NULL)
r=s->left;
else if(s->left!=NULL&&s->right!=NULL)
{
temp = s->left;
father = s;
//找出左子树最大的节点
while(temp->right!=NULL)
{
father=temp;
temp=temp->right;
}
s->data = temp->data;
if(father!=s)
father->right = temp->left;
else
father->left=temp->left;
}
if(r==NULL)
cout<<”删除之后，二叉排序树为空！”<data<<” “;
preOrder(r->left);
preOrder(r->right);
}
}
//中序输出
void inOrder(BSTree *r)
{
if(r==NULL)
return ;
else
{
inOrder(r->left);
cout<data<<” “;
inOrder(r->right);
}
}
//后续输出
void postOrder(BSTree *r)
{
if(r==NULL)
return ;
else
{
postOrder(r->left);
postOrder(r->right);
cout<data<<” “;
}
}

*int _tmain(int argc, _TCHAR\ argv[])
{
int cases;
cout<<”请输入案例个数：”<>cases;
while(cases—)
{
memset(a,0,sizeof(a));
int n;
flag = false;
BSTree *root=NULL;
cout<<”请输入元素个数：”<>n;
int i;
cout<<”请输入这些元素：”<>a[i];
cout<<”建立二叉排序树!”<data<>s;
while(1)
{
if(s==’E’||s==’e’)
break;
else if(s==’I’||s==’i’)
{
cout<<”请输入您要插入的值：”<>x;
BSTree *p =(BSTree*)malloc(sizeof(BSTree));
p->data = x;
p->left = NULL;
p->right = NULL;
root = insert(root,p);
if(flag==false)
cout<<”插入成功！”<>cs;
while(1)
{
if(cs==1)
{
cout<<”请输入您要查找的值：”<>x;
BSTree *p=search(root,x);
BSTree *pfather=getFather(root,p);
cout<<”查找的值为：”<data<data<left==NULL&&p->right==NULL)
cout<<”它是叶子节点，没有子节点”<left != NULL)
cout<<”其左儿子节点的值为：”<left->data<right != NULL)
cout<<”其右儿子的值为：”<right->data<data<data<>val;
BSTree *node = searchPreMidOrder(root,val);
if(node==NULL)
cout<<”不存在此其值为”<data<>val;
BSTree *node = searchPostMidOrder(root,val);
if(node==NULL)
cout<<”不存在此其值为”<data<<endl;
}
}
else if(cs==6)
break;
else
{
cout<<”输入的指令不对，请重新输入！”<<endl;

}
cout<<”请问您需要查询哪种信息？”<>cs;
}**

}
else if(s==’D’||s==’d’)
{
cout<<”请输入您要删除的节点的值：”<>value;
cout<<”你确定要删除吗？(Yy/Nn)”<>order;
while(1)
{
if(order==’Y’||order==’y’)
{
BSTree * node;
node = search(root,value);
if(node==NULL)
cout<<”该节点不存在！”<>order;
}
}
}
else if(s==’P’||s==’p’)
{
cout<<”其前序输出为：”<>s;
}
}
system(“pause”);
return 0;
}