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

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

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

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

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