二叉排序树的操作(BST)二| Chormer's Blog||一个不平凡的80青年

二叉排序树的操作(BST)二—数据结构实验源程序C++/C

此二叉树程序包括:先序遍历,中序遍历,后序遍历,层次遍历,查找结点,求二叉树的高度,求二叉树的叶子总数,输出二叉树的叶子结点。

#include
#include
#include#define KeyType char
typedef int KeyType;
typedef struct tree
{
struct tree *left;
struct tree *right;
KeyType key;
} BSTNode, * BSTree; 

BSTree insertBST(BSTree tptr,KeyType key)
{
BSTree f,p=tptr;
while(p)
{
if(p->key==key) return NULL;
f=p;
p=(key
key)?p->left:p->right;
}
p=(BSTree )malloc(sizeof(BSTNode));
p->key=key; p->left=p->right=NULL;
if(tptr==NULL)
tptr=p;
else
if(keykey)
f->left=p;
else
f->right=p;
return tptr;
}

BSTree createBST()
{
BSTree t=NULL;
KeyType key;
scanf("%d",&key);
while(key!=-1)
{
t=insertBST(t,key);
scanf("%d",&key);
}
return t;
}

void preorder_btree(BSTree root)
{
BSTree p=root;
if(p!=NULL)
{
printf("%6d",p->key);
preorder_btree(p->left);
preorder_btree(p->right);
}
}

void inorder_btree(BSTree root)
{
BSTree p=root;
if(p!=NULL){
inorder_btree(p->left );
printf("%6d",p->key );
inorder_btree(p->right );
}
}

void postorder_btree(BSTree root)
{
BSTree p=root;
if(p!=NULL)
{
postorder_btree(p->left );
postorder_btree(p->right );
printf("%6d",p->key );
}
}

int treedepth(BSTree bt)
{
int hl,hr,max;
if(bt!=NULL)
{
hl=treedepth(bt->left);
hr=treedepth(bt->right);
max=(hl>hr)?hl:hr;
return (max+1);
}
else
return 0;
}

int count=0;

int leafcount(BSTree bt)
{
if(bt!=NULL)
{
leafcount(bt->left);
leafcount(bt->right);
if(bt->left==NULL&&bt->right==NULL)
count++;
}
return count;
}

void paintleaf(BSTree bt)
{
if(bt!=NULL)
{
if(bt->left==NULL&&bt->right==NULL)
printf("%6d",bt->key);
paintleaf(bt->left);
paintleaf(bt->right);
}
}

BSTNode *searchBST(BSTree t,KeyType key)
{
if(t==NULL||key==t->key)
return t;
if(keykey)
return searchBST(t->left,key);
else
return searchBST(t->right,key);
}

typedef BSTree ElemType ;

typedef struct QueueNode
{
ElemType data;
struct QueueNode *next;
} QueueNode;

typedef struct linkQueue
{
QueueNode * front;
QueueNode * rear;
}linkQueue;

void initQueue(linkQueue * q)
{
q->front=q->rear =NULL;     //----无头结点
}

int QueueEmpty(linkQueue * Q)
{
return (Q->front==NULL)&&(Q->rear==NULL);

}

void EnQueue(linkQueue *Q,ElemType x)
{ 

QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));
p->data=x;   p->next=NULL;
if(QueueEmpty(Q))     //----无头结点
Q->front=Q->rear=p;
else
{
Q->rear->next=p;
Q->rear=p;
}
}

ElemType DeQueue (linkQueue *Q)
{
ElemType x;
QueueNode *p;
if(QueueEmpty(Q))
{
printf("Queue underflow");
exit(1) ;
}
p=Q->front;
x=p->data;
Q->front=p->next;
if(Q->rear==p)
Q->rear=NULL;
free(p);
return x;
}

void visit(BSTree p)
{
printf("%6d",p->key);
}

void breadthFirst2(BSTree root)
{
BSTree p,tmp;
linkQueue * q;
tmp=(BSTNode *)malloc(sizeof(BSTNode));
q=(linkQueue *)malloc(sizeof(linkQueue));
tmp->key=-1;
initQueue(q);
p=root;
if(p!=NULL)
{
EnQueue(q,p);
while(!QueueEmpty(q))
{
p=DeQueue(q);
visit(p);
if(p->key!=-1)
{
if(p->left!=NULL)
EnQueue(q,p->left);
else
EnQueue(q,tmp);
if(p->right!=NULL)
EnQueue(q,p->right);
else
EnQueue(q,tmp);
}
}
}
}

