二叉树排序算法实现（数据结构课程设计）

数据结构课程设计（C版语言）二叉排序树算法~

下面的程序包含了树二叉树的所有操作
在二叉树的应用中有二叉排序树。
都是C语言，只不过用了C++的cin(输入)和cout（输出）,因为这两个不需要格式控制符。
//建一个工程：包含头文件：bittree.h Cpp文件：bittree.cpp main函数:main.cpp
编译运行就可以了。

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//头文件 bittree.h
#ifndef _DEF
#define _DEF
#include
#include
#include
using namespace std;
#define TURE 1
#define OK 1
#define FALSE 0
#define ERROR 0
#define INFEASIBLE -1//不可实行的
#define OVERFLOW -2
typedef int stadus;
typedef char Telemtype;
//typedef int Telemtype2;//为了二叉排序树的创建
typedef char ElemType;
#define STACK_SIZE 100;
#define STACKINCREMENT 10;

//二叉树
typedef struct bitnode{
Telemtype data;
struct bitnode *lchild,*rchild;
}BitNode,*BitTree;
extern stadus CreateBitTree(BitTree &T);
extern stadus PreOrderTraverse(BitTree T);
extern stadus InOrderTraverse(BitTree T);
extern stadus PostOrderTraverse(BitTree T);

typedef BitNode selemtypechar;
typedef BitTree selemtypechar2;

// 栈
typedef struct SqStack{
selemtypechar2 *base;
selemtypechar2 *top;
int stacksize;
}sqstack;
extern stadus initstackC(sqstack &S);
extern stadus gettopC(sqstack S,selemtypechar2 &e);
extern stadus pushC(sqstack &S,selemtypechar2 e);
extern stadus popC(sqstack &S,selemtypechar2 &e);
extern stadus destroyC(sqstack &S);//销毁
extern stadus clearC(sqstack &S);//置空
extern stadus stackempty(sqstack S);

//栈实现二叉树的输出
extern stadus PreOrderTraverse2(BitTree T);
extern stadus InOrderTraverse2(BitTree T);
extern stadus PostOrderTraverse2(BitTree T);
//二叉树的应用
extern stadus Depth(BitTree T);
extern stadus Single(BitTree T);
extern stadus Double(BitTree T);
extern stadus CountLeaf(BitTree T);
extern void Change_Left_Right(BitTree T);
//二叉层次遍历用到队列
typedef BitTree Qelemtype;
typedef struct QNode{
Qelemtype data;
struct QNode *next;
}qnode,*QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
}LinkQueue;
extern stadus InitQueue(LinkQueue &Q);
extern stadus DestroyQueue(LinkQueue &Q);
extern stadus EnterQueue(LinkQueue &Q,Qelemtype e);
extern stadus DeQueue(LinkQueue &Q,Qelemtype &e);
//二叉层次遍历
extern stadus LevelOrder(BitTree T);
//二叉排序树
extern void insert(BitTree &T,ElemType x);
extern void CreateBiTree2(BitTree &root);

#endif
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//cpp文件 bittree.cpp
#include "bittree.h"
#include

stadus initstackC (sqstack &s)
{
s.base=(selemtypechar2 *)malloc(100*sizeof(selemtypechar));//用STACKINCREMENT会报错？？？
if (!s.base) exit(OVERFLOW);
s.top=s.base;
s.stacksize=100;
return OK;
}
stadus gettopC(sqstack s,selemtypechar2 &e)
{
if(s.base==s.top) return ERROR;
e=*(s.top-1);
return OK;
}
stadus pushC(sqstack &s,selemtypechar2 e)
{
if ((s.top-s.base)>=s.stacksize)
{
s.base=(selemtypechar2 *)realloc(s.base,((s.stacksize+10)*(sizeof(selemtypechar))));
if(!s.base) exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=10;
}
*(s.top++)=e;
//s.top++;
return OK;
}
stadus popC(sqstack &s,selemtypechar2 &e)
{
if(s.top==s.base) return ERROR;
--s.top;
e=*(s.top);
return OK;
}
stadus destroyC(sqstack &s)
{
free(s.base); s.base=NULL;s.top=NULL;
return OK;
}
stadus clearC(sqstack &s)
{
s.top=s.base;
return OK;
}
stadus stackempty(sqstack s)
{
if(s.top!=s.base) return ERROR;
else
return OK;
}

