二叉樹的存儲結(jié)構(gòu)

   由于二叉樹是一種特殊的樹，這種特殊的樹，采用順序存儲結(jié)構(gòu)就可以實現(xiàn)。既然是順序存儲結(jié)構(gòu)，必然的是通過數(shù)組來實現(xiàn)了。

   有一種極端情況，就是深度為k的右斜樹，只有k個結(jié)點，如果想要存儲它，就要將它轉(zhuǎn)換為二叉樹，那么必然的需要2^k-1個結(jié)點，這么多結(jié)點中，只有k個結(jié)點是有效數(shù)據(jù)，所以，會造成空間的浪費。所以，順序存儲結(jié)構(gòu)只適用于完全二叉樹。

   那么，對于那種類似于極端情況的樹，該如何存儲呢?顯然，順序存儲并不適合它。那么，可以考慮采用鏈?zhǔn)酱鎯?。也就是二叉鏈表。因為，二叉樹每個結(jié)點最多有兩個孩子，所以，在設(shè)計結(jié)構(gòu)時，有一個變量用來存放數(shù)據(jù)，還有兩個指針變量指向左孩子和右孩子。結(jié)構(gòu)定義如下：

typedef struct BiNode{

    TElemType data;
    struct BiTNode *lchild, *rchild;

}BiTNode, *BiTree;