樹與二叉樹C課件

第6章樹與二叉樹(三樹與二叉樹C（精品）第6章樹與二叉樹(三本章的基本內(nèi)容是61樹及其抽象數(shù)據(jù)類型62二叉樹及其抽象數(shù)據(jù)類型63二叉樹的表示和實(shí)現(xiàn)64線索化二叉樹6.5樹、森林與二叉樹的轉(zhuǎn)換6.6哈夫曼編碼與哈夫曼樹構(gòu)造二叉樹建立一棵二查樹必須明確以下兩點(diǎn)(1)結(jié)點(diǎn)與父母結(jié)點(diǎn)以及孩子結(jié)點(diǎn)之間的層次關(guān)系(2)兄弟結(jié)點(diǎn)間的左右子樹的次序關(guān)系能夠唯一確定一棵二查樹的表示(1)先根和中根序列表示(2)標(biāo)明空子樹的先根序列表示第6章樹與二叉樹C（精品）第6章1本章的基本內(nèi)容是61樹及其抽象數(shù)據(jù)類型62二叉樹及其抽象數(shù)據(jù)類型63二叉樹的表示和實(shí)現(xiàn)64線索化二叉樹6.5樹、森林與二叉樹的轉(zhuǎn)換6.6哈夫曼編碼與哈夫曼樹本章的基本內(nèi)容是2構(gòu)造二叉樹建立一棵二查樹必須明確以下兩點(diǎn)(1)結(jié)點(diǎn)與父母結(jié)點(diǎn)以及孩子結(jié)點(diǎn)之間的層次關(guān)系(2)兄弟結(jié)點(diǎn)間的左右子樹的次序關(guān)系能夠唯一確定一棵二查樹的表示(1)先根和中根序列表示(2)標(biāo)明空子樹的先根序列表示構(gòu)造二叉樹31)先根和中根序列表示ii+先根序列BIDIGCEIFIHpreorder左子樹右子樹根左子樹右子樹n-1中根序列|DGB|A左子樹根右子樹(a)先根與中根次序遍歷序列(b)確定根、左子樹、右子樹1)先根和中根序列表示4在BinaryTree類中增加以下構(gòu)造方法publicBinaryTree(Tlprelist,Tlinlist)Ithisroot=create(prelist,inlist,0,0,prelistlength);privateBinaryNodecreate(TDprelist,T[inlist,intpreStart,intinStart,intnif(n<=0)returnnul;Telem=prelist[preStart];BinaryNode<T>p=newBinaryNode<T>(elem);inti=Owhile(i<n&&!elem.equals(inlist[inStart+))1++pleft=create(prelist,inlist,preStart+1,instart,i)pright=create(prelist,inlist,preStart+i+1,instart+i+1,n-1-1)returnp在BinaryTree類中增加以下構(gòu)造方法5(2)標(biāo)明空子樹的先根序列表示(a)AB(b)AB(c)AB..c(d)ABd.g.ce.FH(2)標(biāo)明空子樹的先根序列表示6在BinaryTree類中增加以下構(gòu)造方法publicBinaryTree(T[prelist)Ithisroot=creatprelist);1privateinti=OprivateBinarynode<T>create(TIprelist)(BinaryNode<T>p=null;(i<prelistlength[Telem=prelist[]+if(elem!=nullip=newBinaryNode<t>(elem);pleft=create(prelistpright=create(prelist)returnp在BinaryTree類中增加以下構(gòu)造方法7如何獲得結(jié)點(diǎn)在一種遍歷序列中的前驅(qū)或后繼?leftdataright∧H人(a)一棵二叉樹(b)二叉鏈表如何獲得結(jié)點(diǎn)在一種遍歷序列中的前驅(qū)或864線索化二叉樹(ThreadedBinarytree)用二叉鏈表法(Child,rchild)存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹,結(jié)點(diǎn)的指針區(qū)域中會(huì)有多少個(gè)空指針?分析:用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹,結(jié)點(diǎn)必有2n個(gè)鏈域除根結(jié)點(diǎn)外,二又樹中每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親(直接前驅(qū)),所以只會(huì)有n-1個(gè)結(jié)點(diǎn)的鏈域存放指針,指向非空子女結(jié)點(diǎn)所以,空指針數(shù)目=2n-(n-1)=n+1個(gè)64線索化二叉樹(ThreadedBinarytree9②二叉鏈表空間效率這么低,能否利用這些空閑區(qū)存放有用的信息或線索?可以用它來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索,以加快查找速度問題的提出:普通二叉樹只能找到結(jié)點(diǎn)的左右孩子信息,而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過程中獲得若將遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來,則從第一個(gè)結(jié)點(diǎn)開始就能很快“順藤摸瓜”而遍歷整個(gè)樹可能是根、或最左(右)葉子②二叉鏈表空間效率這么低,能否利用這些空閑區(qū)10樹與二叉樹C課件11樹與二叉樹C課件12樹與二叉樹C課件13樹與二叉樹C課件14樹與二叉樹C課件15樹與二叉樹C課件16樹與二叉樹C課件17樹與二叉樹C課件18樹與二叉樹C課件19樹與二叉樹C課件20樹與二叉樹C課件21樹與二叉樹C課件22樹與二叉樹C課件23樹與二叉樹C課件24樹與二叉樹C課件25樹與二叉樹C課件26樹與二叉樹C課件27樹與二叉樹C課件28樹與二叉樹C課件29樹與二叉樹C課件30樹與二叉樹C課件31樹與二叉樹C課件32樹與二叉樹C課件33樹與二叉樹C課件34樹與二叉樹C課件35樹與二叉樹C課件36樹與二叉樹C課件37樹與二叉樹C課件38樹與二叉樹C課件39樹與二叉樹C課件40樹與二叉樹C課件41樹與二叉樹C課件42樹與二叉樹C課件43樹與二叉樹C課件44樹與二叉樹C課件45樹與二叉樹C課件46樹與二叉樹C課件47樹與二叉樹C課件48樹與二叉樹C課件49樹與二叉樹C課件50樹與二叉樹C課件51樹與二叉樹C課件52第6章樹與二叉樹(三樹與二叉樹C（精品）第6章樹與二叉樹(三本章的基本內(nèi)容是61樹及其抽象數(shù)據(jù)類型62二叉樹及其抽象數(shù)據(jù)類型63二叉樹的表示和實(shí)現(xiàn)64線索化二叉樹6.5樹、森林與二叉樹的轉(zhuǎn)換6.6哈夫曼編碼與哈夫曼樹構(gòu)造二叉樹建立一棵二查樹必須明確以下兩點(diǎn)(1)結(jié)點(diǎn)與父母結(jié)點(diǎn)以及孩子結(jié)點(diǎn)之間的層次關(guān)系(2)兄弟結(jié)點(diǎn)間的左右子樹的次序關(guān)系能夠唯一確定一棵二查樹的表示(1)先根和中根序列表示(2)標(biāo)明空子樹的先根序列表示第6章樹與二叉樹C（精品）第6章53本章的基本內(nèi)容是61樹及其抽象數(shù)據(jù)類型62二叉樹及其抽象數(shù)據(jù)類型63二叉樹的表示和實(shí)現(xiàn)64線索化二叉樹6.5樹、森林與二叉樹的轉(zhuǎn)換6.6哈夫曼編碼與哈夫曼樹本章的基本內(nèi)容是54構(gòu)造二叉樹建立一棵二查樹必須明確以下兩點(diǎn)(1)結(jié)點(diǎn)與父母結(jié)點(diǎn)以及孩子結(jié)點(diǎn)之間的層次關(guān)系(2)兄弟結(jié)點(diǎn)間的左右子樹的次序關(guān)系能夠唯一確定一棵二查樹的表示(1)先根和中根序列表示(2)標(biāo)明空子樹的先根序列表示構(gòu)造二叉樹551)先根和中根序列表示ii+先根序列BIDIGCEIFIHpreorder左子樹右子樹根左子樹右子樹n-1中根序列|DGB|A左子樹根右子樹(a)先根與中根次序遍歷序列(b)確定根、左子樹、右子樹1)先根和中根序列表示56在BinaryTree類中增加以下構(gòu)造方法publicBinaryTree(Tlprelist,Tlinlist)Ithisroot=create(prelist,inlist,0,0,prelistlength);privateBinaryNodecreate(TDprelist,T[inlist,intpreStart,intinStart,intnif(n<=0)returnnul;Telem=prelist[preStart];BinaryNode<T>p=newBinaryNode<T>(elem);inti=Owhile(i<n&&!elem.equals(inlist[inStart+))1++pleft=create(prelist,inlist,preStart+1,instart,i)pright=create(prelist,inlist,preStart+i+1,instart+i+1,n-1-1)returnp在BinaryTree類中增加以下構(gòu)造方法57(2)標(biāo)明空子樹的先根序列表示(a)AB(b)AB(c)AB..c(d)ABd.g.ce.FH(2)標(biāo)明空子樹的先根序列表示58在BinaryTree類中增加以下構(gòu)造方法publicBinaryTree(T[prelist)Ithisroot=creatprelist);1privateinti=OprivateBinarynode<T>create(TIprelist)(BinaryNode<T>p=null;(i<prelistlength[Telem=prelist[]+if(elem!=nullip=newBinaryNode<t>(elem);pleft=create(prelistpright=create(prelist)returnp在BinaryTree類中增加以下構(gòu)造方法59如何獲得結(jié)點(diǎn)在一種遍歷序列中的前驅(qū)或后繼?leftdataright∧H人(a)一棵二叉樹(b)二叉鏈表如何獲得結(jié)點(diǎn)在一種遍歷序列中的前驅(qū)或6064線索化二叉樹(ThreadedBinarytree)用二叉鏈表法(Child,rchild)存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹,結(jié)點(diǎn)的指針區(qū)域中會(huì)有多少個(gè)空指針?分析:用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹,結(jié)點(diǎn)必有2n個(gè)鏈域除根結(jié)點(diǎn)外,二又樹中每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親(直接前驅(qū)),所以只會(huì)有n-1個(gè)結(jié)點(diǎn)的鏈域存放指針,指向非空子女結(jié)點(diǎn)所以,空指針數(shù)目=2n-(n-1)=n+1個(gè)64線索化二叉樹(ThreadedBinarytree61②二叉鏈表空間效率這么低,能否利用這些空閑區(qū)存放有用的信息或線索?可以用它來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索,以加快查找速度問題的提出:普通二叉樹只能找到結(jié)點(diǎn)的左右孩子信息,而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過程中獲得若將遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來,則從第一個(gè)結(jié)點(diǎn)開始就能很快“順藤摸瓜”而遍歷整個(gè)樹可能是根、或最左(右)葉子②二叉鏈表空間效率這么低,能否利用這些空閑區(qū)62樹與二叉樹C課件63樹與二叉樹C課件64樹與二叉樹C課件65樹與二叉樹C課件66樹與二叉樹C課件67樹與二叉樹C課件68樹與二叉樹C課件69樹與二叉樹C課件70樹與二叉樹C課件71樹與二叉樹C課件72樹與二叉樹C課件73樹與二叉樹C課件74樹與二叉樹C課件75樹與二叉樹C課件76樹與二叉樹C課件77樹與二叉樹C課件78樹與二叉樹C課件79樹與二叉樹C課件80樹與二叉樹C課件81樹與二叉樹C課件82樹與二叉樹C課件83樹與二叉