void breadthFirst(BSTree root)
{
BSTree p;
linkQueue * q;
q=(linkQueue *)malloc(sizeof(linkQueue));
initQueue(q);
p=root;
if(p!=NULL)
{
EnQueue(q,p);
while(!QueueEmpty(q))
{
p=DeQueue(q);
visit(p);
if(p->left!=NULL)
EnQueue(q,p->left);
if(p->right!=NULL)
EnQueue(q,p->right);
}
}
}

int main()
{
KeyType key;
int flag;
char cmd;
BSTree root,test;
printf("\n\n--------------------------------------------------------\n");
printf("\n****欢迎测试和修正本程序!本程序用以研究二叉排序树。****\n");
printf("\n--------------------------------------------------------\n\n");
do
{
printf("\n\n 请选择你要执行的操作:\n\n");
printf(" c,C......创建一棵二叉排序树\n");
printf(" a,A......结束本程序\n\n");
flag=0;
do
{
if(flag!=0)
printf("选择操作错误!请重新选择!\n");
fflush(stdin);
scanf("%c",&cmd);
flag++;
}while(cmd!='c'&&cmd!='C'&&cmd!='a'&&cmd!='A');
if(cmd=='c'||cmd=='C')
{
printf("请输入那你所要创建的二叉树的结点的值,以-1结束):\n");
root=createBST();
do
{
flag=0;
printf("\n\n 请选择你要对这棵二叉树所做的操作:\n\n");
printf(" x,X......先序遍历这棵二叉树\n");
printf(" z,Z......中序遍历这棵二叉树\n");
printf(" h,H......后序遍历这棵二叉树\n");
printf(" b,B......层次遍历这棵二叉树\n");
printf(" s,S......查找结点\n");
printf(" d,D......求这棵二叉树的高度\n");
printf(" y,Y......求这棵二叉树的叶子总数\n");
printf(" j,J......输出这棵二叉树的叶子结点\n");
printf(" q,Q......结束对这棵二叉树的操作\n\n");
do
{
if(flag!=0)
printf("选择操作错误!请重新选择!\n");
fflush(stdin);
scanf("%c",&cmd);
flag++;
}while(cmd!='x'&&cmd!='X'&&cmd!='z'&&cmd!='Z'&&cmd!='h'&&cmd!='H'&&cmd!='b'&&cmd!='B'&&cmd!='d'&&cmd!='D'&&cmd!='y'&&cmd!='Y'&&cmd!='j'&&cmd!='J'&&cmd!='q'&&cmd!='Q'&&cmd!='s'&&cmd!='S');
switch(cmd)
{
case 'x':
case 'X':
printf("\n先序遍历开始:\n");
preorder_btree(root);
printf("\n先序遍历结束\n\n");
break;
case 'z':
case 'Z':
printf("\n中序遍历开始:\n");
inorder_btree(root);
printf("\n中序遍历结束\n\n");
break;
case 'h':
case 'H':
printf("\n后序遍历开始:\n");
postorder_btree(root);
printf("\n后序遍历结束\n\n");
break;
case 'b':
case 'B':
printf("\n层次遍历开始:\n");
printf("遍历(1):不输出为空的孩子\n");
breadthFirst(root);
printf("\n");
printf("遍历(2):输出为空的孩子\n");
breadthFirst2(root);
printf("\n层次遍历结束\n\n");
break;
case 's':
case 'S':
printf("请输入你要查找的关键字:\n");
scanf("%d",&key);
test=searchBST(root,key);
if(test==NULL)
printf("\n对不起,你所差找的结点%d不存在!\n",key);
else
printf("\n成功找到结点%d.\n",key);
break;
case 'd':
case 'D':
printf("\n这棵二叉树的高度:\n%d\n\n",treedepth(root));
break;
case 'y':
case 'Y':
count=0;
count=leafcount(root);
printf("\n这棵二叉树的叶子总数为:\n%d\n\n",count);
count=0;
break;
case 'j':
case 'J':
printf("\n这棵二叉树的叶子结点为:\n");
paintleaf(root);
printf("\n");
break;
}
}while(cmd!='q'&&cmd!='Q');
}
}while(cmd!='a'&&cmd!='A');
printf("\n\n----------------------------\n\n");
printf("****谢谢使用!欢迎指正!****\n\n");
printf("----------------------------\n\n");
printf("作者:Chormer\n\n\n\n");
return 0;
}

也许您喜欢下面的文章,不要错过哦:

郑重声明:资讯 【二叉排序树的操作(BST)二| Chormer's Blog||一个不平凡的80青年】由 发布,版权归原作者及其所在单位,其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实,请读者仅作参考,并请自行核实相关内容。若本文有侵犯到您的版权, 请你提供相关证明及申请并与我们联系(qiyeku # qq.com)或【在线投诉】,我们审核后将会尽快处理。
—— 相关资讯 ——