排序二叉樹是我們開發(fā)中經(jīng)常使用到的一種數(shù)據(jù)結構，它具有較好的插入、刪除、查找特性。但是由于二叉樹的指針較多，所以相比較其他的數(shù)據(jù)結構而言，二叉樹來得比較麻煩些。但是也不是沒有辦法，下面介紹一下我個人常用的方法。

我們知道，如果一個二叉樹是一個滿樹的話，那么二叉樹的節(jié)點應該是按照1、2、3、4依次排開的。但是現(xiàn)實情況是這樣的，由于排序二叉樹自身的特性，某個分支節(jié)點常?？赡茏蟀脒呌蟹种?，右半邊沒有分支；或者是右半邊有分支，左半邊沒有分支。那么在數(shù)據(jù)中節(jié)點的順序很可能是不連貫的了。

但是，對于某一個節(jié)點來說，它的左分支節(jié)點、右分支節(jié)點和父節(jié)點之間還是存在著某種聯(lián)系的。比如說，如果父節(jié)點的順序是n，那么它的左節(jié)點只能是n2，右邊節(jié)點只能是2n+1。那么，我們能不能利用父節(jié)點和子節(jié)點之間的關系來進行數(shù)據(jù)的保存呢？答案當然是肯定的。

首先，我們需要對數(shù)據(jù)結構重新定義一下，其中number記錄序列號：

typedef struct _TREE_NODE
{
    int data;
    int number;
    struct _TREE_NODE* left_child;
    struct _TREE_NODE* right_child;
}TREE_NODE;

那么原來添加數(shù)據(jù)的函數(shù)也要做出修改？

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

那么，此時保存的時候放在硬盤里面的數(shù)據(jù)應該有哪些呢？我們在遍歷每一個節(jié)點的時候，只需要把對應的數(shù)據(jù)和序列號依次放到硬盤即可。

typedef struct _DATA
{
    int data;
    int number;
}DATA;

保存的數(shù)據(jù)總要再次啟用吧？怎么加載呢？很簡單，四個步驟：

1）根據(jù)記錄的節(jié)點總數(shù)分配n*sizeof（TREE_NODE）空間；

2）依次從硬盤中取出DATA數(shù)據(jù)，把它們復制給TREE_NODE，暫時left_side和right_side指針為空；

3）對于對于每一個節(jié)點n，尋找它的父節(jié)點n>>1，填充left_side或者是right_side，并且根據(jù)（n%2）是否為1判斷當前節(jié)點是左節(jié)點還是右節(jié)點；

4）獲取n=1的節(jié)點，那么這個節(jié)點就是我們需要尋找的根節(jié)點，至此數(shù)據(jù)就加載完畢。