數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告二叉樹(shù)(共4頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報(bào)告專(zhuān)業(yè)班級(jí)姓名學(xué)號(hào)實(shí)驗(yàn)項(xiàng)目 實(shí)驗(yàn)三 二叉樹(shù)。實(shí)驗(yàn)?zāi)康?、掌握用遞歸方法實(shí)現(xiàn)二叉樹(shù)的遍歷。2、加深對(duì)二叉樹(shù)的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。題目：(1)編寫(xiě)二叉樹(shù)的遍歷操作函數(shù)。先序遍歷，遞歸方法 re_preOrder(TREE *tree)中序遍歷，遞歸方法 re_midOrder(TREE *tree)后序遍歷，遞歸方法 re_postOrder(TREE *tree)(2)調(diào)用上述函數(shù)實(shí)現(xiàn)先序、中序和后序遍歷二叉樹(shù)操作。算法設(shè)計(jì)分析（一）數(shù)據(jù)結(jié)構(gòu)的定義要求用c語(yǔ)言編寫(xiě)一個(gè)演示程序，首先建立一個(gè)二叉樹(shù)，讓用戶(hù)輸入一個(gè)二叉樹(shù)，實(shí)現(xiàn)該二叉樹(shù)的

2、便利操作。二叉樹(shù)型存儲(chǔ)結(jié)構(gòu)定義為：typedef struct TNode char data;/字符型數(shù)據(jù) struct TNode *lchild,*rchild;/左右孩子指針 TNode,* Tree; （二）總體設(shè)計(jì)程序由主函數(shù)、二叉樹(shù)建立函數(shù)、先序遍歷函數(shù)、中序遍歷函數(shù)、后序遍歷函數(shù)五個(gè)函數(shù)組成。其功能描述如下：（1）主函數(shù)：統(tǒng)籌調(diào)用各個(gè)函數(shù)以實(shí)現(xiàn)相應(yīng)功能。 int main()（2）二叉樹(shù)建立函數(shù)：根據(jù)用戶(hù)意愿運(yùn)用先序遍歷建立一個(gè)二叉樹(shù)。int CreateBiTree(Tree &T)（3）先序遍歷函數(shù)：將所建立的二叉樹(shù)先序遍歷輸出。 void PreOrder(Tre

3、e T)（4）中序遍歷函數(shù)：將所建立的二叉樹(shù)中序遍歷輸出。 void InOrder(Tree T)（5）后序遍歷函數(shù)：將所建立的二叉樹(shù)后序遍歷輸出。void PostOrder(Tree T)（三）各函數(shù)的詳細(xì)設(shè)計(jì)：（1）建立一個(gè)二叉樹(shù)，按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值（一個(gè)字符），#表示空樹(shù)。對(duì)T動(dòng)態(tài)分配存儲(chǔ)空間，生成根節(jié)點(diǎn)，構(gòu)造左、右子樹(shù)（2）編寫(xiě)先序遍歷函數(shù)，依次訪問(wèn)根節(jié)點(diǎn)、左子結(jié)點(diǎn)、右子節(jié)點(diǎn)（3）編寫(xiě)中序遍歷函數(shù)，依次訪問(wèn)左子結(jié)點(diǎn)、根節(jié)點(diǎn)、右子節(jié)點(diǎn)（4）編寫(xiě)后序遍歷函數(shù)，依次訪問(wèn)左子結(jié)點(diǎn)、右子節(jié)點(diǎn)、根節(jié)點(diǎn)（5）編寫(xiě)主函數(shù)，調(diào)用各個(gè)函數(shù)，以實(shí)現(xiàn)二叉樹(shù)遍歷的基本操作。實(shí)驗(yàn)測(cè)試結(jié)果及結(jié)果分析

4、（一）測(cè)試結(jié)果輸入HAD#C#B#GF#E#（二）結(jié)果分析 調(diào)試程序時(shí)，出現(xiàn)了許多錯(cuò)誤。如：將函數(shù)定義為有返回值類(lèi)型時(shí)，總是忘記return 0語(yǔ)句，因?yàn)椴恍枰祷匾粋€(gè)實(shí)際值，所以返回0值很容易被忽略。對(duì)于遞歸調(diào)用的使用不熟練，翻書(shū)及上網(wǎng)查詢(xún)后才會(huì)應(yīng)用。實(shí)驗(yàn)總結(jié)這次實(shí)驗(yàn)主要是通過(guò)先序序列建立二叉樹(shù)，和二叉樹(shù)的先序、中序、后續(xù)遞歸遍歷算法。通過(guò)這次實(shí)驗(yàn)，我鞏固了二叉樹(shù)這部分知識(shí),從中體會(huì)理論知識(shí)的重要性。 在做實(shí)驗(yàn)之前，要充分的理解本次實(shí)驗(yàn)的理論依據(jù)。 例如進(jìn)行二叉樹(shù)的遍歷的時(shí)候，要先理解各種遍歷的特點(diǎn)。先序遍歷是先遍歷根節(jié)點(diǎn)，再依次先序遍歷左右子樹(shù)。中序遍歷是先中序遍歷左子

5、樹(shù)，再訪問(wèn)根節(jié)點(diǎn)，最后中序遍歷右子樹(shù)。而后序遍歷則是先依次后續(xù)遍歷左右子樹(shù)，再訪問(wèn)根節(jié)點(diǎn)。  附錄 實(shí)驗(yàn)程序代碼遍歷二叉樹(shù)#include <stdio.h>#include <stdlib.h>typedef struct TNode char data;/字符型數(shù)據(jù) struct TNode *lchild,*rchild;/左右孩子指針 TNode,* Tree; /*建立二叉樹(shù)函數(shù)*/ int CreateTree(Tree &T) /按先序序列創(chuàng)建二叉樹(shù) char data; scanf("%c",&data);

6、if(data = '#')/#表示空樹(shù) T = NULL; else /按先序序列輸入二叉樹(shù) T = (Tree)malloc(sizeof(TNode); T->data = data; CreateTree(T->lchild); CreateTree(T->rchild); return 0; void Visit(Tree T) if(T->data != '#') printf("%c ",T->data); /*先序遍歷函數(shù)*/ void PreOrder(Tree T) if(T != NULL)

7、 Visit(T); PreOrder(T->lchild); PreOrder(T->rchild); /*中序遍歷函數(shù)*/ void InOrder(Tree T) if(T != NULL) InOrder(T->lchild); Visit(T); InOrder(T->rchild); /*后序遍歷函數(shù)*/ void PostOrder(Tree T) if(T != NULL) PostOrder(T->lchild); PostOrder(T->rchild); Visit(T); /*主函數(shù)*/ int main() Tree T; CreateTree(T); printf("先序遍歷：n"); PreOrder(T); printf("n"); printf("中序遍歷：n"); InOrder(T); printf("n"); printf("后序