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

2025-02-08 13:39:41

推荐回答（4个）

回答1：

下面的程序包含了树二叉树的所有操作
在二叉树的应用中有二叉排序树。
都是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)
{
cout<data<<" ";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
return OK;
}
stadus InOrderTraverse(BitTree T)//中序
{
if(!T) return ERROR;
else if (T)
{
InOrderTraverse(T->lchild);
cout<data<<" ";
InOrderTraverse(T->rchild);
}
return OK;
}
stadus PostOrderTraverse(BitTree T)//后序
{
if(!T) return ERROR;
else if (T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<data<<" ";
}
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;
cout<data<<" ";
//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;
cout<data<<" ";
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;
cout<data<<" ";
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;
cout<data<<" ";
//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;
cout<data<<" ";
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);
cout<data<<" ";
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<<"二叉排序树的创建<以'#'结束!!!>"< cout<<"<请输入字母，没写整型!!!>"< 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<<'\t'<<'\t'<<"先序创建二叉树<以'#'表示左右孩子为空!!!>："< CreateBitTree(T);
BitTree T1(T);
select:
cout<<'\t'<<'\t'<<"----------------MAIN-MENU----------------"< cout<<'\t'<<'\t'<<"&1、先序输出 2、中序输出 3、后序输出 &"< cout<<'\t'<<'\t'<<"&4、栈实现输出 5、重新创建二叉树 0、退出&"< cout<<'\t'<<'\t'<<"------------6、二叉树的应用-------------"< char sel;
getchar();
cin>>sel;
switch (sel)//总
{
case '0':
break;
case '1':cout< PreOrderTraverse(T);
cout< goto select;
case '2':cout< InOrderTraverse(T);
cout< goto select;
case '3':cout< PostOrderTraverse(T);
cout< goto select;
case '4':
stackcout:
cout< cout<<'\t'<<" &1、先序输出 2、中序输出 3、后序输出 4、返回 &"< cout<<'\t'<<" ------------------------------------------------"< cin>>sel;
switch (sel)//栈关于树的输出
{
case '1':cout< PreOrderTraverse2(T1);//p->lchild==null,时 T 的值被修改！！！！！！！！
cout< goto stackcout;
case '2':cout< InOrderTraverse2(T);
cout< goto stackcout;
case '3':cout< PostOrderTraverse(T1);//栈实现未写完
cout< goto stackcout;
case '4':goto select;
default:cout<<"选择错误!!!"< goto stackcout;
}
case '5':
goto Create;
case '6':
{
SUB_MENU2:
cout<<'\t'<<'\t'<<"-------------------------SUB-MENU2---------------------"< cout<<'\t'<<'\t'<<"&1、二叉树的深度 2、二叉树的单分支结点数 &"< cout<<'\t'<<'\t'<<"&3、二叉树的多分支结点数 4、二叉树的叶子结点数 &"< cout<<'\t'<<'\t'<<"&5、二叉层次遍历 6、二叉排序树 7、交换左右子树 &"< cout<<'\t'<<'\t'<<"&------------------8、输出 0、返回--------------------&"< cin>>sel;
switch (sel)//二叉树的应用
{
case '0':
goto select;
case '1':
{
int deepth=0;
deepth=Depth(T);
cout< cout<<"树的深度为："< cout< }
goto SUB_MENU2;
case '2':
{
int cou_sig;
cou_sig=Single(T);
cout< cout<<"此树的单分支结点为数："< cout< }
goto SUB_MENU2;
case '3':
{
int cou_dou;
cou_dou=Double(T);
cout< cout<<"此树的双分支结点数为："< cout< }
goto SUB_MENU2;
case '4':
{
int cou_leaf;
cou_leaf=CountLeaf(T);
cout< cout<<"此树的叶子结点数为："< cout< }
goto SUB_MENU2;
case '5':
{
cout<<"二叉层次遍历的结果为："< cout< LevelOrder(T);
cout< }
goto SUB_MENU2;
case '6':
{
BitTree T3;
CreateBiTree2(T3);
SUB3:
cout<<'\t'<<"-------------------------SUB-MENU2-------------------"< cout<<'\t'<<" &1、先序输出 2、中序输出 3、后序输出 0、返回 &"< cout<<'\t'<<"-----------------------------------------------------"< cin>>sel;
switch (sel)//二叉树的层次遍历
{
case '0':
break;
case '1':cout< PreOrderTraverse(T3);
cout< goto SUB3;
case '2':cout< InOrderTraverse(T3);
cout< goto SUB3;
case '3':cout< PostOrderTraverse(T3);
cout< goto SUB3;
default:
cout<<"选择错误!!!"< goto SUB3;
}
}
goto SUB_MENU2;
case '7':
{
Change_Left_Right(T);
cout< cout<<"交换完成，请选择8输出查看!!!"< cout< }
goto SUB_MENU2;
case '8':
goto select;
default:
cout<<"选择错误!!!"< goto SUB_MENU2;
}
}
break;
default :
cout< goto select;
}
}

回答2：

#include
#include
#include

typedef int DataType; //定义数据类型,以int为例

