數(shù)據(jù)結(jié)構(gòu)第六章樹和二叉樹(編輯修改稿)
2025-06-19 21:43 本頁面
【文章內(nèi)容簡介】 SqBiTree。 // 二叉樹的順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ? 二叉樹的二叉鏈表存儲(chǔ)表示 ? typedef struct BiTNode { ElemType data。 struct BiTNode *Lchild, *Rchild。// 左、右孩子指針 } *BiTree。 二叉樹的三叉鏈表存儲(chǔ)表示 ? typedef struct TriTNode { ElemType data。 struct BiTNode *Lchild, *Rchild。 //左、右孩子指針 struct BiTNode *parent。 // 雙親指針 } *TriTree。 二叉樹的雙親鏈表存儲(chǔ)表示 ? typedef struct BPTNode { // 結(jié)點(diǎn)結(jié)構(gòu) ElemType data。 int *parent。 // 指向雙親的指針 char LRTag。 // 左、右孩子標(biāo)志域 } BPTNode 第四節(jié) 二叉樹的遍歷 ? “遍歷 ”的含義是對(duì)結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素都訪問一次且僅僅訪問一次。 ? 由于二叉樹中每個(gè)結(jié)點(diǎn)都有兩個(gè)后繼，則可以有三條搜索路徑： 1) 先 左 (子樹 )后 右 (子樹 )； 2) 先 右 (子樹 )后 左 (子樹 )； 3) 按層次從上到下。 先左后右的遍歷 641遍歷 .swf G H D E F B C A 先序序列： ABDGCEFH 中序序列： DGBAECHF 后序序列： GDBEHFCA 先序遍歷遞歸算法 ? void PreOrder(BTree BT) ? { ? if (BT) { Visit(BT)。 ? PreOrder(BTLchild)。 ? PreOrder(BTRchild)。 } ? } ? 中序遍歷遞歸算法 ? void InOrder(BTree BT) ? { ? if (BT) { ? InOrder(BTLchild)。 ? Visit(BT)。 ? InOrder(BTRchild)。 ? } ? } 后序遍歷遞歸算法 ? void PostOrder(BTree BT) ? { ? if (BT) { ? PostOrder(BTLchild)。 ? PostOrder(BTRchild)。 ? Visit(BT)。 ? } ? } 按層次遍歷二叉樹 ? 按層次遍歷該二叉樹的序列為： ? ABCDEFGH G H D E F B C A ? 二叉樹用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示時(shí)，按層遍歷的算法實(shí)現(xiàn) ? （ 1）訪問根結(jié)點(diǎn)，并將根結(jié)點(diǎn)入隊(duì)； ? （ 2）當(dāng)隊(duì)列不空時(shí)，重復(fù)下列操作： ?從隊(duì)列退出一個(gè)結(jié)點(diǎn)； ?若其有左孩子，則訪問左孩子，并將其左孩子入隊(duì)； ?若其有右孩子，則訪問右孩子，并將其右孩子入隊(duì)； G H D E F B C A ? void LevelOrder(BTree *BT) ? { ? if (!BT) exit。 ? InitQueue(Q)。 p=BT。 //初始化 ? Visite(p)。 EnQueue(amp。Q,p)。 ? //訪問根結(jié)點(diǎn)，并將根結(jié)點(diǎn)入隊(duì) ? while (!QueueEmpty(Q)) ? {//當(dāng)隊(duì)非空時(shí)重復(fù)執(zhí)行下列操作 ? DeQueue(amp。Q,amp。p)。 //出隊(duì) ? if (!pLchild) ? { Visite(pLchild) 。 EnQueue(amp。Q,pLchild)。 } //處理左孩子 ? if (!pRchild) ? { Visite(pRchild)。EnQueue(amp。Q,pRchild)。 } //處理右孩子 ? } ? } 建立二叉樹 ? void CreateBiTree(BiTree amp。T) { // 在先序遍歷二叉樹的過程中輸入二叉樹的 先序字符串 ， // 建立根指針為 T的二叉鏈表存儲(chǔ)結(jié)構(gòu)。在先序字符串中， // 字符 39。39。表示空樹，其它字母字符為結(jié)點(diǎn)的數(shù)據(jù)元素 cin ch ； if (ch==39。39。) T=NULL。 // 建空樹 else { T = new BiTNode 。 // 訪問 操作為生成根結(jié)點(diǎn) Tdata = ch。 CreateBiTree(TLchild)。 // 遞歸建 (遍歷 )左子樹 CreateBiTree(TRchild)。 // 遞歸建 (遍歷 )右子樹 } } ? 統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù) ? void CountLeaf (BiTree T, intamp。 count) { // 先序遍歷二叉樹，以 count 返回二叉樹中葉子結(jié)點(diǎn)的數(shù)目 if ( T ) { if ((!TLchild)amp。amp。 (!TRchild)) count++。 // 對(duì)葉子結(jié)點(diǎn)計(jì)數(shù) CountLeaf( TLchild, count)。 CountLeaf( TRchild, count)。
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1