打印菜单界面，用c语言实现二叉树的基本操作

打印菜单界面，用c语言实现二叉树的基本操作：

其代码原理和用c++实现一样，请看本人上篇博客：二叉树的先序、中序、后序遍历等基本操作c++实现，链接：http://yaoyaolx.blog.51cto.com/10732111/1783527

实现代码：

#include <stdio.h>

#include <stdlib.h>

#define MAXSIZE 50

//定义二叉树的二叉链表结构

typedef struct Node

{

char data;

struct Node *LChild;

struct Node *RChild;

}BiTNode, *BiTree;

typedef struct

{

BiTree element[MAXSIZE];

int front;//队头

int rear;//队尾

}SeqQueue;

//初始化队列

void InitQueue(SeqQueue *Q)

{

Q->front = Q->rear = 0;

}

//入队

int EnterQueue(SeqQueue *Q, BiTree bt)

{

if ((Q->rear + 1) % MAXSIZE == Q->front)

{

return 0;

}

else

{

Q->element[Q->rear] = bt;

Q->rear = (Q->rear + 1) % MAXSIZE;

return 1;

}

}

//出队

int DeleteQueue(SeqQueue *Q, BiTree *bt)

{

if (Q->front == Q->rear)

{

return 0;

}

else

{

*bt = Q->element[Q->front];

Q->front = (Q->front + 1) % MAXSIZE;

return 1;

}

}

//判断队列是否为空

int IsEmpty(SeqQueue *Q)

{

if (Q->front == Q->rear)

{

return 1;

}

else

{

return 0;

}

}

//用拓展先序遍历序列创建二叉链表

void CreateBiTree(BiTree *bt)

{

char ch;

ch = getchar();

if (ch == '\n')

{

return;

}

if (ch == '#')

{

*bt = NULL;

}

else

{

*bt = (BiTree)malloc(sizeof(BiTNode));

(*bt)->data = ch;

CreateBiTree(&((*bt)->LChild));

CreateBiTree(&((*bt)->RChild));

}

}

//先序遍历输出二叉树的结点,根结点->左子树->右子树,root为指向二叉树（或某一子树）根结点的指针

void PreOrder(BiTree root)

{

if (root != NULL)

{

printf("%c  ", root->data);//访问根结点

PreOrder(root->LChild);//遍历左子树

PreOrder(root->RChild);//遍历右子树

}

}

//中序遍历输出二叉树的结点,左子树->根结点->右子树

void InOrder(BiTree root)

{

if (root != NULL)

{

InOrder(root->LChild);

printf("%c  ", root->data);

InOrder(root->RChild);

}

}

//中序非递归遍历输出二叉树的结点

void InOrderNo(BiTree root)

{

int top = 0;

BiTree p = root;

BiTree s[MAXSIZE] = { NULL };

do {

while (p != NULL)

{

if (top > MAXSIZE)

{

return;

}

else

{

top++;

s[top] = p;

p = p->LChild;

}

}

if (top != 0)

{

p = s[top];

top--;

printf("%c  ", p->data);

p = p->RChild;

}

} while (p != NULL || top != 0);

}

//后序遍历输出二叉树的结点,左子树->右子树->根结点

void PostOrder(BiTree root)

{

if (root != NULL)

{

PostOrder(root->LChild);

PostOrder(root->RChild);

printf("%c  ", root->data);

}

}

//桉树状打印二叉树,逆中序

void PrintTree(BiTree root, int nLayer)

{

if (root == NULL)

{

return;

}

else

{

PrintTree(root->RChild, nLayer + 1);

for (int i = 0; i < nLayer; i++)

{

printf("   ");

}

printf("%c\n", root->data);

PrintTree(root->LChild, nLayer + 1);

}

}

//层序遍历二叉树

void LayerOrder(BiTree root)

{

SeqQueue Q;

BiTree p = NULL;

InitQueue(&Q);

if (root == NULL)

{

return;

}

else

{

EnterQueue(&Q, root);

while (!IsEmpty(&Q))

{

DeleteQueue(&Q, &p);

printf("%c  ", p->data);

if (p->LChild != NULL)

{

EnterQueue(&Q, p->LChild);

}

if (p->RChild != NULL)

{

EnterQueue(&Q, p->RChild);

}

}

return 1;

}

}

//求二叉树的高度