struct BSTNode //定义二叉排序树节点类型
{
DataType data;
struct BSTNode *lchild,*rchild;
};
int insert(struct BSTNode **root,DataType data) //插入一个节点,成功返回1，否则返回0
{
struct BSTNode *newNode=(struct BSTNode*)malloc(sizeof(struct BSTNode));
newNode->data=data;
newNode->lchild=newNode->rchild=NULL;
if(*root==NULL) //为空则直接插入
{
*root=newNode;
return 1;
}
if((*root)->data==data) //找到相同元素则返回
return 0;
else if(data<(*root)->data) //递推插入左子树
return insert(&(*root)->lchild,data);
else //递推插入右子树
return insert(&(*root)->rchild,data);
}
void preorder(struct BSTNode *root) //先序遍历
{

if(root==NULL)
return;
printf("%d ",root->data);
preorder(root->lchild);
preorder(root->rchild);
}

void inorder(struct BSTNode *root) //中序遍历,结果必然是由小到大排序
{
if(root==NULL)
return;
inorder(root->lchild);
printf("%d ",root->data);
inorder(root->rchild);
}

int delNode(struct BSTNode **root,DataType key) //在二叉树root中删除关键字为key的节点
{
/*
删除*p结点的三种情况
(1)*p是叶子(即它的孩子数为0)
无须连接*p的子树，只需将*p的双亲*parent中指向*p的指针域置空即可。
(2)*p只有一个孩子*child
只需将*child和*p的双亲直接连接后，即可删去*p。
注意：
*p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或右孩子，故共有4种状态;
(3)*p有两个孩子
先令q=p，将被删结点的地址保存在q中；然后找*q的中序后继*p，并在查找过程中仍用parent记住*p的双亲位置。
*q的中序后继*p一定是*q的右子树中最左下的结点，它无左子树。
因此，可以将删去*q的操作转换为删去的*p的操作，即在释放结点*p之前将其数据复制到*q中，就相当于删去了*q。
*/
struct BSTNode *parent=NULL,*p=*root,*q,*child;
while(p){ //从根开始查找关键字为key的待删结点
if(p->data==key)
break; //已找到，跳出查找循环
parent=p; //parent指向*p的双亲
p=(keydata) ? p->lchild : p->rchild; //在关p的左或右子树中继续找
}
if(!p)
return 0;
q=p; //q记住被删结点*p
if(q->lchild && q->rchild) //*q的两个孩子均非空，故找*q的中序后继*p
for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);
//现在情况(3)已被转换为情况(2)，而情况(1)相当于是情况(2)中child=NULL的状况
child=(p->lchild)? p->lchild:p->rchild;//若是情况(2)，则child非空；否则child为空
if(!parent) //*p的双亲为空，说明*p为根，删*p后应修改根指针
*root=child;//若是情况(1)，则删去*p后，树为空；否则child变为根
else
{ //*p不是根，将*p的孩子和*p的双亲进行连接，*p从树上被摘下
if(p==parent->lchild) //*p是双亲的左孩子
parent->lchild=child;//*child作为*parent的左孩子
else parent->rchild=child;//*child作为 parent的右孩子

if(p!=q) //是情况(3)，需将*p的数据复制到*q
q->data=p->data;//若还有其它数据域亦需复制
}
free(p);//释放*p占用的空间
return 1;
}

void main()
{
int i,key;
char choice;
struct BSTNode *root=NULL; //建立一棵空树
DataType data[]={5,2,9,4,6,1,7,3}; //节点元素
for(i=0;i {
insert(&root,data[i]);
}
printf("\t**********************\n");
printf("\t1,插入一个节点\n");
printf("\t2,删除一个节点\n");
printf("\t3,输出先序遍历\n");
printf("\t4,输出中序遍历\n");
printf("\t5,退出\n");
printf("\t**********************\n");

while(1)
{
printf("请按键选择操作(1~5)\n");
fflush(stdin);
choice=getch();
switch(choice)
{
case '1':
printf("输入插入元素:");
scanf("%d",&key);
if(insert(&root,key))
printf("插入成功\n");
else
printf("已存在此元素\n");
break;
case '2':
printf("输入删除元素:");
scanf("%d",&key);
if(delNode(&root,key))
printf("删除成功\n");
else
printf("不存在此元素\n");
break;
case '3':
preorder(root);
printf("\n");
break;
case '4':
inorder(root);
printf("\n");
break;
case '5':
exit(0);
default:
printf("按键错误\n");
}
}
}

回答3：

回答4：

mark

最新问答

开个珠宝店应该去哪里进货？

QQ空间说说详细显示在主页!。现在我空间主页只能显示一条说说，怎么才能设置成能显示很多条说说的？

四川省巴中市哪有卖商用厨具的如煮面炉燃气灶蒸包机等？最好是在平昌县卖的！

请问淘宝美工一般常去哪些论坛交流呢？？

关于芭蕾舞的一些问题

当电脑自动弹出注册表的某个键值将被修改时那意味着什么？是中毒，还是？

360路由器卫士怎么设置网速限制

新买的手机卡有很多广告的短信、电话是怎么回事…可以怎么解决？

中国邮政储蓄银行社会保障卡怎样激活

阅读下列材料回答问题。材料一如下图亚洲水稻主要分布区、年降水量、人口密度分布图。材料二我国江西