爱华网排序二叉树的性质如下：
若他的左子树不空，则左子树上所有的结点均小于它的根结点的值。
若他的右子树不空，则右子树上所有的结点均大于它的根结点的值。
他的左右子树也是排序二叉树。
代码：
#include<iostream>
using namespace std;
struct node{//树的节点
intValue;
node *left;
node *right;
};
//中序遍历
void circle(node *p)
{
if(NULL == p)
return;
circle(p->right);
cout <<p->Value << ' ';
circle(p->left);
}
//树类
class Tree{
public:
Tree(){head =NULL;}//构造函数
void Create(int [],int);//创建二叉排序树
voidadd(int);//增加
voiddel(int);//删除
voidOutput();//输出
private:
node*head;//根节点
intLength;//总长度
};
//创建二叉排序树
void Tree::Create(int number[], intLength_array)
{
node*p = new node;
p->Value = number[0];
p->left =NULL;
p->right = NULL;
head = p;
Length = Length_array;
//后面的数据
for(int i = 1; i < Length_array;i++)
{
node *q = new node;
q->Value =number[ i];
q->left= NULL;
q->right =NULL;
p = head;
node *t = p;
int count; //判别是左还是右节点
while(p !=NULL)
{
t = p;
if(q->Value> p->Value)
{
p= p->right;
count= 1;
continue;
}
if(q->Value< p->Value)
{
p= p->left;
count= 0;
}
}
if(count)
t->right= q;
else
t->left= q;
}
}
//增加
void Tree::add(int N)
{
node *q = new node;
q->Value = N;
q->left =NULL;
q->right = NULL;
node *p = head;
node *t = p;
int count;
while(p != NULL)
{
t = p;
if(q->Value> p->Value)
{
p =p->right;
count =1;
continue;
}
if(q->Value< p->Value)
{
p =p->left;
count =0;
continue;
}
if(q->Value ==p->Value)
{
cout<< "THE NUMBER IS EXIST!"<< endl;
return;
}
}
if(count)
t->right =q;
else
t->left= q;
Length++;
}
void Tree::del(intN)
{
node *p = head;
node *t = p;
int count;
while(p != NULL)
{
if(N >p->Value)
{
t = p;
p =p->right;
count =1;
continue;
}
if(N <p->Value)
{
t = p;
p =p->left;
count =0;
continue;
}
if(N ==p->Value)
{
break;
}
}
//没有要删的节点
if(NULL == p)
{
cout<< "NO ELEMENT!"<< endl;
return;
}
int sign = 0; //如果删除的是根节点
if(p == head)
sign = 1;
//删除的是叶子节点
if(p->left == NULL&& p->right ==NULL)
{
if(sign) //根节点
{
head =NULL;
delete(p);
return;
}
if(count)
t->right= NULL;
else
t->left= NULL;
delete(p);
return;
}
//只有右节点
if(p->left == NULL&& p->right !=NULL)
{
if(sign) //根节点
{
head =p->right;
delete(p);
return;
}
if(count)
{
t->right= p->right;
}
else
{
t->left= p->right;
}
delete(p);
return;
}
//只有左节点
if(p->right== NULL && p->left!= NULL)
{
if(sign)
{
head =p->left;
delete(p);
return;
}
if(count)
t->right= p->left;
else
t->left= p->left;
delete(p);
return;
}
//两边都有
if(count&& !sign)
t->right =p->left;
else if(!sign)
t->left= p->left;
node *next =p->left;
while(next->right != NULL)
next =next->right;
next->right =p->right;
if(sign)
head =p->left;
delete(p);
}
//输出
void Tree::Output()
{
node *p = head;
if(NULL == p)
{
cout<< "NO ELEMENT"<< endl;
return;
}
circle(p);
cout << endl;
}
//测试数据
int main()
{
Tree tree;
int num[10] = {12, 45, 24, 57, 23, 232, 1111, 1,34, 2};
tree.Create(num,10);//创建树
tree.Output();
tree.add(123);//增加数
tree.add(0);
tree.Output();
tree.del(23);//删除叶子节点
tree.del(1111);
tree.del(123);
tree.Output();
tree.del(232);
tree.del(2);
tree.Output();
tree.del(2);//删除不存在的节点
tree.del(24);//删除度为1的节点
tree.Output();
tree.del(1);
tree.Output();
tree.add(21);
tree.add(21);//重复加数
tree.add(35);
tree.add(46);
tree.add(90);
tree.Output();
tree.del(57);//删除度为2的节点
tree.Output();
tree.del(12);//删除根节点
tree.Output();
return 0;
}