int PostTreeDepth(BiTree root)

{

int hl = 0;

int hr = 0;

int max = 0;

if (root != NULL)

{

hl = PostTreeDepth(root->LChild);

hr = PostTreeDepth(root->RChild);

max = (hl > hr) ? hl : hr;

return max + 1;

}

else

{

return 0;

}

}

//二叉树的结点个数

int RootCount(BiTree root)

{

int count = 1;

if (root != NULL)

{

count += (RootCount(root->LChild) + RootCount(root->RChild));

}

else

{

count = 0;

}

return count;

}

//二叉树的叶子结点个数

int LeafCount(BiTree root)

{

int leafCount = 0;

if (root == NULL)

{

leafCount = 0;

}

else if ((root->LChild == NULL) && (root->RChild == NULL))

{

leafCount = 1;

}

else

{

leafCount = (LeafCount(root->LChild) + LeafCount(root->RChild));

}

return leafCount;

}

//交换二叉树每个结点的左子树和右子树

void ChangeLeftRight(BiTree *bt)

{

if ((*bt)->LChild == NULL && (*bt)->RChild == NULL)

{

return;

}

else

{

BiTree tmp = (*bt)->LChild;

(*bt)->LChild = (*bt)->RChild;

(*bt)->RChild = tmp;

if ((*bt)->LChild != NULL)

{

ChangeLeftRight(&((*bt)->LChild));

}

if ((*bt)->RChild != NULL)

{

ChangeLeftRight(&((*bt)->RChild));

}

}

}

void maue()

{

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("    ☆☆☆★★★★★         8、二叉树的高度         ★★★★★☆☆☆ \n");

printf("    ☆☆☆★★★★★       9、二叉树的结点个数       ★★★★★☆☆☆ \n");

printf("    ☆☆☆★★★★★      10、二叉树的叶子结点个数       ★★★★★☆☆☆ \n");

printf("    ☆☆☆★★★★★  11、交换二叉树的左子树和右子树 ★★★★★☆☆☆ \n");

printf("    ☆☆☆★★★★★           0、退出系统           ★★★★★☆☆☆ \n");

printf("\n");

}

int main()

{

BiTree bt = NULL;

int number = 0;

do {

maue();

printf("请选择您要进行的本系统的功能: > ");

scanf_s("%d", &number);

switch (number)

{

case 1:

printf("请输入二叉树的扩展先序遍历序列:> ");

getchar();

CreateBiTree(&bt);

printf("\n");

break;

case 2:

printf("此二叉树的先序遍历序列为:> ");

PreOrder(bt);

printf("\n");

break;

case 3:

printf("此二叉树的中序遍历序列为:> ");

InOrder(bt);

printf("\n");

break;

case 4:

printf("此二叉树的非递归中序遍历序列为:> ");

InOrderNo(bt);

printf("\n");

break;

case 5:

printf("此二叉树的后序遍历序列为:> ");

PostOrder(bt);

printf("\n");

break;

case 6:

printf("树状打印此二叉树为:>\n ");

PrintTree(bt, 2);

printf("\n");

break;

case 7:

printf("层次遍历印此二叉树为:> ");

LayerOrder(bt);

printf("\n");

break;

case 8:

printf("此二叉树的高度为:> ");

int heigh = PostTreeDepth(bt);

printf("heigh = %d\n", heigh);

break;

case 9:

printf("此二叉树的结点个数为:> ");

int rootCount = RootCount(bt);

printf("rootCount = %d\n", rootCount);

break;

case 10:

printf("此二叉树的叶子结点个数为:> ");

int leafCount = LeafCount(bt);

printf("leafCount = %d\n", leafCount);

break;

case 11:

printf("交换二叉树每个结点的左子树和右子树后，二叉树变为（先序遍历）:>\n ");

ChangeLeftRight(&bt);

PreOrder(bt);

printf("\n");

break;

case 0:

printf("感谢您使用本系统,欢迎您的再次使用！\n");

break;

default:

printf("请输入正确的功能号：\n");

break;

}

} while (number);

system("pause");

return 0;

}

