一步一步写算法（之排序二叉树的保存和加载）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：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的节点，那么这个节点就是我们需要寻找的根节点，至此数据就加载完毕。