c++(排序二叉树插入)

     二叉树的节点插入比较简单。一般来说，二叉树的插入主要分为以下两个步骤：

    1） 对当前的参数进行判断，因为需要考虑到头结点，所以我们使用了指针的指针作为函数的输入参数

    2） 分情况讨论：

        如果原来二叉树连根节点都没有，那么这个新插入的数据就是根节点；

        如果原来的二叉树有根节点，那我们判断这个数据是否存在过，如果存在，那么返回；如果不存在，那么继续插入数据。

        那继续插入的数据怎么保存呢？又要分三种情况：

             1）如果插入的数据小于当前节点的数据，那么往当前节点的左子树方向继续寻找插入位置

             2）如果插入的数据大于当前插入的位置，那么往当前节点的右子树方向继续寻找插入位置

             3）如果方向当前的节点为空，那么表示插入的位置找到了，插入数据即可

    算法说了这么多，下面即开始练习我们的代码：

    view plaincopyprint?

  1. STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)  
  2. {  
  3.     if(NULL == ppTreeNode)  
  4.         return FALSE;  
  5.   
  6.     return TRUE;  
  7. }  
 
STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)
{
	if(NULL == ppTreeNode)
		return FALSE;

	return TRUE;
}

    此时，可以用一个测试用例验证一下

[cpp] view plaincopyprint?
  1. static void test1()  
  2. {  
  3.     assert(FALSE == insert_node_into_tree(NULL, 10));  
  4. }  
static void test1()
{
	assert(FALSE == insert_node_into_tree(NULL, 10));
}


    view plaincopyprint?

 
 
  1. STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)  
  2. {  
  3.     if(NULL == ppTreeNode)  
  4.         return FALSE;  
  5.   
  6.     if(NULL == *ppTreeNode){  
  7.         *ppTreeNode = (TREE_NODE*)create_tree_node(data);  
  8.         assert(NULL != *ppTreeNode);  
  9.         return TRUE;  
  10.     }  
  11.   
  12.     return TRUE;  
  13. }  
 
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;
}

    修改了代码，少不了测试用例的添加。

[cpp] view plaincopyprint?
  1. static void test2()  
  2. {  
  3.     TREE_NODE* pTreeNode = NULL;  
  4.     assert(TRUE == insert_node_into_tree(&pTreeNode, 10));  
  5.     assert(10 == pTreeNode->data);  
  6.     free(pTreeNode);  
  7. }  
static void test2()
{
	TREE_NODE* pTreeNode = NULL;
	assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
	assert(10 == pTreeNode->data);
	free(pTreeNode);
}

  

    view plaincopyprint?

 
 
  1. STATUS _insert_node_into_tree(TREE_NODE** ppTreeNode, int data, TREE_NODE* pParent)  
  2. {  
  3.     if(NULL == *ppTreeNode){  
  4.         *ppTreeNode = create_tree_node(data);  
  5.         assert(NULL != *ppTreeNode);  
  6.         (*ppTreeNode)->parent = pParent;  
  7.         return TRUE;  
  8.     }  
  9.   
  10.     if(data < (*ppTreeNode)->data)  
  11.         return _insert_node_into_tree(&(*ppTreeNode)->left_child, data, *ppTreeNode);  
  12.     else  
  13.         return _insert_node_into_tree(&(*ppTreeNode)->right_child, data, *ppTreeNode);  
  14. }  
  15.   
  16. STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)  
  17. {  
  18.     if(NULL == ppTreeNode)  
  19.         return FALSE;  
  20.   
  21.     if(NULL == *ppTreeNode){  
  22.         *ppTreeNode = (TREE_NODE*)create_tree_node(data);  
  23.         assert(NULL != *ppTreeNode);  
  24.         return TRUE;  
  25.     }  
  26.   
  27.     return _insert_node_into_tree(ppTreeNode, data, NULL);  
  28. }  
 
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);
}

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

[cpp] view plaincopyprint?
  1. static void test3()  
  2. {  
  3.     TREE_NODE* pTreeNode = NULL;  
  4.     assert(TRUE == insert_node_into_tree(&pTreeNode, 9));  
  5.     assert(TRUE == insert_node_into_tree(&pTreeNode, 8));  
  6.     assert(TRUE == insert_node_into_tree(&pTreeNode, 10));  
  7.     assert(9 == pTreeNode->data);  
  8.     assert(8 == pTreeNode->left_child->data);  
  9.     assert(10 == pTreeNode->right_child->data);  
  10.     free(pTreeNode->left_child);  
  11.     free(pTreeNode->right_child);  
  12.     free(pTreeNode);  
  13. }  
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

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wgang171412/p/4953275.html