二叉樹的存儲結構?

?

順序存儲結構

?

完全二叉樹：用一組地址連續的 存儲單元依次自上而下、自左至右存 儲結點元素，即將編號為 i ?的結點元 素存儲在一維數組中下標為 i –1 的分量中。

一般二叉樹：將其每個結點與完 全二叉樹上的結點相對照，存儲在一 維數組的相應分量中。

?

最壞情況：樹退化為線性后：

我們要把它“變”成這個大家伙來存了：

深度為 k 的且只 有 k 個結點的右單支樹需要 長度為2^k-1 的一維數組。?

?

鏈式存儲結構

lchild和rchild都是指向相同結構的指針

在 n 個結點的二叉鏈表中有 n + 1 個空指針域。

typedef struct BiTNode { // 結點結構TElemType data;struct BiTNode *lchild,*rchild;// 左右孩子指針
} BiTNode, *BiTree;

可以多一條指向父的指針。

?

遍歷二叉樹

?

順著某一條搜索路徑巡訪二叉樹中的結點，使 ? 得每個結點均被訪問一次，而且僅被訪問一次

?“訪問”的含義很廣，可以是對結點作各種處理， 如：輸出結點的信息、修改結點的數據值等，但要求這種訪問不破壞原來的數據結構。

（所以有些題目比如morris遍歷、鏈表后半段反轉判斷回文等等必須進行完，解題時就算已經得出答案也要遍歷完，因為我們不能改變原來的數據結構。）

?

具體遍歷的介紹

https://blog.csdn.net/hebtu666/article/details/82853988