打印菜單界面，用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

感謝您使用本系統,歡迎您的再次使用！

請按任意鍵繼續. . .