樹存儲結構

?

父節點表示法

?

數據域：存放結點本身信息。

雙親域：指示本結點的雙親結點在數組中的位置。

對應的樹：

/* 樹節點的定義 */ #define MAX_TREE_SIZE 100typedef struct{TElemType data;int parent; /* 父節點位置域 */ } PTNode;typedef struct{PTNode nodes[MAX_TREE_SIZE];int n; /* 節點數 */ } PTree;

特點：找雙親容易，找孩子難。

孩子表示法（樹的鏈式存儲結構）

?

childi指向一個結點

可以加上parent。

在有 n 個結點、度為 ?d 的樹的 d 叉鏈表中，有 ?n×(d－1)＋1 個空鏈域

?

我們可以用degree記錄有幾個孩子，省掉空間，但是結點的指針個數不相等，為該結點的度 degree。

?

孩子鏈表：

?

把每個結點的孩子結點排列起來，看成是一個線性表，用單鏈表存儲，則 n 個結點有 n 個孩子鏈表（葉子的孩子鏈表為空表）。而 n 個頭指針又組成一個線性表，用順序表（含 n 個元素的結構數組）存儲。

孩子兄弟表示法（二叉樹表示法）

用二叉鏈表作樹的存儲結構，鏈表中每個結點的兩個指針域分別指向其第一個孩子結點和下一個兄弟結點

typedef struct CSNode{ElemType data;struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree;

?

總結

以上是生活随笔為你收集整理的数据结构课上笔记13的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。