數(shù)據(jù)結(jié)構(gòu)-二叉樹的存儲(chǔ)結(jié)構(gòu)和遍歷-文庫吧資料
2024-08-18 06:29本頁面
【正文】 nt Depth (BiTree T ){// 返回二叉樹的深度 } if ( !T ) return (0)。 n = CountNode( Trchild)。 } { 遞歸思想 : 如果是空樹，返回 0 統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù) 求出左子樹的結(jié)點(diǎn)的個(gè)數(shù) m 求出右子樹的結(jié)點(diǎn)的個(gè)數(shù) n 返回 m+n+1 統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù) int CountNode (BiTree T){ //返回指針 T所指二叉樹中所有葉子結(jié)點(diǎn)個(gè)數(shù) } if (!T ) return 0。 main() PreOrder(T)。 // 遍歷左子樹 4 Preorder(Trchild, visit)。 2 visit(Tdata)。 void Preorder (BiTree T,void( *visit)(TElemTypeamp。 Preorder( Tlchild)。 由前序序列和中序序列，或者后序和中序序列可以唯一確定一顆二叉樹 A B C D E F G H K 先序序列： 中序序列： 后序序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A 三種遍歷的比較 復(fù)制二叉樹 建立二叉樹 查詢二叉樹中某個(gè)結(jié)點(diǎn) 應(yīng)用舉例 統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù) 遍歷訪問了每個(gè)結(jié)點(diǎn)一次且僅一次 設(shè)置一個(gè)全局變量 count=0 統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù) 將 visit改為 :count++ 統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù) void PreOrder (BiTree T){ } if (! T ) return。 // 訪問結(jié)點(diǎn) } 后序遍歷 課堂練習(xí) 寫出三種遍歷的結(jié)果 A B E C D A B C D E F G H K 先序序列： 中序序列： 后序序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A 三種遍歷的比較 如果不考慮 visit，三種遍歷的算法在結(jié)構(gòu)上是一樣的，因此，壓棧和出棧的過程相同。 // 遍歷左子樹 3 Postorder(Trchild, visit)。 e)) { // 后序遍歷二叉樹 1 if (!T) return。 // 遍歷右子樹 } 后序（根）遍歷 左 子樹 右 子樹 根 根左 子樹 右 子樹 若二叉樹為空樹，則空操作；否則， （ 1）后序遍歷左子樹； （ 2）后序遍歷右子樹； （ 3）訪問根結(jié)點(diǎn)。 // 遍歷左子樹 3 visit(Tdata)。 e)) { // 中序遍歷 二叉樹 1 if (!T) return。 // 遍歷左子樹 4 Preorder(Trchild, visit)。 2 visit(Tdata)。 ? DRL， RDL， RLD 先序（根）遍歷 左 子樹 右 子樹 根 根左 子樹 右 子樹 若二叉樹為空樹，則空操作；否則， （ 1）訪問根結(jié)點(diǎn) （ 2）先序遍歷左子樹 （ 3）先序遍歷右子樹 先序（根）遍歷 A B C D E F
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1