ANSI C中樹數據結構C

Question

如何在ANSI C（*）中實現樹？ （*）我是指樹（不是二叉樹）的最一般的定義。

Answer 1

最好的實現方法（並且有很多）可能取決於特定的應用程序。例如，將數組中的子節點或子指針存儲在某些應用程序中可能更可取，而在其他應用程序中則完全沒有必要。你真的需要基於索引的隨機訪問給孩子嗎？如果是這樣，請使用數組。

一個經典的非陣列的方法來實現的任意的樹是存儲在每個節點中兩個指針：一個指針，指向拳頭子和一個指針到下一個同級。

struct Element 
{ 
    ... 
    struct Element *p_first_child; 
    struct Element *p_next_sibling; 
}; 

即，每個節點實質上包含一個指向其子女的列表的指針。

例如，有3個孩子的節點通過以下聯結構

Node 
    | 
    (first child) 
    | 
    V 
    Child1 --(next sibling)--> Child2 --(next sibling)--> Child3 

該實現可以存儲任何由樹中的每個節點僅使用兩個指針來表示。不需要額外的數組。由於子節點存儲在列表中，因此只能按順序訪問它們。

從這種方法中下面的有趣的觀察是，所得的數據結構可被認爲是一二進制樹，即任意的樹可以由等效二叉樹來表示。

Answer 2

你做執行元件結構不錯，但嘗試使用二叉樹或B樹來避免動態分配/釋放。你

也將提供一組函數來插入/刪除/初始化/搜索/排序/枚舉樹。

你能拿出像AddToMyBTree（指針樹頭，新元素）的名稱

，你能拿出比一般的操作更多的功能，如果你想。

我想我誤解你的問題： 如果要列舉你肯定會使用遞歸樹中的元素，你也將需要中斷與空對象的子元素列表，或與孩子們指望添加額外的元素。

ProcessNode(element* pElement) 
{ 
    element* pChild = pElement.pChildElements; 

    // process the element here 


    // then begin to process the child elements. 
    while (pChild) 
    { 
     ProcessNode(pChild); 
     pChild++; 
    } 
} 

請記住，您可以傳遞指向處理元素的函數的指針，以便此枚舉器對於您的樹可以是通用的。