數(shù)據(jù)結(jié)構(gòu)第6章B-chapterb課件

第6章樹和二叉樹（Tree&BinaryTree）6.1樹的基本概念6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5赫夫曼樹及其應(yīng)用16.3遍歷二叉樹和線索二叉樹一、遍歷二叉樹（TraversingBinaryTree）遍歷定義——指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)（又稱周游）。遍歷用途——它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。

遍歷方法——牢記一種約定，對每個(gè)結(jié)點(diǎn)的查看都是“先左后右”。2遍歷規(guī)則———二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、

L、RD、L、R的組合定義了六種可能的遍歷方案：LDR,LRD,DLR,DRL,RDL,RLD若限定先左后右，則有三種實(shí)現(xiàn)方案：

DLRLDRLRD先(根)序遍歷中(根)序遍歷后(根)序遍歷

注：“先、中、后”的意思是指訪問的結(jié)點(diǎn)D是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。3+*A*/EDCB先序遍歷+**/ABCDE前綴表示中序遍歷A/B*C*D+E中綴表示后序遍歷AB/C*D*E+后綴表示層序遍歷+*E*D/CAB例2：用二叉樹表示算術(shù)表達(dá)式5遍歷的算法實(shí)現(xiàn)：用遞歸形式格外簡單！回憶1：二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義：typedefstructnode*tree_pointer;typedefstructnode{intdata;tree_pointerleft_child,right_child;}node;則三種遍歷算法可寫出:longintfact(n)//求n!intn;{longf;if(n>1)f=n*fact(n-1);elsef=1;return(f);}6先序遍歷算法DLR(leizi*root){if(root!=NULL)//非空二叉樹

{printf(“%d”,root->data);//訪問DDLR(root->lchild);//遞歸遍歷左子樹DLR(root->rchild);//遞歸遍歷右子樹}return(0);}中序遍歷算法LDR(leizi*root){if(root!=NULL){LDR(root->lchild);printf(“%d”,root->data);

LDR(root->rchild);}return(0);}后序遍歷算法LRD(leizi*root){if(root!=NULL)

{LRD(root->lchild);LRD(root->rchild);printf(“%d”,root->data);}return(0);}結(jié)點(diǎn)數(shù)據(jù)類型自定義typedefstructleizi{intdata;structleizi*lchild,*rchild；}leizi;leizi*root;

7對遍歷的分析：1.從前面的三種遍歷算法可以知道：如果將print語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時(shí)機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個(gè)結(jié)點(diǎn)經(jīng)過3次。AFEDCBG第1次經(jīng)過時(shí)訪問＝先序遍歷第2次經(jīng)過時(shí)訪問＝中序遍歷第3次經(jīng)過時(shí)訪問＝后序遍歷2.二叉樹遍歷的時(shí)間效率和空間效率時(shí)間效率:O(n)

//每個(gè)結(jié)點(diǎn)只訪問一次空間效率:O(n)

//棧占用的最大輔助空間（精確值：樹深為k的遞歸遍歷需要k+1個(gè)輔助單元?。?注：要實(shí)現(xiàn)遍歷運(yùn)算必須先把二叉樹存入機(jī)內(nèi)。思路：利用前序遍歷來建樹

（結(jié)點(diǎn)值陸續(xù)從鍵盤輸入，用DLR為宜）BintreecreateBTpre(){BintreeT;charch;scanf(“%c”,&ch);if(ch==’’)T=NULL;else{T=(Bintree)malloc(sizeof(BinTNode));T->data=ch;T->lchild=createBTpre();T->rchild=createBTpre();}returnT;}怎樣建樹？見教材P131程序。103中序遍歷的非遞歸(迭代)算法算法思路：若不用遞歸，則要實(shí)現(xiàn)二叉樹遍歷的“嵌套”規(guī)則，必用堆棧。可直接用while語句和push/pop操作。參見教材P130-131程序。4.判別給定二叉樹是否為完全二叉樹（即順序二叉樹）。

