實(shí)驗(yàn)四 二叉樹的建立與遍歷

1、實(shí)驗(yàn)四 二叉樹的建立與遍歷【實(shí)驗(yàn)?zāi)康摹縧 掌握二叉樹的定義、性質(zhì)及存儲方式，各種遍歷算法?！緦?shí)驗(yàn)內(nèi)容】采用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序遍歷的遞歸操作。分別求所有葉子結(jié)點(diǎn)及結(jié)點(diǎn)總數(shù)的操作。 提示：設(shè)計(jì)一顆二叉樹，輸入完全二叉樹的先序序列，用#代表虛結(jié)點(diǎn)（空指針），如ABD#CE#F#，建立二叉樹，求出先序、中序和后序遍歷序列，求所有葉子及結(jié)點(diǎn)總數(shù)。【程序源代碼】#include<stdio.h>#include<stdlib.h>typedef char TElemType;typedef int Status;#define OK 1#de

2、fine ERROR 0#define OVERFLOW 0typedef struct BiTNode TElemType data;struct BiTNode *lchild, *rchild;BiTNode , *BiTree;Status CreateBiTree(BiTree &BT);void CountLeaves(BiTree BT, int &count);int NodeCount(BiTree BT);void PreOrder(BiTree BT);void InOrder(BiTree BT);void PostOrder(BiTree BT);in

3、t main()BiTree BT;int choice,cho;int logo = 1;printf("輸入二叉樹結(jié)點(diǎn)，以'#'為空指針n");CreateBiTree(BT);do printf("t 1:遍歷二叉樹n"); printf("t 2：二叉樹總結(jié)點(diǎn)數(shù)及葉子節(jié)點(diǎn)數(shù)n"); printf("t 3：退出程序n "); printf("t 輸入選項(xiàng): "); scanf("%2d",&choice); switch(choice) cas

4、e 1: printf("1:先序遍歷n"); printf("2:中序遍歷n"); printf("3:后序遍歷n"); scanf("%2d",&cho); switch(cho) case 1: PreOrder(BT); printf("n"); break;case 2: InOrder(BT); printf("n"); break; case 3: PostOrder( BT); printf("n"); break; default

5、: printf("輸入錯誤!n"); break;case 2: int count; printf("總結(jié)點(diǎn)數(shù)為:%2dn", NodeCount(BT); CountLeaves(BT, count); printf("葉子結(jié)點(diǎn)數(shù)為:%2dn", count); break;case 3 :exit(0);break;default:printf("輸入錯誤!n"); while(logo=1);return 0;Status CreateBiTree(BiTree &BT)char ch;scanf

6、("%c", &ch);if (ch = '#') BT = NULL;elseif (!(BT = (BiTree)malloc(sizeof(BiTNode)exit(OVERFLOW);BT->data = ch;CreateBiTree(BT->lchild);CreateBiTree(BT->rchild);return OK;void PreOrder(BiTree BT)if (BT != NULL)printf("%c ", BT->data);PreOrder(BT->lchild)

7、;PreOrder(BT->rchild);void InOrder(BiTree BT)if (BT != NULL)PreOrder(BT->lchild);printf("%c ", BT->data);PreOrder(BT->rchild);void PostOrder(BiTree BT)if (BT != NULL)PreOrder(BT->lchild);PreOrder(BT->rchild);printf("%c ", BT->data);void CountLeaves(BiTree BT,int &count)if (BT)if (!BT->lchild && !BT->rchild)count+;CountLeaves(BT->lchild, count);CountLeaves(BT->rchild, count);int NodeCount(BiTree BT)/統(tǒng)計(jì)總結(jié)點(diǎn)數(shù) if (BT = NULL)return 0;elsereturn (NodeCount(BT->lchild) + NodeCount(BT->rchild) + 1);【運(yùn)行結(jié)果分析