//二叉树
stadus CreateBitTree(BitTree &T)//创建
{
Telemtype ch;
cin>>ch;
if(ch=='#') T=NULL;
else{
T=(BitTree)malloc(sizeof(BitNode));
if (!T) exit (OVERFLOW);
T->data=ch;
CreateBitTree(T->lchild);
CreateBitTree(T->rchild);
}
return OK;
}
stadus PreOrderTraverse(BitTree T)//先序访问
{
if(!T) return ERROR;
else if (T)
{
coutdata<<" ";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
return OK;
}
stadus InOrderTraverse(BitTree T)//中序
{
if(!T) return ERROR;
else if (T)
{
InOrderTraverse(T->lchild);
coutdata<<" ";
InOrderTraverse(T->rchild);
}
return OK;
}
stadus PostOrderTraverse(BitTree T)//后序
{
if(!T) return ERROR;
else if (T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
coutdata<<" ";
}
return OK;
}

//栈实现二叉树的访问
stadus PreOrderTraverse2(BitTree T)//先序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
//pushC(s,p);
while (p||!stackempty(s))
{
//popC(s,p);
if (p)
{
pushC(s,p);
if(!p->data)return ERROR;
coutdata<<" ";
//p1=p;
p=p->lchild;
if (p==NULL)
{
popC(s,p);
p=p->rchild;
}
else
pushC(s,p);

}
else {
popC(s,p);
popC(s,p);
p=p->rchild;
if (p==NULL)
{
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
p=p->rchild;
}
}
else{
pushC(s,p);
if(!p->data)return ERROR;
coutdata<<" ";
p=p->lchild;//左空不压栈
if (p==NULL)
{
popC(s,p);
p=p->rchild;
}
else
pushC(s,p);
}
}
}
destroyC(s);
return OK;
}
stadus InOrderTraverse2(BitTree T)//中序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
while (p||!stackempty(s))
{
if (p)
{
pushC(s,p);
p=p->lchild;
}
else {
popC(s,p);
if(!p->data)return ERROR;
coutdata<<" ";
p=p->rchild;
}
}
destroyC(s);
return OK;
}

stadus PostOrderTraverse2(BitTree T)//后序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
while (p||!stackempty(s))
{
if (p)
{
pushC(s,p);
p=p->lchild;
if (p==NULL)
{
popC(s,p);
//p=p->rchild;
if (p->rchild==NULL)
{
if(!p->data)return ERROR;
coutdata<<" ";
//p=p->rchild;
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
//pushC(s,p);//???右结点重复压栈？？？
//p1=p;
p=p->rchild;
//p->rchild=NULL;
}
}
else
{
p=p->rchild;
}
}
else
continue ;
}
else
{
//popC(s,p);
if(!p->data)return ERROR;
coutdata<<" ";
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
//pushC(s,p);
//p1=p;
p=p->rchild;
//p->rchild=NULL;
}
}
}
destroyC(s);
return OK;
}
//二叉树的应用

