數(shù)據(jù)結(jié)構(gòu)-二叉樹的存儲(chǔ)結(jié)構(gòu)和遍歷-預(yù)覽頁
【正文】 / 二叉樹的最大結(jié)點(diǎn)數(shù) typedef struct{ TElemType data[MAX_TREE_SIZE]。 // 1號(hào)單元存儲(chǔ)根結(jié)點(diǎn) SqBiTree bt。 二叉樹的順序存儲(chǔ) 適用于一般的二叉樹 鏈?zhǔn)酱鎯?chǔ) — 二叉鏈表 lchild data rchild 二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu) : 左指針域，指向當(dāng)前結(jié)點(diǎn)的左子樹 數(shù)據(jù)域，存儲(chǔ)當(dāng)前結(jié)點(diǎn)的取值信息 右指針域，指向當(dāng)前結(jié)點(diǎn)的右子樹 指向二叉樹根結(jié)點(diǎn) 頭指針： 前述二叉樹的二叉鏈表如下所示： A F ∧ ∧ E ∧ C ∧ D ∧ ∧ B ∧ root 鏈?zhǔn)酱鎯?chǔ) — 二叉鏈表 a1 a2 a3 L A B D C E F 1 2 5 3 7 14 typedef struct BiTNode { // 結(jié)點(diǎn)結(jié)構(gòu) TElemType data。 struct TriTNode *lchild, *rchild。 問題的提出 定義： 順著某一條搜索路徑巡訪二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。 問題的提出 二叉樹存在下述三條搜索路徑： ? 1． 先上后下 的按層次遍歷； ? 2． 先左 （ 子樹 ） 后右 （ 子樹 ） 的遍歷； ? DLR， LDR， LRD ? 3． 先右 （ 子樹 ） 后左 （ 子樹 ） 的遍歷 。 // 訪問根結(jié)點(diǎn) 3 Preorder(Tlchild, visit)。 2 Inorder(Tlchild, visit)。 后序（根）遍歷 A B C D E F G H K A D C B H K G F E void Postorder (BiTree T, void( *visit)(TElemTypeamp。 // 遍歷右子樹 4 visit(Tdata)。 count++。 e)) { // 先序遍歷二叉樹 1 if (!T) return。// 遍歷右子樹 } 統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù) int count=0。//空樹 m = CountNode( Tlchild)。 depthLeft = Depth( Tlchild )。 查詢二叉樹中的某個(gè)結(jié)點(diǎn) 給定指向二叉樹的根結(jié)點(diǎn)的指針 T和 x，在 T中查找數(shù)據(jù)元素的值等于 x的結(jié)點(diǎn)，如果找到，則返回一個(gè)指針，指向這個(gè)結(jié)點(diǎn)，否則，返回空指針。 p=Search(Tlchild, x)。 pr = Copy(Trchild)。 } 以下列字符串表示 AB C D 建立二叉樹 以字符串的形式“根左子樹右子樹”定義一棵二叉樹 以空白字符“ ”表示 1）空樹 2）只含一個(gè)根結(jié)點(diǎn)的二叉樹 A 以字符串“ A ”表示 A B C D 3） 建立二叉樹 A B C D B A T B C D ^ ^ ^ ^ ^ 建立二叉樹 Status CreateBiTree(BiTree amp。 // 生成根結(jié)點(diǎn) return OK。) T = NULL。 BiNodeT *p = new BiNodeT。}。 pdata = pre[prepos]。 }
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1