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

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

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

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

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

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

6、：ABCDEGF         中序遍歷序列為：CBEGDFA         后序遍歷序列為：CGEFDBA       此二叉樹的葉子數(shù)為：3        此二叉樹的深度為：5       3.程序運行結(jié)果截圖：五、源代碼#include#include/節(jié)點聲明，數(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é)點/先序遍歷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;/計算葉子節(jié)點數(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("請按先序輸入序列（其中的“#”表示空）nn");    T = CreateBiTree();/建立二叉樹printf("n先序遍歷結(jié)果為：");PreOrderTraverse(T);/先序遍歷輸出printf("nn中序遍歷結(jié)果為：");InOrderTraverse