c語言二叉樹-wenkub
2022-09-01 23:17:45 本頁面
【正文】 ?二叉樹的定義及相關(guān)的 5個(gè)特性 ?樹 4種存儲結(jié)構(gòu)與二叉樹的 3種存儲結(jié)構(gòu) ?樹與二叉樹的前序 ,中序 ,后序 ,層次遍歷 作業(yè) ? 已知一棵二叉樹的先根序遍歷序列為 ABDGCEHF，中根序遍歷序列為BGDAEH CF，試畫出該二叉樹。 }JD。 a b c d e f h g i a b c d e f g h i ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 樹的存儲結(jié)構(gòu) ? 順序 存儲結(jié)構(gòu) –實(shí)現(xiàn)：按滿二叉樹的結(jié)點(diǎn)層次編號，依次存放二叉樹中的數(shù)據(jù)元素 –特點(diǎn)： 187。操作容易 187。 //數(shù)據(jù)域 struct node *fc。結(jié)點(diǎn)不同構(gòu)：結(jié)點(diǎn)指針個(gè)數(shù)不等，為該結(jié)點(diǎn)的度 d data child1 child2 ………. childD data degree child1 child2 ………. childd ?孩子鏈表：每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表存儲，再用含 n個(gè)元素的結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈表 孩子結(jié)點(diǎn)： typedef struct node { int child。 }JD。性質(zhì) 5：如果對一棵有 n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號，則對任一結(jié)點(diǎn) i(1?i?n)， 有： (1) 如果 i=1， 則結(jié)點(diǎn) i是二叉樹的根，無雙親；如果 i1， 則其雙親是 ?i/2? (2) 如果 2in， 則結(jié)點(diǎn) i無左孩子；如果 2i?n， 則其左孩子是 2i (3) 如果 2i+1n， 則結(jié)點(diǎn) i無右孩子；如果 2i+1?n， 則其右孩子是 2i+1 二叉樹性質(zhì) ? 雙親表示法 –實(shí)現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域： 187。數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息 187。 JD t[M]。 //該結(jié)點(diǎn)在表頭數(shù)組中下標(biāo) struct node *next。 //指向第一個(gè)孩子結(jié)點(diǎn) }TD。破壞了樹的層次 typedef struct node { datatype data。結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲位置中 187。 lchild data rchild A B C D E F G 在 n個(gè)結(jié)點(diǎn)的二叉鏈表中，有 n+1個(gè)空指針域 A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ 二叉樹的存儲結(jié)構(gòu) ? 三叉鏈表 typedef struct n
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1