數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三二叉樹(shù)基本操作及運(yùn)算實(shí)驗(yàn)報(bào)告

1、《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫(kù)》《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫(kù)》實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目實(shí)驗(yàn)題目二叉樹(shù)的基本操作及運(yùn)算二叉樹(shù)的基本操作及運(yùn)算一、一、需要分析需要分析問(wèn)題描述：?jiǎn)栴}描述：實(shí)現(xiàn)二叉樹(shù)（包括二叉排序樹(shù)）的建立，并實(shí)現(xiàn)先序、中序、后序和按層次遍歷，計(jì)算葉子結(jié)點(diǎn)數(shù)、樹(shù)的深度、樹(shù)的寬度，求樹(shù)的非空子孫結(jié)點(diǎn)個(gè)數(shù)、度為2的結(jié)點(diǎn)數(shù)目、度為2的結(jié)點(diǎn)數(shù)目，以及二叉樹(shù)常用運(yùn)算。問(wèn)題分析：?jiǎn)栴}分析：二叉樹(shù)樹(shù)型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，對(duì)它的熟練掌握是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的

2、基本要求。由于二叉樹(shù)的定義本身就是一種遞歸定義，所以二叉樹(shù)的一些基本操作也可采用遞歸調(diào)用的方法。處理本問(wèn)題，我覺(jué)得應(yīng)該：刪除B后，以廣義表形式打印A（，C（F（，G）））二、二、概要設(shè)計(jì)概要設(shè)計(jì)程序中將涉及下列兩個(gè)抽象數(shù)據(jù)類型：一個(gè)是二叉樹(shù)，一個(gè)是隊(duì)列。1、設(shè)定“二叉樹(shù)”的抽象數(shù)據(jù)類型定義：、設(shè)定“二叉樹(shù)”的抽象數(shù)據(jù)類型定義：ADTBiTree數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：若，則，稱BiTre

3、e為空二叉樹(shù)；??D??R若，則，H是如下二元關(guān)系：??D??HR?（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；（2）若則存在且?????rootD????rlDDrootD?????rlDD（3）若則中存在唯一的元素且存在上的關(guān)系??lDlDlxHxrootl???lD若則中存在唯一的元素且存在上的HHl???rDrDrxHxrootr???rD關(guān)系；??rlrlrHHxrootxrootHHH??????（4

4、）是一棵符合本定義的二叉樹(shù)，稱為根的左子樹(shù)，是一棵符合????llHD????rrHD本定義的二叉樹(shù)，稱為根的有字樹(shù)基本操作：基本操作：CreateBiTree&T)操作結(jié)果：按照T的定義構(gòu)造一個(gè)二叉樹(shù)。BiTreeDepth(&T)初始條件：二叉樹(shù)T已存在。操作結(jié)果：返回T的深度。BiTreeWidth(&T)初始條件：二叉樹(shù)T已存在。操作結(jié)果：返回T的寬度。PreOderTraverse&T)初始條件：二叉樹(shù)T已存在。操作結(jié)果：先序