排序二叉树 排序二叉树的有序序列

排序二叉树的性质如下:

若他的左子树不空,则左子树上所有的结点均小于它的根结点的值。

若他的右子树不空,则右子树上所有的结点均大于它的根结点的值。

他的左右子树也是排序二叉树。

代码:

#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;
}

  

爱华网本文地址 » http://www.413yy.cn/a/25101016/301643.html

更多阅读

发财树的养殖方法和注意事项 发财树摆放禁忌

发财树的养殖方法和注意事项——简介发财树的养殖方法和注意事项,特点:耐阴,耐旱要诀:防湿,防冻发财树的养殖方法和注意事项——工具/原料盆土水肥料发财树的养殖方法和注意事项——方法/步骤发财树的养殖方法和注意事项 1、一、环境的

金钱树的养殖方法 金钱树叶子发黄怎么办

最近2至3年,有一种被称作金钱树的观叶植物,从南到北闪亮登场,售价不菲,每株价格高达数百元,且销路颇好。它于1997年从荷兰引进在广州芳村和顺德 陈村露面,1999年昆明世博会上,人们还不清楚其姓啥名甚,仅以其外部形态特征将其称作“金钱树”

香樟树的外形特征和作用 香樟树春夏秋冬的特点

香樟树的外形特征和作用——简介香樟树是常绿乔木,一年四季都是绿色而且有香气。香樟树的全身都是宝,从树叶到树根,都可以入药,而且还是非常优良的木材。下面winterpoem就给大家介绍一下香樟树的外形特征及其作用。香樟树的外形特征和

上好小学二年级体育课的感想_cth 小学二年级体育课游戏

今年是我第2次上小学二年级的体育课,而且还是两个班级,比去年增加了一个班级。经过去年两个学期的实践教学,多少我了解和理解低段学生上课的身心特点。对这个学期上好二年级的课,做好扎实的基础。如果你没有了解二年级学生的兴趣爱好,或

声明:《排序二叉树 排序二叉树的有序序列》为网友追妚廽歲枂分享!如侵犯到您的合法权益请联系我们删除