數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說(shuō)明書(shū) 樹(shù)的應(yīng)用 樹(shù)和二叉樹(shù)的轉(zhuǎn)換

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

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

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

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