【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：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)