二叉排序树的操作（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;
}

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