问题描述：设计一个与二叉树基本操作相关的演示程序
要求：开发工具Dev C++ c语言编写
1.创建二叉树。
2.将创建的二叉树，以树状形式输出。
3.分别以先序、中序、后序三种遍历方式访问二叉树。
4.输出二叉树中的叶子结点以及叶子结点的个数。
5.输出二叉树的高度。
代码如下
#include
#include
#include
#include
#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("二叉树的高度为：%dn", 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
{
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
bt=q.vec[q.front];
i=q.layer[q.front];
nlocate=q.locate[q.front];
if (j
printf("nn");
j=j+1; k=0;
while(k
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;
}
当我们输入其他数字的时候就会出现
结束
