數(shù)據(jù)結(jié)構(gòu)-實(shí)驗(yàn)四-二叉樹的基本操作

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 實(shí)驗(yàn)四 二叉樹的基本操作一、實(shí)驗(yàn)?zāi)康模?#160;   （1）掌握二叉樹的定義和存儲(chǔ)表示，學(xué)會(huì)建立一棵特定二叉樹的方法；   （2）掌握二叉樹的遍歷算法（先序、中序、后序遍歷算法）的思想；   （3）掌握二叉樹和葉子數(shù)、深度之間的關(guān)系及聯(lián)系。二、實(shí)驗(yàn)內(nèi)容：    構(gòu)造二叉樹，再實(shí)現(xiàn)二叉樹的先序、中序、后序遍歷，最后統(tǒng)計(jì)二叉樹的葉子數(shù)和深度。三、實(shí)驗(yàn)步驟：    (一) 需求分析     1. 二叉樹的建立首先要建立一個(gè)二叉鏈表的結(jié)構(gòu)體，包

2、含根節(jié)點(diǎn)和左右子樹。因?yàn)闃涞拿恳粋€(gè)左右子樹又是一顆二叉樹，所以用遞歸的方法來(lái)建立其左右子樹。二叉樹的遍歷是一種把二叉樹的每一個(gè)節(jié)點(diǎn)訪問(wèn)并輸出的過(guò)程，遍歷時(shí)根結(jié)點(diǎn)與左右孩子的輸出順序構(gòu)成了不同的遍歷方法，這個(gè)過(guò)程需要按照不同的遍歷的方法，先輸出根結(jié)點(diǎn)還是先輸出左右孩子，可以用選擇語(yǔ)句來(lái)實(shí)現(xiàn)。    2程序的執(zhí)行命令為：     1）構(gòu)造結(jié)點(diǎn)類型，然后創(chuàng)建二叉樹。    2）根據(jù)提示，從鍵盤輸入各個(gè)結(jié)點(diǎn)。     3）通過(guò)選擇一種方式（先序、中序或者后序）遍歷。    4）輸出結(jié)

3、果，結(jié)束。    (二)概要設(shè)計(jì)     1.二叉樹的二叉鏈表結(jié)點(diǎn)存儲(chǔ)類型定義       typedef struct Node         DataType data;        struct Node *LChild;        struct Node *RChild;       BitNode,*

4、BitTree;        2.建立如下圖所示二叉樹：            3.本程序包含六個(gè)模塊        1) 主程序模塊         2)先序遍歷模塊        3)中序遍歷模塊        4)后序遍歷模塊        5）葉子數(shù)模塊

5、60;       6）深度模塊 四、測(cè)試結(jié)果       1. 進(jìn)入演示程序后的顯示主界面：      請(qǐng)輸入二叉樹中的元素；      先序、中序、后序遍歷和葉子數(shù)、深度分別輸出結(jié)果。      2.測(cè)試結(jié)果       以擴(kuò)展先序遍歷序列輸入，其中#代表空子樹：ABC#DE#G#F#        先序遍歷序列為

6、：ABCDEGF         中序遍歷序列為：CBEGDFA         后序遍歷序列為：CGEFDBA       此二叉樹的葉子數(shù)為：3        此二叉樹的深度為：5       3.程序運(yùn)行結(jié)果截圖：五、源代碼#include#include/節(jié)點(diǎn)聲明，數(shù)據(jù)域、左孩子指針、右孩子指針typedef struct BiTNode    ch

7、ar data;    struct BiTNode *lchild,*rchild;BiTNode,*BiTree;              /先序建立二叉樹BiTree CreateBiTree()    char ch;BiTree T;    scanf("%c",&ch);    if(ch='#')T=NULL;    else     

8、  T = (BiTree)malloc(sizeof(BiTNode);        T->data = ch;        T->lchild = CreateBiTree();        T->rchild = CreateBiTree();        return T;/返回根節(jié)點(diǎn)/先序遍歷void PreOrderTraverse(BiTree T)    if(T)

9、       printf("%c",T->data);       PreOrderTraverse(T->lchild);       PreOrderTraverse(T->rchild);     /中序遍歷void InOrderTraverse(BiTree T)    if(T)       InOrderTraverse(T->

10、lchild);       printf("%c",T->data);       InOrderTraverse(T->rchild);    /后序遍歷void PostOrderTraverse(BiTree T)    if(T)       PostOrderTraverse(T->lchild);       PostOrderTraverse(

11、T->rchild);       printf("%c",T->data);    /求二叉樹的深度int Depth(BiTree T)   int dep=0,depl,depr;if(!T) dep=0;elsedepl=Depth(T->lchild);depr=Depth(T->rchild);dep=1+(depl>depr?depl:depr);return dep;/計(jì)算葉子節(jié)點(diǎn)數(shù)int leef(BiTree T)if(!T)return 0;e

12、lseif(T->lchild =NULL&&T->rchild =NULL)return 1;else return leef(T->lchild) +leef(T->rchild );/主函數(shù)void main()    BiTree T;printf("請(qǐng)按先序輸入序列（其中的“#”表示空）nn");    T = CreateBiTree();/建立二叉樹printf("n先序遍歷結(jié)果為：");PreOrderTraverse(T);/先序遍歷輸出printf("nn中序遍歷結(jié)果為：");InOrderTraverse