樹的存儲方式

占用連續的存儲空間，邏輯相鄰存儲位置也相鄰，元素之間的邏輯關系蘊含

雙親存儲

每個節點除資料外還需要一個值來存儲雙親所在位置

struct Tree
{
    typename element;    
    int parent;      
};

占用不一定連續的存儲空間，元素之間的邏輯關系需要附加指針域

孩子鍊存儲

每個節點除資料外還需要一些鍊來指向孩子，由于每個結點的兒子數量可能發生很大變化，浪費太多空間，是以這種方法一般不可行（除了孩子數确定的二叉樹，三叉樹等等，但這樣還是會可能造成浪費）

struct Tree
{
  typename element;
  Tree* children[size];  // 此方法實作難
}；

孩子兄弟鍊存儲

一個指針指向第一個孩子，一個指針指向下一個兄弟姐妹

struct Tree
{
   typename element;
   Tree* firstchild;
   Tree* nextsibling;
}；

二叉樹的存儲方式

順序存儲結構

比如一個節點下标為i，他的左孩子在下标為2 i+1處，右孩子在2i+2（假設數組0位置不存取），假如隻有一個孩子，同樣也需要 “虛的” 建構出來

鍊式存儲結構

每個節點除資料外還需要一些鍊來指向孩子

struct  BTree
{
 ElemType data;
 BTree *LChild;
 BTree *RChild;
};

由括号表示法生産樹

安排根節點

‘（ ’進棧一個元素并準備給他安排左孩子 ‘ ，’進棧一個元素并準備給他安排右孩子 ‘ ）’孩子安排完了出棧遇到字元安排節點以及是Top的哪個孩子
插入

不存在傳回null，存在傳回對象，都不行在左子樹找，假如傳回不是null（說明找到了）傳回他，假如是null，傳回右子樹尋找結果