樹的定義和基本術(shù)語二叉樹binarytree二叉樹的存儲(chǔ)結(jié)(編輯修改稿)
2024-08-15 20:10 本頁面
【文章內(nèi)容簡介】 pl+1)。 else return (depr+1)。 } return 0。 } 遍歷二叉樹的應(yīng)用 求二叉樹結(jié)點(diǎn)個(gè)數(shù) int Size(BiTree T) { if (T==NULL) return 0。 else return 1 + Size (Tlchild ) + Size ( Trchild)。 } 按層次遍歷二叉樹 從根開始逐層訪問，用 FIFO隊(duì)列實(shí)現(xiàn)。 typedef BiTNode* ElemType。 typedef struct{ QElemType *base。 int front,rear。 }SqQueue。 遍歷順序 void LevelOrderTraverse(BiTree T) { BiTree p。 SqQueue Q。 InitQueue(Q)。 if (T){ []=T。 =(+1)%MAXQSIZE。 while ( !=) { p=[]。 printf(%c,pdata)。 =(+1)%MAXQSIZE。 if (plchild) { []=plchild。 =(+1)%MAXQSIZE。} if (prchild) { []=prchild。 =(+1)%MAXQSIZE。} } } } 左右子樹互換 void Exchange(BiTree amp。T) { BiTree S。 if (T) { S=Tlchild。 Tlchild=Trchild。 Trchild=S。 Exchange(Tlchild)。 Exchange(Trchild)。 } } 復(fù)制二叉樹 void CopyTree(BiTree T,BiTree amp。T1) { if (T) { T1=(BiTree)malloc(sizeof(BiTNode))。 if (!T1) { printf(Overflow\n)。 exit(1)。 } T1data=Tdata。 T1lchild=T1rchild=NULL。 CopyTree(Tlchild,T1lchild)。 CopyTree(Trchild,T1rchild)。 } } 線索二叉樹（穿線樹、線索樹） (Threaded Binary Tree) 線索 (Thread): 指向結(jié)點(diǎn)前驅(qū)和后繼的指針 若結(jié)點(diǎn)有左孩子，則 lchild指示其左孩子，否則 lchild中存儲(chǔ)該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針； 若結(jié)點(diǎn)有右孩子，則 rchild指示其右孩子，否則 rchild中存儲(chǔ)指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針 實(shí)質(zhì) ：對(duì)一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化操作，使每個(gè)結(jié)點(diǎn)（除第一和最后一個(gè)外）在這些線性序列中有且僅有一個(gè)直接前驅(qū)和直接后繼。 說明 ：在線索樹中的前驅(qū)和后繼是指按某種次序遍歷所得到的序列中的前驅(qū)和后繼。 概 念 : (p132) 線索鏈表、線索、線索化、線索二叉樹 線索二叉樹及其線索鏈表的表示 標(biāo)志域： ltag = 0, lchild為左孩子指針 ltag = 1, lchild為 前驅(qū)線索 rtag = 0, rchild為右孩子指針 rtag = 1, rchild為 后繼指針 線索二叉樹的存儲(chǔ)表示 p133 typedef enum{Link,Thread}PointerTag。 //Link==0：指針，指向孩子結(jié)點(diǎn) //Thread==1：線索，指向前驅(qū)或后繼結(jié)點(diǎn) typedef struct BiThrNode{ TElemType data。 struct BiThrNode *lchild,*rchild。 PointerTag LTag,RTag。 }BiThrNode, *BiThrTree。 BiThrTree T； 帶表頭結(jié)點(diǎn)的中序穿線鏈表 從遍歷的第一個(gè)結(jié)點(diǎn)來看： 先序序列中第一個(gè)結(jié)點(diǎn)必為根結(jié)點(diǎn) 中、后序序列中第一個(gè)結(jié)點(diǎn)的左孩子定為空 從遍歷的最后一個(gè)結(jié)點(diǎn)來看： 先、中序序列中最后一個(gè)結(jié)點(diǎn)的右孩子必為空 后序序列中最后一個(gè)結(jié)點(diǎn)一定為根結(jié)點(diǎn) 作用： 對(duì)于遍歷操作，線索樹優(yōu)于非線索樹； 遍歷線索樹不用設(shè)棧 步驟： 1)找遍歷的第一個(gè)結(jié)點(diǎn) 2)不斷地找遍歷到的結(jié)點(diǎn)的后繼結(jié)點(diǎn)，直到樹中各結(jié)點(diǎn)都遍歷到為止，結(jié)束。 遍歷線索二叉樹 if (current?RTag ==Thread) 后繼為 current?rchild else //current?RTag ==Link 后繼為當(dāng)前結(jié)點(diǎn)右子樹 的中序下的第一個(gè)結(jié)點(diǎn) 尋找當(dāng)前結(jié)點(diǎn) 在中序下的后繼 A B D E C F H I K G J L 中序后繼線索二叉樹 DBGJEACHLKFI if (current?LTag ==Thread) 前驅(qū)為 current?lchild else //current?LTag ==Link 前驅(qū)為當(dāng)前結(jié)點(diǎn)左子樹的 中序下的最后一個(gè)結(jié)點(diǎn) 尋找當(dāng)前結(jié)點(diǎn) 在中序下的前驅(qū) A B D E C F H I K G J L 中序前驅(qū)線索二叉樹 中序序列： DBGJEACHLKFI 遍歷中序線索二叉樹 (不帶頭結(jié)點(diǎn)） void inorder1_Thr(BiThrTree T) { BiThrTree p=T。 while (pLTag==Link) p=plchild。 printf(%c,pdata)。 while (prchild) { if (pRTag==Link) { p=prchild。 while(pLTag==Link) p=plchild。} else p=prchild。 printf(%c,pdata)。 } } void inorder2_Thr(BiThrTree T){ BiThrTree p=T。 while (p){ while (pLTag==Link) p=plchild。 printf(%c,pdata)。 while (pRTag==Thread amp。amp。 prchild){ p=prchild。 printf(%c,pdata)。} p=prchild。 } } A B D E C F H I K G J L A B D E C F H I K G J L 先序線索二叉樹 ABDEGJCFHKLI 后序線索二叉樹 DJGEBLKHIFCA 先序線索二叉樹 在先序線索二叉樹中 尋找當(dāng)前結(jié)點(diǎn)的后繼與前驅(qū) 遍歷先序線索二叉樹 (不帶頭結(jié)點(diǎn)） void preorder_Thr(BiThrTree T) { BiThrTree p=T。 printf(%c,pdata)。 while (prchild) { if (pLTag==Link) p=plchild。 else p=prchild。 printf(%c,pdata)。 } } 后序線索二叉樹 在后序線索化二叉樹中 尋找當(dāng)前結(jié)點(diǎn)的后繼 遍歷后序線索二叉樹 (不帶頭結(jié)點(diǎn)） void postorder_Thr(TriThrTree T) { TriThrTree f,p=T。 do { while (pLTag==Link) p=plchild。 if (pRTag==Link) p=prchild。 } while (pLTag!=Thread || pTag!=Thread)。 printf(%c,pdata)。 while (p!=T) { if (pRTag==Link) { f=pparent。 if (fRTag==Thread || p==
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1