數據結構課程設計報告二叉樹的遍歷報告

1、-. z.數據構造課程設計報告姓 名班 級學 號指導教師課程設計目的培養(yǎng)學生用學到的書本知識解決實際問題的能力；培養(yǎng)實際工作所需要的動手能力；培養(yǎng)學生以科學理論和工程上能力的技術，規(guī)*地開發(fā)大型、復雜、高質量的應用軟件和系統軟件具有關鍵性作用；通過課程設計的實踐，學生可以在程序設計方法、上機操作等根本技能和科學作風方面受到比擬系統和嚴格的訓練。課程設計要求1)學生必須仔細閱讀數據構造課程設計方案，認真主動完成課程設計的要求。有問題及時主動通過各種方式與教師聯系溝通。2)學生要發(fā)揮自主學習能力，充分利用時間，安排好課程設計的時間方案，并在課程設計過程中不斷檢測自己的方案完成情況，及時向教師匯報。

2、3)課程設計按照教學方案需要一周時間完成，一周中每天至少要上兩小時的上機來調試C或C+語言設計的程序，總共至少要上機調試程序10小時。屬教師安排上機時間學生不得缺席。課程設計內容二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現，應包含建樹的實現。課程設計原理設計思想以廣義表格式輸入一個二叉樹，將其接收至一維數組中，利用棧構造建立二叉鏈表樹；通過先、中、后訪問根結點遞歸算法遍歷二叉樹；利用棧構造依次將結點入棧、出棧實現二叉樹的非遞歸遍歷算法；利用隊列的入隊、出隊操作實現二叉樹的層次遍歷。例如：a(c(,d)，f(g,)建立如下列圖所示二叉樹。cadfg數據構造type

3、def BTREENODEPTR elemtype;隊列數據類型定義typedef struct elemtype *elem; int front,rear; int size;SqQueue;棧數據類型定義typedef struct stack_tag elemtype *elem; int top; int size;SQSTACK; 二叉樹數據類型定義typedef struct btreenode char data; struct btreenode *lchild,*rchild;BTREENODE,*BTREENODEPTR,*BTREE;主要模塊設計BTREE Create

4、Btree1(char *str)；/創(chuàng)立二叉樹void PreOrder(BTREE root)；/先序遞歸遍歷二叉樹void InOrder(BTREE root)；/中序遞歸遍歷二叉樹void PostOrder(BTREE root)；/后序遞歸遍歷二叉樹void PreOrder_1(BTREE root)；/先序非遞歸遍歷二叉樹void InOrder_1(BTREE root)；/中序非遞歸遍歷二叉樹void PostOrder_1(BTREE root)；/后序非遞歸遍歷二叉樹void LayerOrder(BTREE root)；/層次遍歷其他模塊包括棧的初始化及其根本操作和

5、隊列的初始化及根本操作。主菜單先序遞歸遍歷中序遞歸遍歷后序遞歸遍歷先序非遞歸遍歷中序非遞歸遍歷后序非遞歸遍歷層次遍歷完畢將以廣義表形式輸入的二叉樹接收到數組str80中，成功建立二叉樹詳細設計二叉樹的建立其中mark的值1、2、3、4分別指stri為字母、(、，、)；tag為左、右孩子的標志；root=null檢查str10()，mark=1；root-data=str0,root-lchild=root-rchild=null;p=root;str0是否為字母YNNmark=2mark=2stri入棧tag=0mark=3mark=3tag=1Nmark=4pop為空return nullN

6、YY)mark=1&棧不空新建結點pp-data=stri p-lchild=p-rchild=nulltag=0循環(huán)完畢后return root棧頂-rchild=p棧頂-lchild=pYN二叉樹的遞歸遍歷(以先序遍歷為例)結點為空N訪問根節(jié)點先序遍歷方式遍歷左子樹先序遍歷方式遍歷右子樹完畢Y開場二叉樹的非遞歸遍歷(以先序遍歷為例)初始化隊列，root入隊棧非空出棧p；打印p-dataYp-lchild!=nullYp-lchild入棧p-lchild!=nullNYNp-rchild入棧完畢N二叉樹的層次遍歷訪問元素所指結點，假設該元素所指結點的左右孩子結點非空，則該元素所指結點的左孩子指針和右孩子指針順序入隊。初始化隊列，root入隊隊列非空出隊p；打印p-dataYp-lchild!=nullYp-lchild入隊p-lchild!=nullNYNp-rchild入隊完畢N運行結果建立二叉樹先序遍歷中序遍歷后序遍歷層次遍歷退出程序出錯信息設計總結二叉樹是數據構造的