【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
排序二叉樹是我們開發中經常使用到的一種數據結構，它具有較好的插入、刪除、查找特性。但是由於二叉樹的指針較多，所以相比較其他的數據結構而言，二叉樹來得比較麻煩些。但是也不是沒有辦法，下面介紹一下我個人常用的方法。
我們知道，如果一個二叉樹是一個滿樹的話，那麼二叉樹的節點應該是按照1、2、3、4依次排開的。但是現實情況是這樣的，由於排序二叉樹自身的特性，某個分支節點常常可能左半邊有分支，右半邊沒有分支；或者是右半邊有分支，左半邊沒有分支。那麼在數據中節點的順序很可能是不連貫的了。
但是，對於某一個節點來說，它的左分支節點、右分支節點和父節點之間還是存在著某種聯系的。比如說，如果父節點的順序是n，那麼它的左節點只能是n*2，右邊節點只能是2*n+1。那麼，我們能不能利用父節點和子節點之間的關系來進行數據的保存呢？答案當然是肯定的。
首先，我們需要對數據結構重新定義一下，其中number記錄序列號：
typedef struct _TREE_NODE
{
int data;
int number;
struct _TREE_NODE* left_child;
struct _TREE_NODE* right_child;
}TREE_NODE;
typedef struct _TREE_NODE
{
int data;
int number;
struct _TREE_NODE* left_child;
struct _TREE_NODE* right_child;
}TREE_NODE; 那麼原來添加數據的函數也要做出修改？
STATUS _insert_node_into_tree(TREE_NODE* pTreeNode, int data)
{
TREE_NODE* pNode;
while(1){
if(data < pTreeNode->data){
if(NULL == pTreeNode->left_child){
pNode = create_tree_node(data);
assert(NULL != pNode);
pNode->number = pTreeNode->number << 1;
pTreeNode->left_child = pNode;
break;
}else
pTreeNode = pTreeNode->left_child;
}else{
if(NULL == pTreeNode->right_child){
pNode = create_tree_node(data);
assert(NULL != pNode);
pNode->number = pTreeNode->number << 1 + 1;
pTreeNode->right_child = pNode;
break;
}else
pTreeNode = pTreeNode->right_child;
}
}
return TRUE;
}
STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)
{
if(NULL == ppTreeNode)
return FALSE;
if(NULL == *ppTreeNode){
*ppTreeNode = (TREE_NODE*)create_tree_node(data);
assert(NULL != *ppTreeNode);
(*ppTreeNode)->number = 1;
return TRUE;
}
return _insert_node_into_tree(*ppTreeNode, data);
}
STATUS _insert_node_into_tree(TREE_NODE* pTreeNode, int data)
{
TREE_NODE* pNode;
while(1){
if(data < pTreeNode->data){
if(NULL == pTreeNode->left_child){
pNode = create_tree_node(data);
assert(NULL != pNode);
pNode->number = pTreeNode->number << 1;
pTreeNode->left_child = pNode;
break;
}else
pTreeNode = pTreeNode->left_child;
}else{
if(NULL == pTreeNode->right_child){
pNode = create_tree_node(data);
assert(NULL != pNode);
pNode->number = pTreeNode->number << 1 + 1;
pTreeNode->right_child = pNode;
break;
}else
pTreeNode = pTreeNode->right_child;
}
}
return TRUE;
}
STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)
{
if(NULL == ppTreeNode)
return FALSE;
if(NULL == *ppTreeNode){
*ppTreeNode = (TREE_NODE*)create_tree_node(data);
assert(NULL != *ppTreeNode);
(*ppTreeNode)->number = 1;
return TRUE;
}
return _insert_node_into_tree(*ppTreeNode, data);
} 那麼，此時保存的時候放在硬盤裡面的數據應該有哪些呢？我們在遍歷每一個節點的時候，只需要把對應的數據和序列號依次放到硬盤即可。
typedef struct _DATA
{
int data;
int number;
}DATA;
typedef struct _DATA
{
int data;
int number;
}DATA;
保存的數據總要再次啟用吧？怎麼加載呢？很簡單，四個步驟：
1）根據記錄的節點總數分配n*sizeof（TREE_NODE）空間；
2）依次從硬盤中取出DATA數據，把它們復制給TREE_NODE，暫時left_side和right_side指針為空；
3）對於對於每一個節點n，尋找它的父節點n>>1，填充left_side或者是right_side，並且根據（n%2）是否為1判斷當前節點是左節點還是右節點；
4）獲取n=1的節點，那麼這個節點就是我們需要尋找的根節點，至此數據就加載完畢。