运行结果：

   ☆☆☆☆★★★★★        欢迎使用本系统         ★★★★★☆☆☆☆

    ☆☆☆★★★★★     1、建立二叉树的二叉链表     ★★★★★☆☆☆

    ☆☆☆★★★★★     2、二叉树的先序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★     3、二叉树的中序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★  4、二叉树的非递归中序递归遍历  ★★★★★☆☆☆

    ☆☆☆★★★★★     5、二叉树的后序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★       6、树状打印此二叉树       ★★★★★☆☆☆

    ☆☆☆★★★★★       7、二叉树的层序遍历       ★★★★★☆☆☆

    ☆☆☆★★★★★         8、二叉树的高度         ★★★★★☆☆☆

    ☆☆☆★★★★★       9、二叉树的结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★      10、二叉树的叶子结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★  11、交换二叉树的左子树和右子树 ★★★★★☆☆☆

    ☆☆☆★★★★★           0、退出系统           ★★★★★☆☆☆

请选择您要进行的本系统的功能: > 1

请输入二叉树的扩展先序遍历序列:> 123##4##56###

   ☆☆☆☆★★★★★        欢迎使用本系统         ★★★★★☆☆☆☆

    ☆☆☆★★★★★     1、建立二叉树的二叉链表     ★★★★★☆☆☆

    ☆☆☆★★★★★     2、二叉树的先序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★     3、二叉树的中序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★  4、二叉树的非递归中序递归遍历  ★★★★★☆☆☆

    ☆☆☆★★★★★     5、二叉树的后序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★       6、树状打印此二叉树       ★★★★★☆☆☆

    ☆☆☆★★★★★       7、二叉树的层序遍历       ★★★★★☆☆☆

    ☆☆☆★★★★★         8、二叉树的高度         ★★★★★☆☆☆

    ☆☆☆★★★★★       9、二叉树的结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★      10、二叉树的叶子结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★  11、交换二叉树的左子树和右子树 ★★★★★☆☆☆

    ☆☆☆★★★★★           0、退出系统           ★★★★★☆☆☆

请选择您要进行的本系统的功能: > 6

树状打印此二叉树为:>

          5

            6

      1

            4

         2

            3

   ☆☆☆☆★★★★★        欢迎使用本系统         ★★★★★☆☆☆☆

    ☆☆☆★★★★★     1、建立二叉树的二叉链表     ★★★★★☆☆☆

    ☆☆☆★★★★★     2、二叉树的先序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★     3、二叉树的中序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★  4、二叉树的非递归中序递归遍历  ★★★★★☆☆☆

    ☆☆☆★★★★★     5、二叉树的后序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★       6、树状打印此二叉树       ★★★★★☆☆☆

    ☆☆☆★★★★★       7、二叉树的层序遍历       ★★★★★☆☆☆

    ☆☆☆★★★★★         8、二叉树的高度         ★★★★★☆☆☆

    ☆☆☆★★★★★       9、二叉树的结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★      10、二叉树的叶子结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★  11、交换二叉树的左子树和右子树 ★★★★★☆☆☆

    ☆☆☆★★★★★           0、退出系统           ★★★★★☆☆☆

请选择您要进行的本系统的功能: > 2

此二叉树的先序遍历序列为:> 1  2  3  4  5  6

   ☆☆☆☆★★★★★        欢迎使用本系统         ★★★★★☆☆☆☆

    ☆☆☆★★★★★     1、建立二叉树的二叉链表     ★★★★★☆☆☆

    ☆☆☆★★★★★     2、二叉树的先序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★     3、二叉树的中序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★  4、二叉树的非递归中序递归遍历  ★★★★★☆☆☆

    ☆☆☆★★★★★     5、二叉树的后序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★       6、树状打印此二叉树       ★★★★★☆☆☆

    ☆☆☆★★★★★       7、二叉树的层序遍历       ★★★★★☆☆☆

    ☆☆☆★★★★★         8、二叉树的高度         ★★★★★☆☆☆

    ☆☆☆★★★★★       9、二叉树的结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★      10、二叉树的叶子结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★  11、交换二叉树的左子树和右子树 ★★★★★☆☆☆

    ☆☆☆★★★★★           0、退出系统           ★★★★★☆☆☆

请选择您要进行的本系统的功能: > 3

