二叉树基本操作演示程序C语言编写-Toy模板网

这篇具有很好参考价值的文章主要介绍了二叉树基本操作演示程序C语言编写。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

问题描述：设计一个与二叉树基本操作相关的演示程序

要求：开发工具Dev C++ c语言编写

1.创建二叉树。

2.将创建的二叉树，以树状形式输出。

3.分别以先序、中序、后序三种遍历方式访问二叉树。

4.输出二叉树中的叶子结点以及叶子结点的个数。

5.输出二叉树的高度。

代码如下

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
#define MAXLEN 100
#define NLAYER 4
typedef char DataType;

typedef struct Node {
   //定义二叉树结点
   DataType data;
   struct Node* leftChild;
   struct Node* rightChild;
}BiTreeNode, * BiTree;

//输入：ABD#G##EH###CF##IK### （#表示孩子为空）
BiTree CreatePreTree(); //建立二叉树
int Count1(BiTree bt);//二叉树的叶子节点的数量
int Treehigh(BiTree bt);//二叉树的高度

void TranslevelPrint(BiTree bt);//树形打印二叉树
void PreOrder(BiTreeNode* root, void visit(DataType item));//前序遍历
void InOrder(BiTreeNode* root, void visit(DataType item));//中序遍历
void PostOrder(BiTreeNode* root, void visit(DataType item));//后序遍历
void visit(DataType item);//访问函数
void Destory(BiTree bt); //释放空间

int main()
{
   BiTree T;
   char sel = ' ';
   while (sel != '0')
   {
       printf("------二叉树演示系统-------\n");
       printf("------------------------------------------\n");
       printf(" 1.创建二叉树\n");
       printf(" 2.树的形状为\n");
       printf(" 3.先序排列操作\n");
       printf(" 4.中序排列操作\n");
       printf(" 5.后序排列操作\n");
       printf(" 6.输出二叉树的叶子结点以及数量\n");
       printf(" 7.输出二叉树的高度\n");
       printf(" 0.退出系统\n");
       printf("请输入选项[0-9]:");
       sel = _getch();
       switch (sel)
       {

       case '1':

           printf("创建二叉树，按照以下规则创建二叉树按照前序遍历来创建二叉树 #表示孩子为空.\n");
           T = CreatePreTree();
           system("pause");
           break;
       case '2':printf("树的形状为：\n"); TranslevelPrint(T);getch();
       break;
       case '3':
           system("cls");
           printf("先序排列操作.\n");
           printf("前序遍历:");
           PreOrder(T, visit);//前序遍历
           system("pause");
           break;
       case '4':
           system("cls");
           printf("中序排列操作.\n");
           printf("\n中序遍历:");
           InOrder(T, visit);//中序遍历
           system("pause");
           break;
       case '5':
           system("cls");
           printf("后序排列操作.\n");
           printf("\n后序遍历:");
           PostOrder(T, visit);//后序遍历
           system("pause");
           break;
       case '6':
           system("cls");
           printf("输出二叉树的叶子节点以及数量.\n");
           printf("叶子节点为: \n");
           printf(" 叶子节点：%d个 \n", Count1(T));
           system("pause");
           break;
       case '7':
           system("cls");
           printf("输出二叉树的高度.\n");
           printf("二叉树的高度为：%d\n", Treehigh(T));
           system("pause");
           break;

       case '0':
           system("cls");
           printf("\n谢谢使用，再见！\n");
           break;
       default:
           printf("您输入的选项不合法，请重新选择！\n");
       }
   }
   return 0;
}
void visit(DataType item)
{
   printf("%c ", item);
}

BiTree CreatePreTree()//建立二叉树
{
   char c;
   scanf("%c", &c);
   if (c == '#') //空格
       return NULL;
   else
   {
       BiTree T = (BiTree)malloc(sizeof(BiTreeNode));
       T->data = c;
       T->leftChild = CreatePreTree();
       T->rightChild = CreatePreTree();
       return T;
   }
}
void TranslevelPrint(BiTree bt)
{
//本算法实现二叉树的按层打印
struct node
{
/* data */
BiTree vec[MAXLEN];//存放树结点
int layer[MAXLEN];//结点所在的层
int locate[MAXLEN];//打印结点的位置
int front,rear;
}q; //定义队列q
int i,j=1,k=0,nlocate;
q.front=0; q.rear=0;//初始化队列q队头，队尾
printf(" ");
q.vec[q.rear]=bt;//将二叉树根节点入队列
q.layer[q.rear]=1;
q.locate[q.rear]=20;
q.rear=q.rear+1;
while(q.front<q.rear)
{
bt=q.vec[q.front];
i=q.layer[q.front];
nlocate=q.locate[q.front];
if (j<i) //进层打印时换行
{
printf("\n\n");
j=j+1; k=0;
while(k<nlocate)
{
printf(" ");
k++;
}
}
while(k<(nlocate-1))
{
printf(" ");
k++;
}
printf("%c",bt->data );
q.front=q.front+1;
if(bt->leftChild !=NULL)//存在左子树，将左子树根节点入队列
{ q.vec[q.rear]=bt->leftChild;
q.layer[q.rear]=i+1;
q.locate[q.rear]=(int)(nlocate-pow(2,NLAYER-i-1));
q.rear=q.rear+1;
}
if(bt->rightChild !=NULL)
{
q.vec[q.rear]=bt->rightChild;
q.layer[q.rear]=i+1;
q.locate[q.rear]=(int)(nlocate+pow(2,NLAYER-i-1));
q.rear=q.rear+1;
}
}
}
void PreOrder(BiTreeNode* root, void visit(DataType item)) {
   //前序遍历二叉树root，访问操作为visit
   if (root != NULL)
   {
       visit(root->data);
       PreOrder(root->leftChild, visit);
       PreOrder(root->rightChild, visit);
   }
}
void InOrder(BiTreeNode* root, void visit(DataType item)) {
   //中序遍历二叉树root，访问操作为visit
   if (root != NULL)
   {
       InOrder(root->leftChild, visit);
       visit(root->data);
       InOrder(root->rightChild, visit);
   }
}

void PostOrder(BiTreeNode* root, void visit(DataType item)) {
   //后序遍历二叉树root，访问操作为visit
   if (root != NULL)
   {
       PostOrder(root->leftChild, visit);
       PostOrder(root->rightChild, visit);
       visit(root->data);
   }
}

int Count1(BiTree bt) //求叶子节点的数量并输出叶子节点
{
   if (bt == NULL) return 0;
   else if (bt->leftChild == NULL && bt->rightChild == NULL)
   {

       printf("%c ",bt->data);
       return 1;
   }
   else
       return (Count1(bt->leftChild) + Count1(bt->rightChild));
}

int Treehigh(BiTree bt) //求二叉树的高度
{
   int lefthigh, righthigh, high;
   if (bt == NULL) high = 0;//空树
   else
   {
       lefthigh = Treehigh(bt->leftChild);
       righthigh = Treehigh(bt->rightChild);
       int i = lefthigh > righthigh ? lefthigh : righthigh;//找到子树的高度
       high = i + 1;//子树高度+1=树的高度
   }
   return high;
}
二叉树基本操作演示程序C语言编写