c語言二叉樹(專業版)

　　

【正文】 浪費空間，適于存滿二叉樹和完全二叉樹 a b c d e f g a b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11 二叉樹的存儲結構 ? 鏈式 存儲結構 –二叉鏈表 typedef struct node { datatype data。 樹的存儲結構 a b c d e f h g i a c d e f g h i b 0 1 2 2 3 5 5 5 1 0 9 6 0 1 2 3 4 5 7 8 9 data parent 0號單元不用或 存結點個數 如何找孩子結點 樹的存儲結構 ? 孩子表示法 –多重鏈表：每個結點有多個指針域，分別指向其子樹的根 187。結點同構：結點的指針個數相等，為 樹的度 D 187。 struct node *lchild, *rchild。結點間關系蘊含在其存儲位置中 187。 JD t[M]。結點不同構：結點指針個數不等，為該結點的度 d data child1 child2 ………. childD data degree child1 child2 ………. childd ?孩子鏈表：每個結點的孩子結點用單鏈表存儲，再用含 n個元素的結構數組指向每個孩子鏈表 孩子結點： typedef struct node { int child。 }JD。 a b c d e f h g i a b c d e f g h i ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 樹的存儲結構 ? 順序 存儲結構 –實現：按滿二叉樹的結點層次編號，依次存放二叉樹中的數據元素 –特點： 187。 }JD。 //該結點在表頭數組中下標 struct node *next。 lchild data rchild A B C D E F G 在 n個結點的二叉鏈表中，有 n+1個空指針域 A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ 二叉樹的存儲結構 ? 三叉鏈表 typedef struct node { datatype data。 }JD。 int