一步一步写算法（之排序二叉树插入）

 

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

 

 

 

 

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