动态查找表的一种理想数据结构。
二叉排序树的定义是：二叉排序树T是一棵树,它或者是空，或者具备一下三条性质：
（1）、如果T的根节点的左子树非空，其左子树所有结点的值均小于T的根节点的值
（2）、如果T的根节点的右子树非空，其右子树所有结点的值均大于T的根节点的值
（3）、T的根结点的左右子树均为二叉排序树
下面是代码：
文件"tree.h"
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
#define MAX_NODE_NUM 20 //树结点最大值
class Bin_Sort_Tree;
//树结点
class BSTnode
{
int tag;//后序遍历作为访问标志
int data;
BSTnode *lchild;
BSTnode *rchild;
friend class Bin_Sort_Tree;
};
//二叉排序树
class Bin_Sort_Tree
{
public:
int Get_data(BSTnode *p)
{
return p->data;
}
bool Search_BST(BSTnode *T,int a,BSTnode *&f,BSTnode *&p)
{
/*-----------------------------
/在树中查找值为a的结点，查找到
/了，用p保存该结点地址，f指向
/p的双亲结点
/-----------------------------*/
p=T;
while(p)
{
if(p->data==a)
return true;
else if(p->data>a)
{
f=p;
p=p->lchild;
}
else
{
f=p;
p=p->rchild;
}
}
return false;
}
//将值为a的结点插入树中，若值已存在，就不插入
void Insert_BST_1(BSTnode *&T,int a)
{
BSTnode *f=NULL;
BSTnode *p=NULL;
if(Search_BST(T,a,f,p))
return; //树中已有值相同结点，不插入
else
{
BSTnode *s=new BSTnode;
s->data=a;
s->lchild=s->rchild=NULL;
if(s->data>f->data)
f->rchild=s;
else
f->lchild=s;
}
}
void Insert_BST_2(BSTnode *&T,int a) //插入算法递归实现
{
if(!T)
{
cout<<"树为空"<<endl;
return;
}
if(T->data>a)
{
if(!T->lchild)
{
T->lchild=new BSTnode;
T->lchild->data=a;
T->lchild->lchild=NULL;
T->lchild->rchild=NULL;
return;
}
else
Insert_BST_2(T->lchild,a);
}
if(T->data<a)
{
if(!T->rchild)
{
T->rchild=new BSTnode;
T->rchild->data=a;
T->rchild->lchild=NULL;
T->rchild->rchild=NULL;
return;
}
else
Insert_BST_2(T->rchild,a);
}
}
void Create_BSTree(BSTnode *&T) //建树
{
cout<<"输入二叉排序树的元素,输入-1代表结束输入：";
int num[MAX_NODE_NUM];
int a,i=0;
while(cin>>a && a!=-1)
{
num[i]=a;
i++;
}
if(num[0]==-1)
{
cout<<"排序树为空"<<endl;
return;
}
int k=i;
T=new BSTnode;
T->data=num[0];
T->lchild=T->rchild=NULL;
for(i=1;i<k;i++)
Insert_BST_1(T,num[i]);
cout<<"____建树完成____"<<endl;
}
void Delete_BST(BSTnode *&T,int a)//删除结点值为a的结点
{
/*---------------------------------------------------------
/ 从树中删除一个节点后，要保证删后的树还是一棵二叉排序树，
/ 删除前，首先是在树中查找是否有这个结点，用p指向该结点，
/ 用f指向p的双亲结点，这个结点在树中的位置有下面四种情况:
/
/ 1:如果p指向的结点是叶子结点，那么直接将f指针的左子树或者
/ 右子树置空，然后删除p结点即可。
/
/ 2:如果p指向的结点是只有左子树或右子树，那么只需要让p结点
/ 原来在f中的位置(左子树或右子树)用p的子树代替即可。
/
/ 3:如果p所指向的结点是根节点，那么直接将根节点置空
/
/ 4:如果p所指向的结点左右子树都非空，为了删除p后原序列的顺
/ 序不变，就需要在原序列中先找出p的直接前驱(或者直接后继)
/ 结点用那个结点的值来代替p结点的值，然后再删掉那个直接前
/ 驱(或者直接后继)结点。
/ 在中序遍历序列中找结点的直接前驱的方法是顺着结点的左孩子
/ 的右链域开始，一直到结点右孩子为空为止。
/---------------------------------------------------------*/
BSTnode *f=NULL;
BSTnode *p=NULL;
BSTnode *q=NULL;
BSTnode *s=NULL;
if(Search_BST(T,a,f,p))
{
if(p->lchild && p->rchild)
{
q=p;
s=p->lchild;
while(s->rchild)
{
q=s;
s=s->rchild;
}
p->data=s->data;
//s指向要删除结点的直接前驱，且s是一定没有右子树的
if(q!=p)
q->rchild=s->lchild;
else
q->lchild=s->lchild;//这种情况是,q的左子树的右子树为空时
delete s;
cout<<"结点删除成功"<<endl;
return ;
}
else
{
if(!p->lchild) //左子树为空
{
q=p;
p=p->rchild;
}
else //右子树为空
{
q=p;
p=p->lchild;
}
//下面将p所指向的子树连接到f所指(被删结点的双亲)的结点上
if(!T) //被删的结点为根节点
T=p;
else if(q==f->lchild)
f->lchild=p;
else
f->rchild=p;
delete q;
cout<<"结点删除成功"<<endl;
return;
}
}
else
{
cout<<"要删除的结点不存在"<<endl;
return ;
}
}
//下面是二叉树的四种遍历方式，都是非递归方式实现
void PreOrder_Traverse(BSTnode *T) //前序遍历
{
stack<BSTnode *> s;
BSTnode *p;
p=T;
while(p || !s.empty())
{
if(p)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
else
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
void InOrder_Traverse(BSTnode *T) //中序遍历
{
stack<BSTnode *> s;
BSTnode *p=T;
while(p || !s.empty())
{
if(p)
{
s.push(p);
p=p->lchild;
}
else
{
p=s.top();
s.pop();
cout<<p->data<<" ";
p=p->rchild;
}
}
}
void PostOrder_Traverse(BSTnode *T) //后序遍历
{
stack<BSTnode *> s;
BSTnode *p=T;
while(p || !s.empty())
{
if(p)
{
p->tag=0;
s.push(p);
p=p->lchild;
}
else
{
p=s.top();
if(p->tag)
{
cout<<p->data<<" ";
s.pop();
p=NULL;
}
else
{
p->tag=1;
p=p->rchild;
}
}
}
}
void LevelOrder_Traverse(BSTnode *T) //层次遍历
{
queue<BSTnode *> q;
BSTnode *p=T;
q.push(p);
while(!q.empty())
{
p=q.front();
q.pop();
cout<<p->data<<" ";
if(p->lchild)
q.push(p->lchild);
if(p->rchild)
q.push(p->rchild);
}
}
};
主函数"main.cpp"
#include"tree.h"
int main()
{
Bin_Sort_Tree tree;
BSTnode *root=NULL;
cout<<"_____建立二叉排序树____"<<endl;
tree.Create_BSTree(root);
cout<<"前序遍历二叉树为：";
tree.PreOrder_Traverse(root);
cout<<endl;
cout<<"中序遍历二叉树为：";
tree.InOrder_Traverse(root);
cout<<endl;
cout<<"后序遍历二叉树为：";
tree.PostOrder_Traverse(root);
cout<<endl;
cout<<"层次遍历二叉树为：";
tree.LevelOrder_Traverse(root);
cout<<endl;
int data;
BSTnode *f=NULL;
BSTnode *p=NULL;
cout<<"输入你要搜索的结点的值：";
cin>>data;
if(tree.Search_BST(root,data,f,p))
{
cout<<"你所搜索的结点地址为："<<p<<endl;
cout<<"他的双亲结点值为："<<tree.Get_data(f)<<endl;
}
else
cout<<"树中没有你要找的结点"<<endl;
cout<<"输入你要删除的结点的值：";
cin>>data;
tree.Delete_BST(root,data);
cout<<"删除后的二叉树的中序遍历为：";
tree.InOrder_Traverse(root);
cout<<endl;
cout<<"输入你要插入树中的值：";
cin>>data;
tree.Insert_BST_2(root,data);
cout<<"插入后，树的中序遍历为：";
tree.InOrder_Traverse(root);
cout<<endl;
return 0;
}
下面是测试结果
_____建立二叉排序树____ 输入二叉排序树的元素,输入-1代表结束输入：5 7 3 2 9 4 8 8 1 10 -1 ____建树完成____ 前序遍历二叉树为：5 3 2 1 4 7 9 8 10 中序遍历二叉树为：1 2 3 4 5 7 8 9 10 后序遍历二叉树为：1 2 4 3 8 10 9 7 5 层次遍历二叉树为：5 3 7 2 4 9 1 8 10 输入你要搜索的结点的值：7 你所搜索的结点地址为：00380D18 他的双亲结点值为：5 输入你要删除的结点的值：10 结点删除成功 删除后的二叉树的中序遍历为：1 2 3 4 5 7 8 9 输入你要插入树中的值：6 插入后，树的中序遍历为：1 2 3 4 5 6 7 8 9 Press any key to continue
按照一开始建树时的输入，生成的树为：
