C++算法之二叉樹的保存和加載

排序二叉樹是我們開發中經常使用到的一種數據結構，它具有較好的插入、刪除、查找特性。但是由于二叉樹的指針較多，所以相比較其他的數據結構而言，二叉樹來得比較麻煩些。但是也不是沒有辦法，下面介紹一下我個人常用的方法。
我們知道，如果一個二叉樹是一個滿樹的話，那么二叉樹的節點應該是按照1、2、3、4依次排開的。但是現實情況是這樣的，由于排序二叉樹自身的特性，某個 分支節點常常可能左半邊有分支，右半邊沒有分支；或者是右半邊有分支，左半邊沒有分支。那么在數據中節點的順序很可能是不連貫的了。
但是，對于某一個節點來說，它的左分支節點、右分支節點和父節點之間還是存在著某種聯系的。比如說，如果父節點的順序是n，那么它的左節點只能是n2， 右邊節點只能是2n+1。那么，我們能不能利用父節點和子節點之間的關系來進行數據的保存呢？答案當然是肯定的。    首先，我們需要對數據結構重新定義一下，其中number記錄序列號：

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);  

}
//該代碼片段來自于: http://www.sharejs.com/codes/cpp/6568</pre>     那么，此時保存的時候放在硬盤里面的數據應該有哪些呢？我們在遍歷每一個節點的時候，只需要把對應的數據和序列號依次放到硬盤即可。
typedef struct _DATA

{

    int data;

    int number;

}DATA;

</pre>     保存的數據總要再次啟用吧？怎么加載呢？很簡單，四個步驟：

         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的節點，那么這個節點就是我們需要尋找的根節點，至此數據就加載完畢。