1、課程設計二叉樹的基本操作課程設計論文學生姓名 學 號 所屬學院 信息工程學院 專 業(yè) 計算機科學與技術 班 級 計算機 指導教師 教師職稱 講師 塔里木大學教務處制目錄前言1正文12.1設計目的及意義12.2問題描述12.3 數(shù)據(jù)結構分析22.4算法設計及分析22.5算法測試及分析6總結7參考文獻8附錄9前言數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作的學科。通過一學期的學習，對數(shù)據(jù)結構這門學科有了了解。為了檢驗這學期所學的知識，不光要通過考試，還要對其中的知識點進行深一步的了解探討和研究。所以做這個課程設計對知識點可以深度的研究。當數(shù)據(jù)的邏輯結構確定以

2、后，數(shù)據(jù)在物理空間中的存儲方式，稱為數(shù)據(jù)的存儲結構。同一邏輯結構可以具有不同的存儲結構，因而有不同的算法。本次課程設計，程序中的數(shù)據(jù)采用“樹形結構”作為其數(shù)據(jù)結構。具體采用的是二叉樹。二叉樹是樹形結構的一個重要的類型，二叉樹是n(n0)個結點的有限集，它或者是空集(n0),或者由一個根結點以及兩棵互不相交的，分別稱為左子樹和右子樹的二叉樹組成。二叉樹的順序存儲結構是把二叉樹所有結點，按照一定的次序排序，存儲到一片連續(xù)的存儲單元中。但二叉樹的順序存儲結構浪費空間并且插入、刪除不方便。二叉樹的鏈式存儲每個結點至少包含三個域：數(shù)據(jù)域、左指針域、右指針域，不浪費空間。二叉樹的存儲結構和算法比較簡單，特

3、別適合計算機處理，即使一般形式的樹也可簡單的轉換為二叉樹。現(xiàn)實中經(jīng)常用到二叉樹，因此本課程設計主要實現(xiàn)了二叉樹的建立、三種遍歷，計算二叉數(shù)的樹深、統(tǒng)計葉子結點的個數(shù)等功能。正文2.1設計目的及意義課程設計為學生提供了一個既動手又動腦，獨立實踐的機會，將課本上的理論知識和實際有機的結合起來，鍛煉學生的分析解決實際問題的能力。提高學生適應實際，實踐編程的能力。2.2問題描述二叉樹的很多操作都是基于遍歷實現(xiàn)的。二叉樹的遍歷是采用某種策略使得采用樹型結構組織的若干結點對應于一個線性序列。二叉樹的遍歷策略有四種先序遍歷、中序遍歷、后序遍歷和層次遍歷。(1)按先序次序輸入二叉樹中結點的值,構造二叉鏈表表示

4、的二叉樹t；(2)對二叉樹t作先序、中序、后序遍歷的遞歸算法,輸出結果；(3)計算二叉樹t的深度,輸出結果；(4)計算二叉樹t的葉子結點個數(shù)2.3 數(shù)據(jù)結構分析本程序分為：7大模塊。二叉樹的建立鏈式存儲結構、前序遍歷、中序遍歷、后序遍歷、求葉子結點的個數(shù)計算、中序遍歷、后序遍歷、深度、主函數(shù)。1、二叉樹的建立鏈式存儲結構；首先typedef struct bitnode：定義二叉樹的鏈式存儲結構，此處采用了每個結點中設置三個域，data：即值域，*lchild：左指針域和rchild：右指針域。2、二叉樹的前序遍歷；利用二叉鏈表作為存儲結構的前序遍歷：先訪問根結點，再依次訪問左右子樹。3、二叉

5、樹的中序遍歷；利用二叉鏈表作為存儲結構的中序遍歷：先訪問左子數(shù)，再訪問根結點，最后訪問右子樹。4、二叉樹的后序遍歷；利用二叉鏈表作為存儲結構的前序遍歷：先訪問左右子樹，再訪問根結點。5、求二叉樹的深度：首先判斷二叉樹是否為空，若為空則此二叉樹的深度為0。否則，就先別求出左右子樹的深度并進行比較，取較大的+1就為二叉樹的深度。6、二叉樹的求葉子結點的個數(shù)計算；先分別求得左右子樹中各葉子結點個數(shù)，再計算出兩者之和即為二叉樹的葉子結點數(shù)。7、主函數(shù)。主函數(shù)中分別調(diào)用各函數(shù)。2.4算法設計及分析算法流程圖main()createbitree ()構造二叉樹preordertraverse()nrpre