此二叉树的中序遍历序列为:> 3  2  4  1  6  5

   ☆☆☆☆★★★★★        欢迎使用本系统         ★★★★★☆☆☆☆

    ☆☆☆★★★★★     1、建立二叉树的二叉链表     ★★★★★☆☆☆

    ☆☆☆★★★★★     2、二叉树的先序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★     3、二叉树的中序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★  4、二叉树的非递归中序递归遍历  ★★★★★☆☆☆

    ☆☆☆★★★★★     5、二叉树的后序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★       6、树状打印此二叉树       ★★★★★☆☆☆

    ☆☆☆★★★★★       7、二叉树的层序遍历       ★★★★★☆☆☆

    ☆☆☆★★★★★         8、二叉树的高度         ★★★★★☆☆☆

    ☆☆☆★★★★★       9、二叉树的结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★      10、二叉树的叶子结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★  11、交换二叉树的左子树和右子树 ★★★★★☆☆☆

    ☆☆☆★★★★★           0、退出系统           ★★★★★☆☆☆

请选择您要进行的本系统的功能: > 11

交换二叉树每个结点的左子树和右子树后，二叉树变为（先序遍历）:>

 1  5  6  2  4  3

   ☆☆☆☆★★★★★        欢迎使用本系统         ★★★★★☆☆☆☆

    ☆☆☆★★★★★     1、建立二叉树的二叉链表     ★★★★★☆☆☆

    ☆☆☆★★★★★     2、二叉树的先序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★     3、二叉树的中序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★  4、二叉树的非递归中序递归遍历  ★★★★★☆☆☆

    ☆☆☆★★★★★     5、二叉树的后序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★       6、树状打印此二叉树       ★★★★★☆☆☆

    ☆☆☆★★★★★       7、二叉树的层序遍历       ★★★★★☆☆☆

    ☆☆☆★★★★★         8、二叉树的高度         ★★★★★☆☆☆

    ☆☆☆★★★★★       9、二叉树的结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★      10、二叉树的叶子结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★  11、交换二叉树的左子树和右子树 ★★★★★☆☆☆

    ☆☆☆★★★★★           0、退出系统           ★★★★★☆☆☆

请选择您要进行的本系统的功能: > 9

此二叉树的结点个数为:> rootCount = 6

   ☆☆☆☆★★★★★        欢迎使用本系统         ★★★★★☆☆☆☆

    ☆☆☆★★★★★     1、建立二叉树的二叉链表     ★★★★★☆☆☆

    ☆☆☆★★★★★     2、二叉树的先序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★     3、二叉树的中序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★  4、二叉树的非递归中序递归遍历  ★★★★★☆☆☆

    ☆☆☆★★★★★     5、二叉树的后序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★       6、树状打印此二叉树       ★★★★★☆☆☆

    ☆☆☆★★★★★       7、二叉树的层序遍历       ★★★★★☆☆☆

    ☆☆☆★★★★★         8、二叉树的高度         ★★★★★☆☆☆

    ☆☆☆★★★★★       9、二叉树的结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★      10、二叉树的叶子结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★  11、交换二叉树的左子树和右子树 ★★★★★☆☆☆

    ☆☆☆★★★★★           0、退出系统           ★★★★★☆☆☆

请选择您要进行的本系统的功能: > 8

此二叉树的高度为:> heigh = 3

   ☆☆☆☆★★★★★        欢迎使用本系统         ★★★★★☆☆☆☆

    ☆☆☆★★★★★     1、建立二叉树的二叉链表     ★★★★★☆☆☆

    ☆☆☆★★★★★     2、二叉树的先序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★     3、二叉树的中序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★  4、二叉树的非递归中序递归遍历  ★★★★★☆☆☆

    ☆☆☆★★★★★     5、二叉树的后序递归遍历     ★★★★★☆☆☆

    ☆☆☆★★★★★       6、树状打印此二叉树       ★★★★★☆☆☆

    ☆☆☆★★★★★       7、二叉树的层序遍历       ★★★★★☆☆☆

    ☆☆☆★★★★★         8、二叉树的高度         ★★★★★☆☆☆

    ☆☆☆★★★★★       9、二叉树的结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★      10、二叉树的叶子结点个数       ★★★★★☆☆☆

    ☆☆☆★★★★★  11、交换二叉树的左子树和右子树 ★★★★★☆☆☆

    ☆☆☆★★★★★           0、退出系统           ★★★★★☆☆☆

请选择您要进行的本系统的功能: > 0

感谢您使用本系统,欢迎您的再次使用！

请按任意键继续. . .