樹 - 二叉樹 - 二叉樹的存儲結構（二）

　　鏈式存儲結構

　　結點的結構

　　二叉樹的每個結點最多有兩個孩子用鏈接方式存儲二叉樹時每個結點除了存儲結點本身的數據外還應設置兩個指針域

　　lchild和rchild分別指向該結點的左孩子和右孩子結點的結構為

　　

　　結點的類型說明

　　typedef char DataType; //用戶可根據具體應用定義DataType的實際類型

　　typedef struct node{

　　DataType data;

　　Struct node *lchild*rchild; //左右孩子指針

　　}BinTNode; //結點類型

　　typedef BinTNode *BinTree;//BinTree為指向BinTNode類型結點的指針類型

　　二叉鏈表(二叉樹的常用鏈式存儲結構)

　　在一棵二叉樹中所有類型為BinTNode的結點再加上一個指向開始結點(即根結點)的BinTree型頭指針(即根指針)root就構

　　成了二叉樹的鏈式存儲結構並將其稱為二叉鏈表

　　【例】下面左圖所示二叉樹的二叉鏈表如下面中圖所示

　　

　　注意

　　① 一個二叉鏈表由根指針root惟一確定若二叉樹為空則root=NULL;若結點的某個孩子不存在則相應的指針為空

　　② 具有n個結點的二叉鏈表中共有n個指針域其中只有n個用來指示結點的左右孩子其余的n+個指針域為空

　　帶雙親指針的二叉鏈表

　　經常要在二叉樹中尋找某結點的雙親時可在每個結點上再加一個指向其雙親的指針parent形成一個帶雙親指針的二叉鏈表

　　【例】上面右圖是上面左圖所示的二叉樹的帶雙親指針的二叉鏈表

　　注意

　　二叉樹存儲方法的選擇主要依賴於所要實施的各種運算的頻度

From:http://tw.wingwit.com/Article/program/sjjg/201311/23885.html