ステップ書きアルゴリズム(ツリー挿入のソート)

【声明:著作権所有、転載歓迎、商業用途に使用しないでください.連絡ポスト:[email protected]】
ツリーのノード挿入は比較的簡単です.一般的に、ツリーの挿入は主に次の2つのステップに分けられます.
1)現在のパラメータを判断するには,ヘッダノードを考慮する必要があるため,ポインタのポインタを関数の入力パラメータとして用いた.
2)状況別討論:
元のツリーにルートノードがない場合、この新しく挿入されたデータはルートノードです.
もし元の二叉木にルートノードがあれば、私たちはこのデータが存在したかどうかを判断し、存在すれば、戻ります.存在しない場合は、データの挿入を続けます.
では、挿入し続けたデータはどのように保存しますか?また、3つの状況に分けられます.
1)挿入データが現在のノードのデータより小さい場合、現在のノードの左サブツリー方向に挿入位置を探し続ける
2)挿入データが現在挿入されている位置より大きい場合、現在のノードの右サブツリー方向に挿入位置を探し続ける
3)方向現在のノードが空の場合は,挿入位置が見つかったことを示し,データを挿入すればよい.
アルゴリズムがこんなにたくさん言ったので、コードの練習を始めます.
a)入力データの正当性判断

STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)
{
	if(NULL == ppTreeNode)
		return FALSE;

	return TRUE;
}

この場合、1つのテスト・インスタンスで検証できます.

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

はコードを修正し、テスト例の追加が欠かせない.

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

上のコードは、ルートノードではない場合を考慮しています.これに基づいてテスト例を追加できます.

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である.
【予告:次のブログでは主に二叉木のノード削除について紹介します】