一步一步写算法（之排序二叉树插入）
【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】
二叉树的节点插入比较简单。一般来说，二叉树的插入主要分为以下两个步骤：
1） 对当前的参数进行判断，因为需要考虑到头结点，所以我们使用了指针的指针作为函数的输入参数
2） 分情况讨论：
如果原来二叉树连根节点都没有，那么这个新插入的数据就是根节点；
如果原来的二叉树有根节点，那我们判断这个数据是否存在过，如果存在，那么返回；如果不存在，那么继续插入数据。
那继续插入的数据怎么保存呢？又要分三种情况：
1）如果插入的数据小于当前节点的数据，那么往当前节点的左子树方向继续寻找插入位置
2）如果插入的数据大于当前插入的位置，那么往当前节点的右子树方向继续寻找插入位置
3）如果方向当前的节点为空，那么表示插入的位置找到了，插入数据即可
算法说了这么多，下面即开始练习我们的代码：
a）判断输入数据的合法性
STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)
{
if(NULL == ppTreeNode)
return FALSE;
return TRUE;
}
STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)
{
if(NULL == ppTreeNode)
return FALSE;
return TRUE;
} 此时，可以用一个测试用例验证一下
static void test1()
{
assert(FALSE == insert_node_into_tree(NULL, 10));
}
static void test1()
{
assert(FALSE == insert_node_into_tree(NULL, 10));
}
b）判断当前根节点是否存在，修改代码
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);
return TRUE;
}
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);
return TRUE;
}
return TRUE;
} 修改了代码，少不了测试用例的添加。
static void test2()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(10 == pTreeNode->data);
free(pTreeNode);
}
static void test2()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(10 == pTreeNode->data);
free(pTreeNode);
}
c）上面考虑了没有根节点的情况，那么如果根节点存在呢？
STATUS _insert_node_into_tree(TREE_NODE** ppTreeNode, int data, TREE_NODE* pParent)
{
if(NULL == *ppTreeNode){
*ppTreeNode = create_tree_node(data);
assert(NULL != *ppTreeNode);
(*ppTreeNode)->parent = pParent;
return TRUE;
}
if(data < (*ppTreeNode)->data)
return _insert_node_into_tree(&(*ppTreeNode)->left_child, data, *ppTreeNode);
else
return _insert_node_into_tree(&(*ppTreeNode)->right_child, data, *ppTreeNode);
}
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);
return TRUE;
}
return _insert_node_into_tree(ppTreeNode, data, NULL);
}
STATUS _insert_node_into_tree(TREE_NODE** ppTreeNode, int data, TREE_NODE* pParent)
{
if(NULL == *ppTreeNode){
*ppTreeNode = create_tree_node(data);
assert(NULL != *ppTreeNode);
(*ppTreeNode)->parent = pParent;
return TRUE;
}
if(data < (*ppTreeNode)->data)
return _insert_node_into_tree(&(*ppTreeNode)->left_child, data, *ppTreeNode);
else
&n
补充：软件开发 , C语言 ,
