數(shù)據(jù)結(jié)構課程設計說明書 樹的應用 樹和二叉樹的轉(zhuǎn)換

1、中北大學 中北大學數(shù)據(jù)結(jié)構與算法課程設計 數(shù)據(jù)結(jié)構與算法課程設計說 明 書學 院 、 系 ： 軟件學院專 業(yè)： 軟件工程班 級： 1314010xxx學 生 姓 名： 名： 學 號： 號： 1314010xxx設 計 題 目： 樹的應用起 迄 日 期: 2015 年 1 月 12 日- 2015 年 1 月 29 日指 導 教 師: 尹四清2015 年 1 月 29 日2樹的后根序列 樹的后根序列 E F

2、 B C I J K H G D A由樹和二叉樹的轉(zhuǎn)換關系知，二叉樹的先序和中序遍歷所得序列分別與樹的先根和后根遍歷所得序列相同，據(jù)此驗證轉(zhuǎn)化是否正確。二叉樹的先序和中序遍歷序列如下：二叉樹先序序列 二叉樹先序序列 A B E F C D G H I J K二叉樹中序序列 二叉樹中序序列 E F B C I J K H G D A二、概要設計為了實現(xiàn)上述程序功能，樹采用孩子

3、兄弟表示法，二叉樹采用二叉鏈表表示法。為此，需要兩個抽象數(shù)據(jù)類型，樹和二叉樹的抽象數(shù)據(jù)類型。1.樹的抽象數(shù)據(jù)類型定義ADT Tree{ 數(shù)據(jù)對象 D：D 是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關系 R：若 D 為空集，則稱為空樹； 若 D 僅含有一個數(shù)據(jù)元素，則 R 為空集，否則 R={H}，H 是如下二元關系： (1)在 D 中存在唯一的稱為根的數(shù)據(jù)元素 root，它在關系 H 下無前驅(qū)； (2)若 D-{root}≠Φ，則存在

4、D-{root}的一個劃分 D1,D2,D3, ?,Dm(m>0)，對于任意 j≠k(1≤j,k≤m)有 Dj∩Dk=Φ,且對任意的 i(1≤i≤m)，唯一存在數(shù)據(jù)元素 xi∈Di 有∈H;(3)對應于 D-{root}的劃分，H-{,?,}有唯一的一個劃分H1，H2,?,Hm(m>0)，對任意 j≠k(1≤j,k≤m)有 Hj∩Hk=Φ，且對任意 i(1≤i≤m),Hi 是 Di 上的二元關系，(Di,{Hi})是一棵符合