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

2011-11-02

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】 排序二叉树是我们开发中经常使用到的一种数据结构，它具有较好的插入、删除、查找特性。但是由于二叉树的指针较多，所以...

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】

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的节点，那么这个节点就是我们需要寻找的根节点，至此数据就加载完毕。