c語言二叉樹-文庫吧在線文庫
【正文】 性質(zhì) 5：如果對一棵有 n個結(jié)點的完全二叉樹的結(jié)點按層序編號，則對任一結(jié)點 i(1?i?n)， 有： (1) 如果 i=1， 則結(jié)點 i是二叉樹的根，無雙親；如果 i1， 則其雙親是 ?i/2? (2) 如果 2in， 則結(jié)點 i無左孩子；如果 2i?n， 則其左孩子是 2i (3) 如果 2i+1n， 則結(jié)點 i無右孩子；如果 2i+1?n， 則其右孩子是 2i+1 二叉樹性質(zhì) ? 雙親表示法 –實現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點，每個結(jié)點含兩個域： 187。 JD t[M]。 //指向第一個孩子結(jié)點 }TD。結(jié)點間關(guān)系蘊含在其存儲位置中 187。 ? 已知一棵二叉樹的后根序遍歷序列為 GDEBHFCA，中根序遍歷序列為DGBEAF HC，試畫出該二叉樹 。 struct node *lchild, *rchild。 //t[0]不用 樹的存儲結(jié)構(gòu) a b c d e f h g i 6 0 1 2 3 4 5 7 8 9 a c d e f g h i b data fc 2 3 ^ 4 5 ^ ^ 9 7 8 ^ 6 ^ ^ ^ ^ ^ 如何找雙親結(jié)點 樹的存儲結(jié)構(gòu) ?帶雙親的孩子鏈表 6 1 2 3 4 5 7 8 9 a c d e f g h i b data fc 2 3 4 5 9 7 8 6 ^ ^ ^ ^ ^ ^ ^ ^ ^ 0 1 2 2 3 5 5 5 1 parent a b c d e f h g i 樹的存儲結(jié)構(gòu) ? 孩子兄弟表示法（二叉樹表示法） –實現(xiàn)：用二叉鏈表作樹的存儲結(jié)構(gòu)，鏈表中每個結(jié)點的兩個指針域分別指向其第一個孩子結(jié)點和下一個兄弟結(jié)點 –特點 187。結(jié)點同構(gòu)：結(jié)點的指針個數(shù)相等，為 樹的度 D 187。二叉樹 2 回顧 本次課程內(nèi)容 ?樹的定義及術(shù)語 ?二叉樹的定義及基本概念 (重點 ) ?樹與二叉樹的存儲結(jié)構(gòu) ?樹與二叉樹的遍歷 （重點） 樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu) –定義 ? 定義：樹 (tree)是 n(n0)個結(jié)點的有限集 T， 其中： –有且僅有一個特定的結(jié)點，稱為樹的 根 (root) –當(dāng) n1時，其余結(jié)點可分為 m(m0)個 互不相交 的有限集T1,T2,……Tm， 其中每一個集合本身又是一棵樹，稱為根的子樹 (subtree) ? 特點： –樹中至少有一個結(jié)點 ——根 –樹中各子樹是互不相交的
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1