大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第五章：樹和二叉樹-第四節(jié)-線索二叉樹

第四節(jié)線索二叉樹一、線索二叉樹的概念1、定義n個結(jié)點的二叉鏈表中含有n+1個空指針域。利用二叉鏈表中的空指針域，存放指向結(jié)點在某種遍歷次序下的前趨和后繼結(jié)點的指針（這種附加的指針稱為"線索"）。這種加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹。根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。2、線索鏈表的結(jié)點結(jié)構(gòu)【例】如圖(a)所示的二叉樹所對應(yīng)的中序線索二叉樹如圖(b)所示，圖(c)所示為二叉線索鏈表樹。3、線索鏈表的結(jié)點類型定義typedefstructnode｛DataTypedata；intltag，rtag；structnode*lchild，*rchild；｝BinThrNode；//線索鏈表結(jié)點類型typedefBinThrNode*BinThrTree；//定義線索鏈表類型二、二叉樹線索化算法1、算法思想按某種次序遍歷二叉樹，在遍歷過程中用線索取代空指針即可.(1)如果根結(jié)點的左孩子指針域為空，則將左線索標(biāo)志域置1，同時給根結(jié)點加左線索。(2)如果根結(jié)點的右孩子指針域為空，則將右線索標(biāo)志域置l，同時給根結(jié)點加右線索。(3)將根結(jié)點指針賦給存放前趨結(jié)點指針的變量，以便當(dāng)訪問下一個結(jié)點時，此根結(jié)點作為前趨結(jié)點。2、二叉鏈表加中序線索的算法算法與中序遍歷算法類似，只是將遍歷算法中訪問根結(jié)點*bt的操作改為在*bt和中序前趨*pre之間建立線索。voidInorderThread(BinThrTreebt){StaticBinThrNode*pre=NULL；//定義指向前趨結(jié)點的指針pre(靜態(tài)變量，只初始化1次)，保存剛訪問過的結(jié)點if(bt!=NULL)//當(dāng)二叉樹為空時結(jié)束遞歸{InorderThread(bt->lchild)；//左子樹線索化if(bt->lchild==NULL)bt->ltag=l；elsebt->ltag=0；if(bt->rchild==NULL)bt->rtag=l；elsebt->rtag=0；if(pre){if(pre->rtag==1)pre->rchild=bt；//給前趨結(jié)點加后繼線索if(bt->ltag==1)bt->lchild=pre；//給當(dāng)前結(jié)點加前趨線索}pre=bt；//將剛訪問過的當(dāng)前結(jié)點置為前趨結(jié)點InorderThread(bt->rchild)；//右子樹線索化}}三、二叉線索鏈表上的運算1、在中序線索二叉樹上查找某結(jié)點*p的后繼結(jié)點【分析】分兩種情況：(1)若結(jié)點*p的rtag域值為1，則表明p->rchild為右線索，它直接指向結(jié)點。(2)若結(jié)點*p的rtag域值為O，則表明p->rchild指向右孩子結(jié)點，結(jié)點*p的中序后繼結(jié)點必是其右子樹第一個中序遍歷到的結(jié)點，因此從結(jié)點*p的右孩子開始，沿左指針鏈向下查找，直到找到一個沒有左孩子(即ltag為1)的結(jié)點為止，該結(jié)點是結(jié)點*p的右子樹中"最左下"的結(jié)點，它就是結(jié)點*p的中序后繼結(jié)點。【算法描述】BinThrNode*InorderNext(BinThrNode*p){//在中序線索二叉樹上求結(jié)點*p的中序后繼結(jié)點if(p->rtag==1)//rchild域為右線索returnp->rchild；//返回中序后繼結(jié)點指針else{p=p->rchild；//從*p的右孩子開始while(p->ltag==O)p=p->lchild；//沿左指針鏈向下查找returnp；}}2、線索二叉樹的中序遍歷算法【基本思想】首先從根結(jié)點起沿左指針鏈向下查找，直到找到一個左線索標(biāo)志為1的結(jié)點止，該結(jié)點的左指針域必為空，它就是整個中序序列中的第一個結(jié)點。訪問該結(jié)點，然后就可以依次找結(jié)點的后繼，直至中序后繼為空時為止?！舅惴枋觥縱oidTinorderThrTree(BinThrThrtreebt){BinThrNode*p；if(bt!=NULL)//二叉樹不空{(diào)p=bt；//使p指向根結(jié)點while(p->ltag==O)//查找出中序遍歷的第一個結(jié)點p=p->lchild；do{printf("%c"，p->data);//輸出訪問結(jié)點值p=InorderNext(p)；//調(diào)用前面的函數(shù)查找結(jié)點*p的中序后繼｝while(p!=NULL)；//當(dāng)p為空時算法結(jié)束}}當(dāng)前講授【真題選解】（例題?單選題）下列所示各圖中是中序線索化二叉樹的是()A.B.C.D.

隱藏答案【答案】A【解析】選項A，b的前驅(qū)是NULL，后繼是a；c的前驅(qū)是a，后繼是空。所以遍歷順序為bac，可見，選項A是中序線索化二叉樹。選項B，b的前驅(qū)是a，后繼是c；c的前驅(qū)是b，