6、order（）分別輸出遞歸與非遞歸先序遍歷結果inordertrave（）nrinorder（）分別輸出中序遞歸與非遞歸遍歷結果postordertravesr()nrpostorder（）分別輸出遞歸與非遞歸的后序遍歷結果求結點的中序前驅后繼中序inordertraver（） 1、存儲結構的建立由遞歸函數(shù)實現(xiàn)具體函數(shù)為：typedef struct bitnode telemtype data; struct bitnode *lchild,*rchild;bitnode ,*bitree;bitree createbitree(bitree t)char ch;scanf(%c,&ch);

7、if(ch=#) t=null;elseif(!(t=(bitnode *)malloc(sizeof(bitnode) exit(overflow);t-data=ch;t-lchild=createbitree(t-lchild);t-rchild=createbitree(t-rchild);return t;在創(chuàng)建的二叉樹中，左右孩子都為字符型。char的作用是輸入n個任意的字符，而且在輸入n個字符后，必須輸入n+1個#，才能得到本程序所有能夠實現(xiàn)的功能。t=null是將二叉樹置空。if(!(t=(bitnode *)malloc(sizeof(bitnode)，采用動態(tài)申請新結點的方

8、式，不僅實現(xiàn)起來方便，而且還節(jié)省大量的存儲空間。t-data=ch;值域t-lchild=createbitree(t-lchild);t-rchild=createbitree(t-rchild);將二叉樹中的每一個結點設置為：值域，左指針域，右指針。這一小段程序實現(xiàn)了二叉樹的置空，二叉樹的建立，二叉樹的存儲。2、前序遍歷：先訪問根結點，再訪問左子樹，最后訪問右子樹。具體函數(shù)為：void preordertraverse(bitree t)if(t)printf(%c,t-data);preordertraverse(t-lchild);preordertraverse(t-rchild);

9、3、中序遍歷：先訪問左子樹，再訪問根結點，最后訪問右子樹。具體函數(shù)為：void inordertraverse(bitree t) if (t) inordertraverse(t-lchild);printf(%c,t-data);inordertraverse(t-rchild); 4、后序遍歷：先訪問左子樹，再訪問右子樹，最后訪問根結點。具體函數(shù)為：void postordertraverse(bitree t) if(t)postordertraverse(t-lchild);postordertraverse(t-rchild);printf(%c,t-data); 5、求二叉樹的深

10、度：先定義三個整形變量m,n.如果樹為空，則height=0；否則，先分別訪問出左右子樹的深度，再進行比較，將較大的+1的結果就是所求二叉樹的深度。具體函數(shù)為：int height(bitree t)int m,n;if(t=null) return 0;else m=height(t-lchild);n=height(t-rchild);return (mn)?m+1:n+1;6、求葉子結點的個數(shù)：用leafcount變量表示葉子結點的總個數(shù)，用leafcount(t-lchild)、leafcount(t-rchild)分別表示訪問的左右子樹中葉子結點的個數(shù)。當樹為空是此時討論葉子結點個數(shù)

11、無意義；當樹非空時分為：一、左右子數(shù)都不存在時，即葉子結點的個數(shù)為1；二、左右子樹存在，就用分別訪問出左右子樹中葉子結點的個數(shù)，兩者相加就為二叉樹葉子結點的個數(shù)。具體函數(shù)為：int leafcount(bitree t) if(!t) return 0; /空數(shù)無葉子 else if(!t-lchild&!t-rchild) return 1; else return leafcount(t-lchild)+leafcount(t-rchild);7、主函數(shù)：包括：二叉樹的數(shù)據(jù)結構bitree t、函數(shù)createbitree、height、leafcount、前序遍歷preordertrav

12、erse、中序遍歷inordertraverse、后序遍歷postordertraverse。具體函數(shù)為：void main()bitree t;int w,v;printf(請輸入建樹字符序列:);t=createbitree(t);printf(先續(xù)遍歷的結果是:);preordertraverse(t);printf(n);printf(中續(xù)遍歷的結果是:);inordertraverse(t);printf(n);printf(后續(xù)遍歷的結果是:);postordertraverse(t);printf(n);printf(二叉樹的深度是:);w=height(t);printf(%d

13、n,w);printf(二叉樹的葉子結點的數(shù)目為:);v=leafcount(t);printf(%d,v);printf(n);2.5算法測試及分析建立一個二叉樹 遍歷二叉樹結點求二叉樹所有結點數(shù)總結通過對二叉樹的基本操作的學習，熟悉的掌握了二叉樹的結構特性，掌握了二叉樹的鏈式存儲結構的特點和適用范圍，通過二叉樹的基本操作實現(xiàn)，思考一般樹的基本操作的實現(xiàn)。熟悉掌握各種遍歷各種二叉樹的策略的遞歸和非遞歸算法。在對二叉樹基本操作的學習過程中不斷對其中的算法思想進行改進和修正，更熟悉的掌握關于二叉樹的基本操作. 熟練掌握二叉樹的結構特性，了解相應的證明方法。 熟悉二叉樹的各種存儲結構的特點及適用范

14、圍。 遍歷二叉樹是二叉樹各種操作的基礎。實現(xiàn)二叉樹遍歷的具體算法與所采用的存儲結構有關。不僅要熟練掌握各種遍歷策略的遞歸和非速歸算法，了解遍歷過程中 棧 的作用和狀態(tài)，而且能靈活運用遍歷算法實現(xiàn)二叉樹的其它操作。層次遍歷是按另一種搜索策略進行的遍歷。 理解二叉樹線索化的實質(zhì)是建立結點與其在相應序列中的前驅或后繼之間的直接聯(lián)系，熟練掌握二叉樹的線索化過程以及在中序線索化樹上找給定結點的前驅和后繼的方法。二叉樹的線索化過程是基于對二叉樹進行遍歷，而線索二叉樹上的線索又為相應的遍歷提供了方便。 熟悉樹的各種存儲結構及其特點，掌握樹和森林與二叉樹的轉換方法。建立存儲結構是進行其它操作的前提，因此讀者應

15、掌握 1 至 2 種建立二叉樹和樹的存儲結構的方法。學會編寫實現(xiàn)樹的各種操作的算法。 了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。 理解前序序列和中序序列可唯一確定一棵二叉樹的道理，理解具有相同的前序序列而中序序列不同的二叉樹的數(shù)目與序列 12n 按不同順序進棧和出棧所能得到的排列的數(shù)目相等的道理，掌握由前序序列和中序序列建立二叉樹的存儲結構的方法。參考文獻1 嚴蔚敏，吳偉民.數(shù)據(jù)結構（c語言版）.第1版.北京；清華大學出版社，2005年；58-64.2 嚴蔚敏，吳偉民.數(shù)據(jù)結構題集（c語言版）.第1版.北京；清華大學出版社，2005年；96-105.3 李春葆，章啟俊.c+程序設計.

16、第1版.北京；清華大學出版社，2007年；56-31.4 譚浩強.c程序設計（第二版）.第6版.北京；清華大學出版社，2004年；9-15.5 陳一華等編.數(shù)據(jù)結構-使用c 語言.第一版.北京；電子科技大學出版社，1998年；12-14.6 許卓群數(shù)據(jù)結構第一版. 北京；高等教育出版社，1989年；14-18.7 嚴蔚敏，吳偉民數(shù)據(jù)結構題集（c語言版）第一版. 北京；清華大學出版社，1999；3-10.8 蔡明志數(shù)據(jù)結構（使用c語言）第二版. 北京；科學出版社，1997年；12-15.9 蔡自經(jīng)，施伯樂數(shù)據(jù)結構教程第二版. 上海；復旦大學出版社，1984年，11-14.附錄源代碼:#inclu

17、de #include #include #define ok 1#define error 0#define overflow -1typedef char telemtype;typedef struct bitnode telemtype data; struct bitnode *lchild,*rchild;bitnode ,*bitree;bitree createbitree(bitree t)char ch;scanf(%c,&ch);if(ch=#) t=null;elseif(!(t=(bitnode *)malloc(sizeof(bitnode) exit(overfl

18、ow);t-data=ch;t-lchild=createbitree(t-lchild);t-rchild=createbitree(t-rchild);return t; void preordertraverse(bitree t) if(t)printf(%c,t-data);preordertraverse(t-lchild);preordertraverse(t-rchild); void inordertraverse(bitree t)if (t) inordertraverse(t-lchild);printf(%c,t-data);inordertraverse(t-rchild); void postordertraverse(bitree t) if(t)postordertraverse(t-lchild);