📄 二叉排序树.cpp
字号:
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
#define NULL 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 1024
#define STACKINCREMENT 10
#define CLS system("cls")
#define EXIT exit(0);
typedef struct BiTNode{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
struct node{
struct BiTNode * a[100];
int rear,front;
}Q;
typedef struct {
BiTree * base;
BiTree * top;
int stacksize;
}SqStack;
void InitStack(SqStack &S){
S.base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}
BiTree GetTop(SqStack S,BiTree &e){
if(S.top==S.base) return ERROR;
e=*(S.top-1);
return e;
}
BiTree push(SqStack &S,BiTree e){
if(S.top-S.base>=S.stacksize){
S.base=(BiTree *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTNode));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return e;
}
BiTree pop(SqStack &S,BiTree &e){
if(S.top==S.base) return ERROR;
e=*--S.top;
return e;
}
void CreateBitree(BiTree *T,int n){ /*插入二叉排序树结点*/
if(!(*T)){
(*T)=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->data = n;
(*T)->lchild = NULL;
(*T)->rchild = NULL;
return;
}
else{
if((*T)->data==n)
return;
if(n>(*T)->data)
CreateBitree(&(*T)->rchild,n);
else
CreateBitree(&(*T)->lchild,n);
}
}
int PrintElement(int e){
printf("%d ",e);
return OK;
}
int PreOrder(BiTree T,int(*PrintElement)(int e)){ /*先序递归遍历*/
if(T){
if(PrintElement(T->data))
if(PreOrder(T->lchild,PrintElement))
if(PreOrder(T->rchild,PrintElement)) return OK;
return ERROR;
}
else return OK;
}
int MidOrder(BiTree T,int(*PrintElement)(int e)){ /*中序递归遍历*/
if(T){
if(MidOrder(T->lchild,PrintElement))
if(PrintElement(T->data))
if(MidOrder(T->rchild,PrintElement)) return OK;
return ERROR;
}
else return OK;
}
void InOrder(BiTree T,int(*PrintElement)(int e)){ /*中序非递归遍历*/
SqStack S;
BiTree p;
InitStack(S);push(S,T);
while(S.base!=S.top){
while(GetTop(S,p)&&p) push(S,p->lchild);
p=pop(S,p);
if(S.base!=S.top){
pop(S,p);
PrintElement(p->data);
push(S,p->rchild);
}
}
}
int PostOrder(BiTree T,int(*PrintElement)(int e)){ /*后序递归遍历*/
if(T){
if(PostOrder(T->lchild,PrintElement))
if(PostOrder(T->rchild,PrintElement))
if(PrintElement(T->data)) return OK;
return ERROR;
}
else return OK;
}
void LevelOrder(BiTree T,int(*PrintElement)(int e)){ /*层次遍历*/
Q.rear=Q.front=0;
if(T)
PrintElement(T->data);
Q.a[Q.rear]=T;
Q.rear=Q.rear+1;
while(Q.rear>Q.front){
T=Q.a[Q.front];
Q.front++;
if(T->lchild){
PrintElement(T->lchild->data);
Q.a[Q.rear]=T->lchild;
Q.rear++;
}
if(T->rchild){
PrintElement(T->rchild->data);
Q.a[Q.rear]=T->rchild;
Q.rear++;
}
}
}
void SearchBitree(BiTree T,int key,BiTree f,BiTree &p){ /*查找关键字*/
if(!T){
p=f;
printf("没有这个数据\n");
}
else if(key==T->data){
p=T;
printf("这个数据在树中\n");
}
else if(key<T->data)
SearchBitree(T->lchild,key,T,p);
else
SearchBitree(T->rchild,key,T,p);
}
void ExchangeBitree(BiTree &T){ /*交换左右子树*/
BiTree U;
if (T) {
ExchangeBitree(T->lchild);
ExchangeBitree(T->rchild);
U=T->lchild;
T->lchild=T->rchild;
T->rchild=U;
}
}
int DepthBitree(BiTree T){ /*二叉排序树的深度*/
int d,dl,dr;
if(T!=NULL){
dl=DepthBitree(T->lchild);
dr=DepthBitree(T->rchild);
if(dl>dr)
d=dl;
else
d=dr;
return (d+1);
}
else
return (0);
}
int CLeafBitree(BiTree T){ /*二叉排序树的叶子结点数*/
int c,n;
if(!T) return (0);
else if(T->lchild==NULL&&T->rchild==NULL)
return (1);
else {
c=CLeafBitree(T->lchild);
n=CLeafBitree(T->rchild);
return (c+n);
}
}
void main(){
BiTree G=NULL;
loop:printf("********************************************************************************");
printf("* *");
printf("* 二叉排序树 *");
printf("* *");
printf("* 1. 建立一棵二叉排序树 *");
printf("* 2. 插入一个结点 *");
printf("* 3. 先序递归遍历 *");
printf("* 4. 中序递归遍历 *");
printf("* 5. 中序非递归遍历 *");
printf("* 6. 后序递归遍历 *");
printf("* 7. 层次遍历 *");
printf("* 8. 查找数据 *");
printf("* 9. 交换左右子树 *");
printf("* 10. 二叉排序树的深度 *");
printf("* 11. 二叉排序树的叶子结点数 *");
printf("* 0. 退出 *");
printf("* *");
printf("* *");
printf("* *");
printf("********************************************************************************");
printf("\n");
printf("请输入功能号: ");
int x;
input:scanf("%d",&x);
switch(x){
case 0: EXIT;break;
case 1:{
CLS;
int j,k;
printf("请输入数据，若全部输入结束，请输入00:\n");
for(j=1; ;j++){
scanf("%d",&k);
if(k==00){
printf("输入结束\n");
CLS;
goto loop;
}
else
CreateBitree(&G,k);
}
}break;
case 2: CLS;printf("\n");int z;printf("插入一个结点: ");scanf("%d",&z);CreateBitree(&G,z);printf("\n");printf("\n");goto loop;break;
case 3: CLS;printf("\n");printf("先序递归遍历: ");PreOrder(G,PrintElement);printf("\n");printf("\n");goto loop;break;
case 4: CLS;printf("\n");printf("中序递归遍历: ");MidOrder(G,PrintElement);printf("\n");printf("\n");goto loop;break;
case 5: CLS;printf("\n");printf("中序非递归遍历: ");InOrder(G,PrintElement);printf("\n");printf("\n");goto loop;break;
case 6: CLS;printf("\n");printf("后序递归遍历: ");PostOrder(G,PrintElement);printf("\n");printf("\n");goto loop;break;
case 7: CLS;printf("\n");printf("层次遍历: ");LevelOrder(G,PrintElement);printf("\n");printf("\n");goto loop;break;
case 8: CLS;printf("\n");int f;BiTree M,A;printf("输入要查找的数据: ");scanf("%d",&f);printf("\n");SearchBitree(G,f,M,A);printf("\n");printf("\n");goto loop;break;
case 9: CLS;printf("\n");printf("交换成功!\n");ExchangeBitree(G);printf("\n");printf("\n");goto loop;break;
case 10: CLS;printf("\n");printf("二叉排序树的深度是: %d",DepthBitree(G));printf("\n");printf("\n");goto loop;break;
case 11: CLS;printf("\n");printf("二叉排序树的叶子结点数是: %d",CLeafBitree(G));printf("\n");printf("\n");goto loop;break;
default : printf("输入错误，请重新输入: ");goto input;
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -