實驗內(nèi)容 實驗內(nèi)容 1 編寫函數(shù) 輸入字符序列 建立 二叉樹的 二叉鏈表 2 編寫函數(shù) 實現(xiàn)二叉樹的中序遞歸遍歷算法 最好也能實現(xiàn)前綴和后綴遍 歷算法 3 編寫函數(shù) 實現(xiàn)二叉樹的中序非遞歸遍歷算法 4 編寫函數(shù) 借助隊列實現(xiàn)二叉樹的層次遍歷算法 5 編寫函數(shù) 求二叉樹的高度 6 編寫函數(shù) 求二叉樹的結(jié)點個數(shù) 7 編寫函數(shù) 求二叉樹的葉子個數(shù) 8 編寫函數(shù) 交換二叉樹每個結(jié)點的左子樹和右子樹 9 編寫一個主函數(shù) 在主函數(shù)中設(shè)計一個簡單的菜單 分別調(diào)試上述算法 實驗?zāi)康募耙?實驗?zāi)康募耙?1 掌握二叉樹的存儲實現(xiàn) 2 掌握二 叉樹的遍歷思想 3 掌握二叉樹的 常見算法的程序?qū)崿F(xiàn) 實驗內(nèi)容 方法與步驟 使用附頁填寫并附在本頁后 實驗內(nèi)容 方法與步驟 使用附頁填寫并附在本頁后 實驗結(jié)果 實驗結(jié)果 小結(jié) 小結(jié) 通過這次實驗 我體會到深刻理解數(shù)據(jù)結(jié)構(gòu)的重要性 只有真正理解定義數(shù)據(jù)類 型的好處才能用好這樣一種數(shù)據(jù)結(jié)構(gòu) 在一開始定義數(shù)據(jù)結(jié)構(gòu)時 不夠細心 總有問題出現(xiàn) 如數(shù)據(jù)域與指針域的定義 類型的不同 在輸好了結(jié)構(gòu)體之后 我開始一個個編寫本實驗要求實現(xiàn)功能的子函數(shù) 以前總覺得使用遞歸算法是非常難的事情 很復(fù)雜很亂 經(jīng)常會理解不了而導(dǎo)致 編程出錯 但這次的實驗中二叉樹的中序 先序 后序遍歷都使用了遞歸算法 而且 用起來并不復(fù)雜 這使我更進一步地學(xué)習(xí)和理解了函數(shù)的遞歸調(diào)用并得到靈活的運用 還有 再次發(fā)現(xiàn)自己對指針的認識還很膚淺 也常常使所設(shè)計的程序無法實現(xiàn)需 求功能 所以最后我選擇了棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)來實現(xiàn) 通過本實驗調(diào)試過程中出現(xiàn)的一些問題 我對二叉樹的結(jié)構(gòu)有了較為深入的理解 相信以后在更多的嘗試之中 自己會不斷進步 include include define MAXSIZE 100 typedef char DataType typedef struct BiTNode 二叉鏈表存儲結(jié)構(gòu)二叉鏈表存儲結(jié)構(gòu) DataType data struct BiTNode lchild rchild BiTree typedef BiTree ElemType 棧中數(shù)據(jù)元素類型 棧中保存結(jié)點指針棧中數(shù)據(jù)元素類型 棧中保存結(jié)點指針 typedef struct ElemType data MAXSIZE int top SeqStack 棧的類型定義 順序棧棧的類型定義 順序棧 typedef struct ElemType queue MAXSIZE int front rear SP SeqStack initSeqStack 初始化棧初始化棧 SeqStack s 首先建立?？臻g 然后初始化棧頂指針首先建立?？臻g 然后初始化棧頂指針 s SeqStack malloc sizeof SeqStack s top 1 return s int push SeqStack s ElemType x if s top MAXSIZE 1 棧滿不能入棧棧滿不能入棧 printf 棧滿棧滿 return 0 s top s data s top x return 1 void pop SeqStack s 出棧 假設(shè)棧不空出棧 假設(shè)棧不空 s top int empty SeqStack s if s top 1 return 1 else return 0 ElemType top SeqStack s 設(shè)棧不空設(shè)棧不空 return s data s top 遞歸算法創(chuàng)建二叉鏈表遞歸算法創(chuàng)建二叉鏈表 BiTree createBiTree DataType ch BiTree T ch getchar if ch 0 return NULL else T BiTree malloc sizeof BiTree T data ch T lchild createBiTree T rchild createBiTree return T 中序遍歷二叉樹的遞歸算法中序遍歷二叉樹的遞歸算法 void InOrder BiTree T if T InOrder T lchild printf c T data InOrder T rchild 前序遍歷二叉樹的遞歸算法前序遍歷二叉樹的遞歸算法 void PreOrder BiTree T if T printf c T data PreOrder T lchild PreOrder T rchild 后序遍歷二叉樹的遞歸算法后序遍歷二叉樹的遞歸算法 void PostOrder BiTree T if T PostOrder T lchild PostOrder T rchild printf c T data 中序遍歷二叉樹的非遞歸算法中序遍歷二叉樹的非遞歸算法 void InOrderFei BiTree p SeqStack s s initSeqStack while 1 while p push s p p p lchild 先將結(jié)點指針壓棧 待出棧時再訪問先將結(jié)點指針壓棧 待出棧時再訪問 if empty s break p top s pop s printf c p data p p rchild 按層次遍歷按層次遍歷 void LevelOrder BiTree T SP p p SP malloc sizeof SP p front 0 p rear 0 if T NULL p queue p front T p front p front 1 while p front p rear T p queue p rear p rear p rear 1 printf c T data if T lchild NULL p queue p front T lchild 左孩子進隊列左孩子進隊列 p front p front 1 if T rchild NULL p queue p front T rchild 右孩子進隊列右孩子進隊列 p front p front 1 求二叉樹的高度求二叉樹的高度 int height BiTree T int i j if T return 0 i height T lchild 求左子樹的高度求左子樹的高度 j height T rchild 求右子樹的高度求右子樹的高度 return i j i 1 j 1 二叉樹的高度為左右子樹中較高的高度加二叉樹的高度為左右子樹中較高的高度加 1 求二叉樹的所有結(jié)點個數(shù)求二叉樹的所有結(jié)點個數(shù) int Nodes BiTree T int n1 n2 if T NULL return 0 else if T lchild NULL else n1 Nodes T lchild n2 Nodes T rchild return n1 n2 1 求二叉樹的葉子結(jié)點個數(shù)求二叉樹的葉子結(jié)點個數(shù) int leafs BiTree T int num1 num2 if T NULL return 0 else if T lchild NULL num1 leafs T lchild 求左子樹中葉子結(jié)點數(shù)求左子樹中葉子結(jié)點數(shù) num2 leafs T rchild 求右子樹中葉子結(jié)點數(shù)求右子樹中葉子結(jié)點數(shù) return num1 num2 交換二叉樹的所有左右子樹交換二叉樹的所有左右子樹 void exchange BiTree T BiTree temp NULL if T lchild NULL else temp T lchild T lchild T rchild T rchild temp if T lchild exchange T lchild if T rchild exchange T rchild 交換后二叉樹的遍歷交換后二叉樹的遍歷 void Display BiTree T printf t 交換后二叉樹按中序遍歷輸出交換后二叉樹按中序遍歷輸出 InOrder T printf n printf t 交換后二叉樹按前序遍歷輸出交換后二叉樹按前序遍歷輸出 PreOrder T printf n printf t 交換后二叉樹按后序遍歷輸出交換后二叉樹按后序遍歷輸出 PostOrder T printf n void menu printf n printf t t1 遞歸遞歸 創(chuàng)建二叉鏈表創(chuàng)建二叉鏈表 n printf t t2 遞歸遞歸 中序遍歷二叉樹中序遍歷二叉樹 n printf t t3 遞歸遞歸 前序遍歷二叉樹前序遍歷二叉樹 n printf t t4 遞歸遞歸 后序遍歷二叉樹后序遍歷二叉樹 n printf t t5 非遞歸非遞歸 中序遍歷二叉樹中序遍歷二叉樹 n printf t t6 層次層次 遍歷二叉樹遍歷二叉樹 n printf t t7 二叉樹的高度二叉樹的高度 n printf t t8 二叉樹的結(jié)點個數(shù)二叉樹的結(jié)點個數(shù) n printf t t9 二叉樹的葉子結(jié)點個數(shù)二叉樹的葉子結(jié)點個數(shù) n printf t t10 交換二叉樹的所有左右子樹交換二叉樹的所有左右子樹 n printf t t0 退出系統(tǒng)退出系統(tǒng) n printf n t 請選擇請選擇 void main BiTree bt bt NULL int n m 1 while m menu scanf d getchar switch n case 1 printf n t 請輸入結(jié)點的前序序列創(chuàng)建二叉樹請輸入結(jié)點的前序序列創(chuàng)建二叉樹 0 表示空表示空 bt createBiTree break 生成二叉樹生成二叉樹 case 2 printf n t 遞歸遞歸 中序遍歷二叉樹中序遍歷二叉樹 InOrder bt printf n break case 3 printf n t 遞歸遞歸 前序遍歷二叉樹前序遍歷二叉樹 PreOrder bt printf n break case 4 printf n t 遞歸遞歸 后序遍歷二叉樹后序遍歷二叉樹 PostOrder bt printf n break case 5 printf n t 非遞歸非遞歸 中序遍歷二叉樹中序遍歷二叉樹 InOrderFei bt printf n break case 6 printf n t 按層次遍歷二叉樹按層次遍歷二叉樹 LevelOrder bt printf n break case 7 printf n t 二叉樹的高度為二叉樹的高度為 d n height bt p