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

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

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

实现代码：

#include

#include

#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

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

请按任意键继续. . .

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。