數(shù)據(jù)結(jié)構(gòu)第六章作業(yè)及答案課件

數(shù)據(jù)結(jié)構(gòu)第六章作業(yè)1、已知一棵樹(shù)邊的集合為{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<H,L>,<C,H>,<A,C>},請(qǐng)畫出這棵樹(shù),并回答下列問(wèn)題:(1)哪些是葉子結(jié)點(diǎn)?(2)哪些是結(jié)點(diǎn)G的雙親?(3)哪些是結(jié)點(diǎn)G的祖先?(4)哪些是結(jié)點(diǎn)E的子孫?(5)樹(shù)的深度是多少?2、(1)二叉樹(shù)與樹(shù)之間有何區(qū)別？

(2)一棵度為2的樹(shù)與二叉樹(shù)有何區(qū)別？1數(shù)據(jù)結(jié)構(gòu)第六章作業(yè)13、試分別畫出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。4、對(duì)右圖所示的二叉樹(shù)求出以下的遍歷序列：

(1)先序序列

(2)中序序列

(3)后序序列5、假設(shè)一棵二叉樹(shù)的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。請(qǐng)畫出該樹(shù)，并給出后序序列。6、假設(shè)一棵二叉樹(shù)的中序序列為DCBGEAHFIJK和后序序列為DCEGBFHKJIA。請(qǐng)畫出該樹(shù)，并給出先序序列。ABCDGEFH23、試分別畫出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)ABCDGE7、將以下森林轉(zhuǎn)換成二叉樹(shù)。CABFGEDKJLIH37、將以下森林轉(zhuǎn)換成二叉樹(shù)。CABFGEDKJLIH38、畫出和下列二叉樹(shù)相應(yīng)的森林。(a)(b)(c)(d)(e)

ABCACBACBAHDGBAFCIKEJM48、畫出和下列二叉樹(shù)相應(yīng)的森林。ABCACBACBAHDGB第六章作業(yè)解答1、(1)M、N、D、L、F、J、K是葉子結(jié)點(diǎn)

(2)C是結(jié)點(diǎn)G的雙親

(3)A、C是結(jié)點(diǎn)G的祖先

(4)I、M、N是結(jié)點(diǎn)E的子孫

(5)樹(shù)的深度是52、(1)二叉樹(shù)與樹(shù)的區(qū)別:

二叉樹(shù)的一個(gè)結(jié)點(diǎn)至多有2個(gè)子樹(shù),樹(shù)則不然;

二叉樹(shù)的一個(gè)結(jié)點(diǎn)有左、右之分,而樹(shù)則沒(méi)有此要求

(2)一棵度為2的樹(shù)有2個(gè)分支,沒(méi)有左、右之分,

一棵二叉樹(shù)也可以有2個(gè)分支,但有左、右之分,

且左、右不能交換。3、具有3個(gè)結(jié)點(diǎn)的樹(shù)的形態(tài)為:5第六章作業(yè)解答5有3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有形態(tài)為:

664、解：

(1)先序序列為：ABDGCEFH(2)中序序列為：DGBAECHF(3)后序序列為：GDBEHFCA5、后序序列為：ACDBGJKIHFE6、先序序列為：ABCDGEIHFJKEBDACFHIGKJABCGDEIHJFK74、解：EBDACFHIGKJABCGDEIHJFK77、解：轉(zhuǎn)換后的二叉樹(shù)為：ABCDEIHFGJLK87、解：轉(zhuǎn)換后的二叉樹(shù)為：ABCDEIHFGJLK88、解：轉(zhuǎn)換后的森林為：

ACABBAC(a)(b)(c)ABC(d)(e)ABCFIMKDGHJE98、解：轉(zhuǎn)