//二叉树的深度
stadus Depth(BitTree T)
{
int depthval,depthLeft,depthRight;
if (!T) depthval=0;
else{
depthLeft=Depth(T->lchild);
depthRight=Depth(T->rchild);
depthval=1+(depthLeft>depthRight?depthLeft:depthRight);
}
return depthval;
}
//二叉树的单分支结点数
stadus Single(BitTree T)
{
if (T==NULL) return 0; //空树
else if (T->lchild==NULL && T->rchild==NULL) return 0; //叶子结点
else{
if (!T->lchild && T->rchild) return Single(T->rchild)+1;//只有左单分支
if (T->lchild && !T->rchild) return Single(T->lchild)+1;//只有右单分支
if(T->lchild && T->rchild) return Single(T->lchild)+Single(T->rchild);//双分支结点
}
}
//二叉树的多分支结点数
stadus Double(BitTree T)
{

if (T==NULL) return 0; //空树
else if (T->lchild==NULL && T->rchild==NULL) return 0; //叶子结点
else{
if (!T->lchild && T->rchild) return Double(T->rchild);//只有左单分支
if (T->lchild && !T->rchild) return Double(T->lchild);//只有右单分支
if(T->lchild && T->rchild) return Double(T->lchild)+Double(T->rchild)+1;//双分支结点
}
}
//叶子结点
stadus CountLeaf(BitTree T)
{
int num,num1,num2;
if(T==NULL) num=0;
else if(T->lchild==NULL&&T->rchild==NULL)
num=1;
else
{
num1=CountLeaf(T->lchild);
num2=CountLeaf(T->rchild);
num=num1+num2;
}
return num;
}
//交换左右子树
void Change_Left_Right(BitTree T)
{
BitTree Temp;
if (T)
{
Change_Left_Right(T->lchild);
Change_Left_Right(T->rchild);
Temp=T->lchild;
T->lchild=T->rchild;
T->rchild=Temp;
}
}
//二叉层次遍历用到队列
stadus InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(100*sizeof(qnode));
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
stadus DestroyQueue(LinkQueue &Q)
{
while (Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}

stadus EnterQueue(LinkQueue &Q,Qelemtype e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(qnode));
if(!p) return ERROR;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
stadus DeQueue(LinkQueue &Q,Qelemtype &e)
{ QueuePtr p;
if(Q.front==Q.rear) return ERROR;
p=Q.front->next;e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return OK;
}
//二叉层次遍历
stadus LevelOrder(BitTree T)
{
LinkQueue Q;
BitTree B;
InitQueue(Q);
if (T!=NULL)
{
EnterQueue(Q,T);
while (!(Q.front==Q.rear))
{
DeQueue(Q,B);
coutdata<<" ";
if(B->lchild!=NULL) EnterQueue(Q,B->lchild);
if(B->rchild!=NULL) EnterQueue(Q,B->rchild);
}
}
return OK;
}
//二叉排序树
void insert(BitTree &T,ElemType x)
{
if (T==NULL)
{
T=(BitTree)malloc(sizeof(BitNode));
T->data=x;
T->lchild=T->rchild=NULL;
}
else
{
if(xdata)insert(T->lchild,x);
if(x>=T->data)insert(T->rchild,x);
}
}
void CreateBiTree2(BitTree &root)
{
ElemType x;
root=NULL;
cout"<<endl;
cout"<<endl;
cin>>x;
while (x!='#')
{
insert(root,x);
cin>>x;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//主函数 main.cpp
#include "bittree.h"
void main()
{
system("cls");
system("color f0");
BitTree T;
Create:
cout："<<endl;
CreateBitTree(T);
BitTree T1(T);
select:
cout<<''<<''<<"----------------MAIN-MENU----------------"<<endl;
cout<<''<<''<<"&1、先序输出 2、中序输出 3、后序输出 &"<<endl;
cout<<''<<''<<"&4、栈实现输出 5、重新创建二叉树 0、退出&"<<endl;
cout<<''<<''<<"------------6、二叉树的应用-------------"<<endl;
char sel;
getchar();
cin>>sel;
switch (sel)//总
{
case '0':
break;
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '4':
stackcout:
cout<<endl<<''<<" -------------------SUB-MENU1---------------------"<<endl;
cout<<''<<" &1、先序输出 2、中序输出 3、后序输出 4、返回 &"<<endl;
cout<<''<<" ------------------------------------------------"<<endl;
cin>>sel;
switch (sel)//栈关于树的输出
{
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse2(T1);//p->lchild==null,时 T 的值被修改！！！！！！！！
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse2(T);
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T1);//栈实现未写完
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '4':goto select;
default:cout<<"选择错误!!!"<<endl;
goto stackcout;
}
case '5':
goto Create;
case '6':
{
SUB_MENU2:
cout<<''<<''<<"-------------------------SUB-MENU2---------------------"<<endl;
cout<<''<<''<<"&1、二叉树的深度 2、二叉树的单分支结点数 &"<<endl;
cout<<''<<''<<"&3、二叉树的多分支结点数 4、二叉树的叶子结点数 &"<<endl;
cout<<''<<''<<"&5、二叉层次遍历 6、二叉排序树 7、交换左右子树 &"<<endl;
cout<<''<<''<<"&------------------8、输出 0、返回--------------------&"<<endl;
cin>>sel;
switch (sel)//二叉树的应用
{
case '0':
goto select;
case '1':
{
int deepth=0;
deepth=Depth(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"树的深度为："<<deepth<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '2':
{
int cou_sig;
cou_sig=Single(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的单分支结点为数："<<cou_sig<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '3':
{
int cou_dou;
cou_dou=Double(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的双分支结点数为："<<cou_dou<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '4':
{
int cou_leaf;
cou_leaf=CountLeaf(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的叶子结点数为："<<cou_leaf<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '5':
{
cout<<"二叉层次遍历的结果为："<<endl;
cout<<endl<<"---------------------------------"<<endl;
LevelOrder(T);
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '6':
{
BitTree T3;
CreateBiTree2(T3);
SUB3:
cout<<''<<"-------------------------SUB-MENU2-------------------"<<endl;
cout<<''<<" &1、先序输出 2、中序输出 3、后序输出 0、返回 &"<<endl;
cout<<''<<"-----------------------------------------------------"<<endl;
cin>>sel;
switch (sel)//二叉树的层次遍历
{
case '0':
break;
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
default:
cout<<"选择错误!!!"<<endl;
goto SUB3;
}
}
goto SUB_MENU2;
case '7':
{
Change_Left_Right(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"交换完成，请选择8输出查看!!!"<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '8':
goto select;
default:
cout<<"选择错误!!!"<<endl;
goto SUB_MENU2;
}
}
break;
default :
cout<<endl<<"选择错误!!!"<<endl;
goto select;
}
}

晕了，真是好纠结，我在写完下面的代码后，才在网上找了找，居然发现和你的题目完全一样的代码，算了，我就直接发在网上找到的文档和代码给你吧，可怜我写了这么久代码呀。。。。。已发，请注意查收。

代码写好了。
VC下经测试通过。
不过如果你还要论文之类的或者设计文档，我也比较难帮到你了。

#include
using namespace std;

class node
{
public:
node(int i):data(i),left(NULL),right(NULL){}
void inorder(node *&root) //中序遍历，符合升序输出
{
if(root!=NULL)
{
inorder(root->left);
coutdata<<' ';
inorder(root->right);
}
}
void insert(node *&ptr,int item) //在查找树中插入元素
{
if(ptr==NULL)
ptr=new node(item);
else if(itemdata)
insert(ptr->left,item);
else insert(ptr->right,item);
}
node *find(node *&ptr,int item) //在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。
{
if(ptr==NULL)
return NULL;
if(ptr->data==item)
return ptr;
else if(itemdata)
find(ptr->left,item);
else find(ptr->right,item);
}
node *&findy(node *&ptr,int item) //在查找树中查找肯定存在的元素,并返回其引用
{
if(ptr->data==item)
return ptr;
else if(itemdata)
findy(ptr->left,item);
else findy(ptr->right,item);
}
node* rl(){return left;}
node* rr(){return right;}
void dele(node *&ptr) //删除值为item所在结点
{
if(ptr->rl()==NULL&&ptr->rr()==NULL)
ptr=NULL;
else if(ptr->rr()==NULL)
ptr=ptr->rl();
else
ptr=ptr->rr();
}
private:
int data;
node *left; //左孩子结点
node *right; //右孩子结点
};

int main()
{
int t,i=0,j;
cout<<"输入数字个数(结点个数):";
cin>>t;
cout<<"输入"<<t<<"个数字，数字之间用空格隔开:";
cin>>j;
node *x=new node(j);
for(;i<t-1;i++)
{
cin>>j;
x->insert(x,j);
}
cout<<"中序遍历为:";
x->inorder(x); //作中序遍历
cout<<"
输入操作(当输入-1时程序结束):"<<endl;
cin>>j;
while(j!=-1)
{

node *t=x->find(x,j); //定位结点
if(t!=NULL)
{
node *&y=x->findy(x,j);
x->dele(y);
cout<<"中序遍历为:";
x->inorder(x);
}
else cout<<"无"<<j;
cout<<"
输入操作(当输入-1时程序结束):"<<endl;
cin>>j;
}
return 0;
}

附测试数据一组
8
22 33 1 50 88 99 77 55
33
50
51
55
-1
有什么不明的话可以M我或者留言我。

#include <malloc.h>
#include<stdio.h>
#define NUM 7 //宏定义
int i; //变量类型定义
typedef struct Node{
int data ; //数据域
struct Node *next; //指针域
}Node,*LNode; //用结构体构造结点及相应的指针

typedef struct Tree{
int data ;
struct Tree *left ;
struct Tree *right ;
}Tree,*LTree ; //用结构体构造树及相应的指针

CreateList( LNode Head ) //创建单链表
{
for(int i=1 ; i <=NUM ; i++) //创建循环，依次输入NUM个数据
{
LNode temp ; //中间结点
temp = (LNode) malloc( sizeof( Node ) ); //动态存储分配

temp-> next = NULL; //中间结点初始化
scanf("%2d",&temp-> data); //输入赋值到结点temp数据域
temp-> next = Head-> next ;
Head-> next = temp ; //将temp结点插入链表

}
return 1 ;//返回1
}

InsertSqTree( LTree &root , LNode temp ) //二叉树排序原则的设定
{
if(!root) //root为NULL时执行
{
root = (LTree)malloc(sizeof(Tree)); //动态存储分配

root-> left =NULL;
root-> right=NULL; //初始化
root-> data = temp-> data ; //赋值插入
return 1 ; //函数正常执行，返回1
}
else
{
if(root-> data>= temp-> data)
return InsertSqTree( root-> left , temp ) ; //比较插入左子树
else if(root-> data <temp-> data)
return InsertSqTree( root-> right , temp ); //比较插入右子树
}
return 1 ; //如果满足，就不做处理，返回1
}

void BianLiTree(LTree root) //采用中序遍历，实现将所有数字按从左向右递增的顺序排序
{
if(root) //root不为空执行
{BianLiTree(root-> left); //左递归处理至叶子结点，当root-> left为NULL时不执行
printf("%4d ",root-> data); //输出
BianLiTree(root-> right); //处理右结点
}
}

int main()
{
LNode Head = NULL;
LTree root = NULL ; //初始化
Head = (LNode) malloc(sizeof(Node)); //动态存储分配

Head-> next = NULL ; //初始化
printf("please input numbers:\n");//输入提示语句
if(!CreateList( Head )) //建单链表成功返回1不执行下一语句
return 0; //结束函数，返回0
LNode temp = Head-> next ; //将头指针的指针域赋值予中间结点
while( temp ) //temp为NULL时停止执行
{
if(!InsertSqTree( root ,temp )) //排序正常执行，返回1不执行下一语句
return 0 ; //结束函数，返回0
Head-> next = temp-> next ; //将中间指针的指针域赋值予头结点指针域
free(temp); //释放空间
temp = Head-> next ; //将头指针的指针域赋值予中间结点，以上三句实现了temp指针后移
}
printf("the result is:\n");//输出提示语句
BianLiTree(root); //采用中序遍历，输出并观察树结点
return 1; //函数正常结，返回1
}

/*以下是用c++ 实现的二叉排序树的源代码*/

#include<iostream.h>
typedef struct TreeNode
{
int key;
struct TreeNode *left;
struct TreeNode *right;

}treeNode;

class BiSortTree
{
public:
BiSortTree(void);
void desplayTree(void);//显示这个树
void insertTree(int key);//在树中插入一个值
deleteTree(int key);//在树中删除一个值
treeNode* searchTree(int key);//在树中查找一个值

~BiSortTree();

private:
treeNode* buildTree(treeNode* head,int number);//建立一个树
treeNode* search(treeNode* head ,int key);//查找
treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p);//查找出p的父亲节点的指针
treeNode* BiSortTree::searchMinRight(treeNode* head);//找到右子树中最小的节点

void showTree(treeNode* head);//显示
void destroyTree(treeNode* head);//删除

treeNode *Head;

};

/**************以下是建立一个二叉排序树****************/
BiSortTree::BiSortTree()
{
cout<<"建立一棵二叉排序树,请输入你要建树的所有数(以-1 作为结束标志!): "<<endl;
Head=NULL;
int number;
cin>>number;
while(number!=-1)
{
Head=buildTree(Head,number);
cin>>number;

}

}
treeNode* BiSortTree::buildTree(treeNode* head,int number)
{

treeNode *p;
p=new treeNode;
p->key=number;
p->left =p->right=NULL;

if(head==NULL)
{

return p;
}
else
{

if(p->key <head->key)
head->left=buildTree(head->left,number);
else
head->right=buildTree(head->right,number);

return head;
}

}
/*****************以下是在一棵二叉排序树插入一个数***********************************/
void BiSortTree::insertTree(int key)
{

Head=buildTree(Head,key);

}
/*****************以下是在一个二叉排序树查找一个数是否存在*************************/
treeNode* BiSortTree::searchTree(int key)
{
return search(Head,key);
}
treeNode* BiSortTree::search(treeNode* head ,int key)
{
if(head==NULL)
return NULL;
if(head->key==key)
return head;
else
{
if(key<head->key )
return search( head->left,key);

else
return search(head->right,key);

}

}

/************以下是在一个二叉排序树删除一个给定的值*********************************/
BiSortTree::deleteTree(int key)
{

treeNode *p;
p=NULL;
p=search(Head,key);
if(p==NULL)
{
cout<<"Don't find the key";

}
if(p==Head)
{
Head=NULL;

}
else
{
treeNode* parent;
parent=searchParent(Head,p);
if(p->left==NULL&&p->right==NULL)//叶子节点
{
if(parent->left==p)
{
parent->left=NULL;
}
else
{
parent->right=NULL;

}
}
else//非叶子节点
{
if(p->right==NULL)//该节点没有右孩子
{
if(parent->left==p)
{
parent->left=p->left ;
}
else
{
parent->right=p->left;

}
}

else//该点有左右孩子
{
treeNode * rightMinSon,* secondParent;//secondParent为右子树中的最小节点的父亲
rightMinSon=searchMinRight(p->right);
secondParent=searchParent(p->right ,rightMinSon);

secondParent->left=rightMinSon->right;

if(p->right==rightMinSon)//右子树中的最小节点的父亲为p
{

p->right=rightMinSon->right ;

}

p->key=rightMinSon->key ;

}
}
}
}

treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p)
{

if(head->left==p||head->right==p||head==p||head==NULL)
return head;
else
{
if(p->key<head->key)
return searchParent(head->left ,p);
else
return searchParent(head->right ,p);

}

}

treeNode* BiSortTree::searchMinRight(treeNode* head)//找到右子树中最小的节点
{

if(head->left ==NULL||head==NULL)
{
return head;

}
else
{
return searchMinRight(head->left);

}

}

/*****************以下是显示一个二叉排序树****************************************/
void BiSortTree::desplayTree(void)
{

showTree(Head);
cout<<endl;
}
void BiSortTree::showTree(treeNode* Head)
{

if(Head!=NULL)
{
showTree(Head->left ) ;

cout<<Head->key<<' ' ;

showTree(Head->right) ;

}

}

/*****************以下是删除一棵整二叉排序树************************************/
BiSortTree::~BiSortTree()
{
cout<<"已经消除了一棵树!!!!"<<endl;
destroyTree(Head);
}
void BiSortTree::destroyTree(treeNode* head )
{

if(head!=NULL)
{
destroyTree(head->left );
destroyTree(head->right );
delete head;

}

}

/*********************/
void print()
{

cout<<endl<<endl<<"以下是对二叉排序树的基本操作:"<<endl
<<"1.显示树"<<endl
<<"2.插入一个节点"<<endl
<<"3.寻找一个节点"<<endl
<<"4.删除一个节点"<<endl;
}

void main()
{
BiSortTree tree;
int number;
int choiceNumber;
char flag;
while(1)
{
print() ;

cout<<"请选择你要进行的操作(1~4)"<<endl;
cin>>choiceNumber;
switch(choiceNumber)
{
case 1:
tree.desplayTree();break;
case 2:
cout<<"请插入一个数: "<<endl;
cin>>number;
tree.insertTree(number);
tree.desplayTree();
break;

case 3:
cout<<"请插入你要找数: "<<endl;
cin>>number;
if(tree.searchTree(number)==NULL)
{
cout<<"没有发现"<<endl;
}
else
{

cout<<"发现"<<endl;

}
break;

case 4:
cout<<"请输入你要删除的数: "<<endl;
cin>>number;
tree.deleteTree(number);
tree.desplayTree();
break;

default: break;
}
cout<<"你是否要继续(Y/N)?"<<endl;
cin>>flag;
if(flag=='N'||flag=='n')
break;

}

}

---

冕宁县13145625496： 二叉树排序算法实现(数据结构课程设计) - ？
侯质上生： #include <malloc.h> #include<stdio.h> #define NUM 7 //宏定义 int i; //变量类型定义 typedef struct Node{int data ; //数据域struct Node *next; //指针域 }Node,*LNode; //用结构体构造结点及相应的指针typedef struct Tree{int data ;struct ...

冕宁县13145625496： 数据结构课程设计:二叉排序树的实现 - ？
侯质上生： /*以下是用c++ 实现的二叉排序树的源代码*/#include<iostream.h> typedef struct TreeNode { int key; struct TreeNode *left; struct TreeNode *right;}treeNode;class BiSortTree { public:BiSortTree(void); void desplayTree(void);//显示这个树 void ...

冕宁县13145625496： 数据结构课程设计(C版语言)二叉排序树算法 - ？
侯质上生： #include<stdio.h>#include<stdlib.h>#include<conio.h> typedef int DataType; //定义数据类型,以int为例 struct BSTNode //定义二叉排序树节点类型 { DataType data; struct BSTNode *lchild,*rchild; }; int insert(struct BSTNode **root,DataType data...

冕宁县13145625496： 二叉排序树的实现 用顺序和二叉链表作存储结构 数据结构课程设计？
侯质上生： Program p6_6(Input, Output); Type tree=^node; node=Record data:Integer; lchild,rchild:tree; End; Var bt:tree; n:Integer; Procedure creat_order_tree(Var btx:tree;nx:Integer); Var p,s,f:tree; flag:Boolean; Begin New(s); s^.data:=nx; s^.lchild:=Nil; s^....

冕宁县13145625496： 二叉排序树的构造与运算 (数据结构C语言版)课程设计 - ？
侯质上生： //木有wint-tc,没运行,不好意思.以前写的,楼主看能用否.#include<stdio.h>#include<stdlib.h> typedef struct BiT{ char data; struct BiT *lchild; struct BiT *rchild; }BiT; BiT* CreateBiTree(BiT *T) { //构造二叉链表表示的二叉树T char ch; scanf(＂%c...

冕宁县13145625496： 二叉排序树问题,课程设计采用顺序存储方式或二叉链表存储方式保存二叉排序树？
侯质上生： #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; typedef struct node { int data; node *left; node *right; }node; node* CreateTree(node *root,int n) { if(root==NULL) { root=(node *)malloc(sizeof(node)); root-&gt;data=n; root-&gt;left=NULL; root-&gt;right=...

冕宁县13145625496： c++ 数据结构 课程设计 - ？
侯质上生： 1、起泡排序 算法:核心思想是扫描数据清单,寻找出现乱序的两个相邻的项目.当找到这两个项目后,交换项目的位置然后继续扫描.重复上面的操作直到所有的项目都按顺序排好 bubblesort(struct rec r[],int n) { int i,j; struct rec w; unsigned ...

冕宁县13145625496： 数据结构 课程设计 二叉树操作？
侯质上生： #include <stdio.h> #include <malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; }BTNode; void CreateBTNode(BTNode *&b,char *str) { BTNode *St[MaxSize],*p=NULL...

冕宁县13145625496： 求高手帮我做份数据结构课程设计的详细答案{二叉排序树操作},我们要交作业,做的好,我把分都给你!! - ？
侯质上生： #include ＂stdio.h＂#include＂stdlib.h＂#include typedef struct BTREE {char data;struct BTREE *left;struct BTREE *right; } BTNode,*BTree; BTree node; void createBST(BTree *T, char ord); BTree createBT() { BTree *T,t; int tong,i; t=(BTree)...

冕宁县13145625496： 课程设计任务书:构建一棵二叉排序树的C程序的设计 - ？
侯质上生： 好吧,程序我帮你写好了,功能完全能按你的要求来实现. VC下通过. #include <stdio.h> #include <stdlib.h>struct node {node(int i):data(i),left(NULL),right(NULL){}int data;node *left; //左孩子结点node *right; //右孩子结点void inorder(...