數(shù)據(jù)結(jié)構(gòu)與算法b-2014年4月18日課堂

數(shù)據(jù)結(jié)構(gòu)與算二叉主講教凌2014年4月18 4.5二叉樹(shù)的實(shí)4.5.1用指針實(shí)現(xiàn)二叉4.5.2空間開(kāi)銷分4.5.3用數(shù)組實(shí)現(xiàn)完全二4.5.4穿線二叉北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page中序穿線二叉北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page中序穿線二叉北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page中序穿線先從穿線樹(shù)的根出發(fā)，一直沿左指針，找到“最左”結(jié)(它一定是中序的第一個(gè)結(jié)點(diǎn))；然后反復(fù)地找結(jié)點(diǎn)中序后繼當(dāng)前結(jié)點(diǎn)的右指如果是線索，則“右指針”如果不是線索，則其右子樹(shù)的“最左”結(jié)點(diǎn)游的結(jié)點(diǎn)北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page穿線二叉原來(lái)為空的左指針指向結(jié)點(diǎn)在某種周游序列下的前原來(lái)為空的右指針指向結(jié)點(diǎn)在同一種周游序列下的后這樣的二叉樹(shù)稱為穿線樹(shù)目的：利用空指針的存儲(chǔ)空間，建立周游線索可以有中序穿線樹(shù)、前序穿線樹(shù)、后序穿線樹(shù)北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page區(qū)分線索和指lTag left為左子女指lTag rTag= right為右子女指rTag right為后繼線北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page穿線二叉樹(shù)結(jié)點(diǎn)template<classclass{intlTag,rTag;//左右標(biāo)志ThreadBinaryTreeNode<T>*left*right;Telement; ThreadBinaryTreeNode(constT) 北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Pagetemplate<class

class{intT

ThreadBinaryTreeNode(constT) 北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 PageT&value()const{returnelementThreadBinaryTreeNode<T>* {returnleft};ThreadBinaryTreeNode<T>*rightchild()const{returnvoidsetValue(constT&type){element=type;//析構(gòu)函virtual北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Pagetemplate<class

二叉樹(shù)classThreadBinaryTree{ThreadBinaryTreeNode<T>*root;//根結(jié)點(diǎn)指針ThreadBinaryTree(){root=NULL;};//構(gòu)造函數(shù)virtual~ThreadBinaryTree{DeleteTree(root);};//返回根結(jié)點(diǎn)指ThreadBinaryTreeNode<T>*getroot(){return//中序線索化二叉voidInThread(ThreadBinaryTreeNode<T>*//中序周voidInOrder(ThreadBinaryTreeNode<T>*北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Pagetemplate<classvoid(ThreadBinaryTreeNode<T>*ThreadBinaryTreeNode<T>*if(root==NULL)return;InThread(root->leftchild(),pre);北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Pageif(root->leftchild()==NULL){if(pre)root-}if((pre)&&(pre->rightchild()==NULL)){pre-}InThread(root->rightchild(),}北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Pagetemplate<classvoidThreadBinaryTreeNode<T>*{ThreadBinaryTreeNode<T>* elsepointer=root;//找“最左下”結(jié)點(diǎn),中續(xù)周游的第一個(gè)結(jié)北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page{Visit(pointer->value());//訪問(wèn)當(dāng)前結(jié)點(diǎn) pointer=pointer->rightchild(//按照線索尋找后繼pointer=pointer-while(pointer->lTag==0)//直到子樹(shù)最左葉pointer=pointer->leftchild();//沿左鏈下}//end}//end 北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page穿線樹(shù)的結(jié)點(diǎn)插結(jié)點(diǎn)C的右邊插入結(jié)點(diǎn)F的右邊插入北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page結(jié)點(diǎn)插入算 中序序列里，新結(jié)點(diǎn)插到pointer指的結(jié)新結(jié)點(diǎn)成為pointer指向的結(jié)點(diǎn)的右子樹(shù)的根新結(jié)點(diǎn)的右子樹(shù)是pointer指向的結(jié)點(diǎn)的原來(lái)右子樹(shù)；北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Pagepointer的后繼(右指針) 1若pointer右子樹(shù)不空，則右子樹(shù)的最左結(jié)點(diǎn)的左線索指向newpointer；newpoint的左線索？2若pointer右子樹(shù)為空，則newpoint的右線索繼承pointer的；newpoint的左線索？北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Pagetemplate<classvoidThreadBinaryTree<T>::InsertNode(ThreadBinaryTreeNode<T>*pointer，ThreadBinaryTreeNode<T>*newpointer){ //找point指向結(jié)點(diǎn)if(pointer-北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Pageelseifpointer->rTag==1//右孩子為線索{//右孩子為指temppointer=pointer-while(temppointer-temppointer=temppointer-}//temppointer指針指向pointer結(jié)點(diǎn)的中序后//調(diào)整插入新結(jié)點(diǎn)前的pointer結(jié)點(diǎn)的中序后繼的左線if((temppointer!=NULL)&&(temppointer-北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page//建立新結(jié)點(diǎn)的右pointer-//調(diào)整插入處point結(jié)點(diǎn)的右pointer-//建立新結(jié)點(diǎn)的左newpointer-newpointer-}北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page在前序周游序列中的后繼結(jié)一個(gè)重要事實(shí)：若一個(gè)樹(shù)葉是某子樹(shù)的中序下的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的前序下的最后一個(gè)結(jié)點(diǎn)。北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page中序穿線樹(shù)指定結(jié)在前序周游序列中的后繼結(jié)情況一：指定結(jié)點(diǎn)不是樹(shù)若指定結(jié)點(diǎn)有左子女，則左子女是它的前序后問(wèn)題的解決非常簡(jiǎn)單，不問(wèn)題的解決非常簡(jiǎn)單，不需要線索的幫助指定結(jié)點(diǎn)是樹(shù)葉北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page中序穿線樹(shù)指定結(jié)在前序周游序列中的后繼結(jié)情況二:指定結(jié)點(diǎn)北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page若指定結(jié)點(diǎn)“某結(jié)點(diǎn)x”的左子樹(shù)中按

結(jié)點(diǎn)；則指定結(jié)點(diǎn)沒(méi)有前序后北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page中序穿線樹(shù)指定結(jié)在前序周游序列中的后繼結(jié)情況二：指定結(jié)點(diǎn)是樹(shù)北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page中序穿線樹(shù)指定結(jié)在前序周游序列中的后繼結(jié)情況二：指定結(jié)點(diǎn)是樹(shù) 。北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page中序穿線樹(shù)指定結(jié)在前序周游序列中的后繼結(jié)template<classT>ThreadBinaryTreeNode<T>*ThreadBinaryTree<T>::FindNextinInorderTree(ThreadBinaryTreeNode<T>*{ThreadBinaryTreeNode<T>*//指定結(jié)點(diǎn)有if(pointer-returnpointer->leftchild();elsetemppointer=pointer;北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page中序穿線樹(shù)指定結(jié)在前序周游序列中的后繼結(jié)temppointer=temppointer-return}北京大學(xué)信息學(xué)，轉(zhuǎn)載或翻印必Page穿線樹(shù)總穿線樹(shù)的最大優(yōu)點(diǎn)：有了線索的存在，周游二叉樹(shù)和北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page4.5二叉樹(shù)的實(shí)4.5.1用指針實(shí)現(xiàn)二叉4.5.2空間開(kāi)銷分4.5.3用數(shù)組實(shí)現(xiàn)完全二4.5.4穿線二叉北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page大4.1二叉樹(shù)的概4.2二叉樹(shù)的主要性4.3二叉樹(shù)的抽象數(shù)據(jù)類4.4周游二叉4.5二叉樹(shù)的實(shí)4.6二叉搜索4.7堆與優(yōu)先隊(duì)4.8Huffman編碼北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page二叉搜索樹(shù)圖北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page4.6二叉搜索或者是一顆空樹(shù)點(diǎn)，設(shè)其值為K，則該結(jié)點(diǎn)的左子樹(shù)()的任意一個(gè)結(jié)點(diǎn)的值都小于K；該結(jié)點(diǎn)的右子樹(shù)(若不空)的任意一個(gè)結(jié)點(diǎn)的值都大于或等于K；而且它的左右子樹(shù)也分別為二叉搜索樹(shù)。二叉搜索樹(shù)的性照中序周游將各結(jié)點(diǎn)打印北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page二叉搜索樹(shù)的搜二叉搜索樹(shù)的效率就在于只需檢索二個(gè)從根結(jié)點(diǎn)開(kāi)始，在二叉搜索樹(shù)中檢索值如果根結(jié)點(diǎn)儲(chǔ)存的值為K，則檢索結(jié)束如果K如果K這個(gè)過(guò)程一直持續(xù)到K被找到或者遇上了一個(gè)樹(shù)葉若遇上樹(shù)葉仍沒(méi)發(fā)現(xiàn)K，則K就不在該二叉搜索北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page二叉搜索樹(shù)的插保證插入后仍符合二叉搜索樹(shù)的定子樹(shù)里，再與子樹(shù)的根比較，如此進(jìn)行下去，到把新結(jié)點(diǎn)插入到二

北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 template<classvoidBinarySearchTree<T>::InsertNode(BinaryTreeNode<T>*root,BinaryTreeNode<T>*newpointer){BinaryTreeNode<T>*pointer=NULL;if(root==NULL){}else北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page每次關(guān)鍵碼值比較之后，若小于當(dāng)前結(jié)點(diǎn)的關(guān)鍵碼值若遇到無(wú)左子女的結(jié)點(diǎn)則直接將結(jié)點(diǎn)插入作該結(jié)點(diǎn)的左子女結(jié)點(diǎn)while(1)

否則，pointer將保存隨后進(jìn)入的當(dāng)前結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)指針;且更新pointer//相等則不用插if(newpointer->value()==pointer-returnelseif(newpointer->value()<pointer-{if(pointer->leftchild()==NULL)pointer->left=newpointer//作為左子樹(shù)}elsepointer=pointer-}北京大學(xué)信息學(xué) ，轉(zhuǎn)載或翻印必 Page

每次關(guān)鍵碼值比較之后，若大于當(dāng)前結(jié)點(diǎn)的關(guān)鍵碼值若遇到無(wú)右子女的結(jié)點(diǎn)則直接將結(jié)點(diǎn)插入