算法思路：完全二叉樹的特點(diǎn)是：沒有左子樹空而右子樹單獨(dú)存在的情況(前k-1層都是滿的，且第k層左邊也滿）。技巧:按層序遍歷方式，先把所有結(jié)點(diǎn)（不管當(dāng)前結(jié)點(diǎn)是否有左右孩子）都入隊(duì)列.若為完全二叉樹,則層序遍歷時(shí)得到的肯定是一個(gè)連續(xù)的不包含空指針的序列.如果序列中出現(xiàn)了空指針，則說明不是完全二叉樹。12中序遍歷：BDCEAFHG

后序遍歷：DECBHGFA（BDCE）（FHG）ABF（DCE）（HG）CDEGHABBFF14問：用二叉鏈表法（l_child,r_child）存儲包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的指針區(qū)域中會有多少個(gè)空指針？分析：用二叉鏈表存儲包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)必有2n個(gè)鏈域（見二叉鏈表數(shù)據(jù)類型說明）。 除根結(jié)點(diǎn)外，二叉樹中每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親（直接前驅(qū)），所以只會有n－1個(gè)結(jié)點(diǎn)的鏈域存放指針，指向非空子女結(jié)點(diǎn)（即直接后繼）。思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？——我們可以用它來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索，以加快查找速度。所以，空指針數(shù)目＝2n－(n-1)=n+1個(gè)。n+115二、線索二叉樹（ThreadedBinaryTree）普通二叉樹只能找到結(jié)點(diǎn)的左右孩子信息，而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。若將遍歷后對應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來，則從第一個(gè)結(jié)點(diǎn)開始就能很快“順藤摸瓜”而遍歷整個(gè)樹了。兩種解決方法增加兩個(gè)域：fwd和bwd；利用空鏈域（n+1個(gè)空鏈域）存放前驅(qū)指針存放后繼指針如何預(yù)存這類信息？例如中序遍歷結(jié)果：BDCEAFHG，實(shí)際上已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！可能是根、或最左（右）葉子16規(guī)定：1）若結(jié)點(diǎn)有左子樹，則lchild指向其左孩子；否則，lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點(diǎn)有右子樹，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)。為了避免混淆，增加兩個(gè)標(biāo)志域，如下圖所示：lchildLTagdataRTagrchild約定:當(dāng)Tag域?yàn)?時(shí),表示正常情況;當(dāng)Tag域?yàn)?時(shí),表示線索情況.17有關(guān)線索二叉樹的幾個(gè)術(shù)語：線索鏈表：用前頁結(jié)點(diǎn)結(jié)構(gòu)所構(gòu)成的二叉鏈表線索：指向結(jié)點(diǎn)前驅(qū)和后繼的指針線索二叉樹：加上線索的二叉樹（圖形式樣）線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程注：在線索化二叉樹中，并不是每個(gè)結(jié)點(diǎn)都能直接找到其后繼的，當(dāng)標(biāo)志為0時(shí)，則需要通過一定運(yùn)算才能找到它的后繼。18ABCGEIDHFroot懸空？懸空？解：該二叉樹中序遍歷結(jié)果為:

H,D,I,B,E,A,F,C,G所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：例2：畫出以下二叉樹對應(yīng)的中序線索二叉樹。為避免懸空態(tài)，應(yīng)增設(shè)一個(gè)頭結(jié)點(diǎn)20對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為:H,D,I,B,E,A,F,C,G0--root021voiditer_inorder(tree_pointernode){inttop=-1;/*initializestack*/tree_pointerstack[MAX_STACK_SIZE];for(;;){for(;node;node=node->left_child)add(&top,node);/*addtostack*/node=delete(&top);/*deletefromstack*/if(!node)break;/*emptystack*/printf(“%D”,node->data);node=node->right_child;}}時(shí)間復(fù)雜度O(n)附：中序遍歷迭代算法(利用堆棧)23voidlevel_order(tree_pointerptr)/*levelordertreetra