二叉樹的建立與遍歷實驗報告(c語言編寫,附源代碼).doc

第 1 頁，共 9 頁二叉樹的建立與遍歷實驗報告級 班 年 月 日 姓名 學號_ 1實驗題目建立一棵二叉樹，并對其進行遍歷(先序、中序、后序)，打印輸出遍歷結果。2需求分析本程序用 VC 編寫，實現建立一棵二叉樹的功能，并對其進行遍歷(先序、中序、后序)，并且打印輸出遍歷結果。 輸入的形式和輸入值的范圍輸入二叉樹的先序，當其結點為空時，需要輸入。(輸入的先序僅含字母和) 輸出的形式輸出二叉樹的先序、中序、后序。 程序所能達到的功能實現建立一棵二叉樹的功能，并對其進行遍歷(先序、中序、后序)，并且打印輸出遍歷結果。 測試數據輸入數據輸入 ABCDEGF輸出結果二叉樹的先序遍歷為ABCDEGF二叉樹的中序遍歷為CBEGDFA二叉樹的后序遍歷為CGEFDBA3概要設計1 為了實現上述程序功能，需要定義二叉鏈表的抽象數據類型typedef struct BinaryTreeNode TElemType data;二叉樹結點中的數據域struct BinaryTreeNode *lchild , *rchild; 二叉樹結點的左孩子和右孩子指針BinaryTreeNode ,*BiTree;第 2 頁，共 9 頁基本操作A. void CreateBinaryTree BiTree 3中序遍歷二叉樹，并且輸出中序遍歷的結果 void MidOrderBiTree T; 4序遍歷二叉樹，并且輸出后序遍歷的結果 void PostOrderBiTree T; 5各函數間關系如下主函數 mainCreateBinaryTree PreOrder MidOrder PostOrder第 3 頁，共 9 頁4詳細設計1 二叉鏈表的定義typedef struct BinaryTreeNode定義一個樹結點的數據域;定義一個該結點的左孩子指針和右孩子指針;2 void CreateBinaryTree BiTree if輸入字符 T 指針置值為 NULL;else 動態申請一個指向二叉樹結構體的指針把輸入字符賦值給新指針的數據域 data;調用 CreateBinaryTree新指針的 lchild 成員;調用 CreateBinaryTree新指針的 rchild 成員;3 void PreOrderBiTree T 先序遍歷二叉樹ifT指針不為NULL輸出T的data域;先序遍歷左子樹; 先序遍歷右子樹;第 4 頁，共 9 頁4 void MidOrderBiTree T 中序遍歷二叉樹ifT指針不為NULL中序遍歷左子樹;輸出T的data域;中序遍歷右子樹;5 void PostOrderBiTree T 中序遍歷二叉樹ifT指針不為NULL后序遍歷左子樹;后序遍歷右子樹;輸出T的data域;5調試分析在編寫程序過程中，我將 scanf(”c”,typedef struct BinaryTreeNode二叉鏈表的存儲結構TElemType data;struct BinaryTreeNode *lchild , *rchild;BinaryTreeNode ,*BiTree;void CreateBinaryTree BiTree scanf“c“,ifch TNULL;else ifT BinaryTreeNode *malloc sizeofBinaryTreeNode exit -1;判斷 malloc 函數是否獲得符合要求的內存塊，是則繼續程序，否則使用 exit 函數強制退出程序第 7 頁，共 9 頁如果 malloc 函數無法獲得符合要求的內存塊，malloc 函數會返回 NULL 指針T-datach;CreateBinaryTreeT-lchild;CreateBinaryTreeT-rchild;void PreOrderBiTree T先序遍歷二叉樹ifTprintf“c “,T-data;PreOrderT-lchild; PreOrderT-rchild;void MidOrderBiTree T中序遍歷二叉樹ifTMidOrderT-lchild;第 8 頁，共 9 頁printf“c “,T-data;MidOrderT-rchild;void PostOrderBiTree T后序遍歷二叉樹ifTPostOrderT-lchild;PostOrderT-rchild;printf“c “,T-data;void mainBiTree Tree;printf“輸入字符，先序建立二叉樹n“;CreateBinaryTreeTree;printf“二叉樹的先序遍歷為n“;PreOrderTree;printf“n 二叉樹的中序遍歷為n“;第 9 頁，共 9 頁MidOrderTree;printf“n 二叉樹的后序遍歷為n“;PostOrderTree;getchar;getchar;