首页 > 程序开发 > 软件开发 > C语言 >

一步一步写算法(之排序二叉树插入)

2011-10-26

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】 二叉树的节点插入比较简单。一般来说,二叉树的插入主要分为以下两个步骤: 1) 对当前的参数进行判断,因为需要考虑...

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

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);

}

上面的代码已经考虑了不是根节点的情况。我们可以据此添加一个测试用例。

static void test3()

{

TREE_NODE* pTreeNode = NULL;

assert(TRUE == insert_node_into_tree(&pTreeNode, 9));

assert(TRUE == insert_node_into_tree(&pTreeNode, 8));

assert(TRUE == insert_node_into_tree(&pTreeNode, 10));

assert(9 == pTreeNode->data);

assert(8 == pTreeNode->left_child->data);

assert(10 == pTreeNode->right_child->data);

free(pTreeNode->left_child);

free(pTreeNode->right_child);

free(pTreeNode);

}

static void test3()

{

TREE_NODE* pTreeNode = NULL;

assert(TRUE == insert_node_into_tree(&pTreeNode, 9));

assert(TRUE == insert_node_into_tree(&pTreeNode, 8));

assert(TRUE == insert_node_into_tree(&pTreeNode, 10));

assert(9 == pTreeNode->data);

assert(8 == pTreeNode->left_child->data);

assert(10 == pTreeNode->right_child->data);

free(pTreeNode->left_child);

free(pTreeNode->right_child);

free(pTreeNode);

} 由于上面的代码是递归代码,为了实现代码的健壮性和完毕性,其实我们设计测试用例的时候应该至少包括9个测试用例:

(1) 参数非法

(2) 根节点不存在

(3)根节点存在,但是插入的数据已经存在

(4)根节点存在,插入数据为9,8

(5)根节点存在, 插入数据为9,10

(6)根节点存在,插入数据为9,8,7

(7)根节点存在,插入数据为9,7,8

(8)根节点存在,插入数据为7,8,9

(9)根节点存在,插入数据为7,9,8

【预告: 下面一篇博客主要介绍二叉树的节点删除】

相关文章
最新文章
热点推荐