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

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

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

首先，我們需要對(duì)數(shù)據(jù)結(jié)構(gòu)重新定義一下，其中number記錄序列號(hào)：

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

那么原來(lái)添加數(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í)保存的時(shí)候放在硬盤里面的數(shù)據(jù)應(yīng)該有哪些呢？我們?cè)诒闅v每一個(gè)節(jié)點(diǎn)的時(shí)候，只需要把對(duì)應(yīng)的數(shù)據(jù)和序列號(hào)依次放到硬盤即可。

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

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

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

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

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

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