一歩一歩アルゴリズムを書く

【声明:著作権所有、転載歓迎、商業用途に使用しないでください.連絡ポスト:[email protected]】
二叉木の遍歴では、広さ遍歴という、珍しい遍歴方法があります.他の3つの遍歴方法とは異なり、ツリーの広さ遍歴には追加のデータ構造が必要ですか?データ構造は何ですか?それがキューです.キューには先進的な先行機能があるため、この機能では、新しい階層のデータを巡回する前に、前回のデータをすべて巡回して終了する必要があります.しばらくキューの知識を身につけていない友达は私のこのブログ-キューを見てもいいです.
a)次に、新たに追加されたキューデータ構造を示します.ここで、データ部分はツリーノードポインタのポインタに変わります.

typedef struct _QUEUE
{
	int head;
	int tail;
	int length;
	TREE_NODE** pHead;
}QUEUE;

注:headは開始、tailは終了、lengthはpHeadの長さ、pHeadはポインタの開始アドレス
b)lengthの長さに関する問題があるため、ツリー内のノードの総数を計算する必要があるキューを作成する

QUEUE* create_queue_for_tree(const TREE_NODE* pTreeNode)
{
	QUEUE* pQueue;
	int count;

	if(NULL == pTreeNode)
		return NULL;

	count = count_all_node_number(pTreeNode);
	pQueue = (QUEUE*)malloc(sizeof(QUEUE));
	assert(NULL != pQueue);
	memset(pQueue, 0, sizeof(QUEUE));

	pQueue->pHead = (TREE_NODE**)malloc(sizeof(TREE_NODE*)* count);
	assert(NULL != pQueue->pHead);
	memset(pQueue->pHead, 0, sizeof(TREE_NODE*) * count);

	pQueue->head = pQueue->tail = 0;
	pQueue->length = count;
	return pQueue;
}

    
c)キューのデータ加入とデータポップアップ操作を実現する

void insert_node_into_queue(QUEUE* pQueue, TREE_NODE* pNode)
{
	if(NULL == pQueue || NULL == pQueue->pHead ||NULL == pNode)
		return;

	pQueue->pHead[pQueue->tail ++] = pNode;
	return;
}

TREE_NODE* get_node_from_queue(QUEUE* pQueue)
{
	if(NULL == pQueue || NULL == pQueue->pHead)
		return NULL;

	if(pQueue->head == pQueue->tail)
		return NULL;

	return pQueue->pHead[pQueue->head++];
}

注:ここで定義したキューはループキューではないので、データの圧入とポップアップは簡単で、headとtailに直接処理すればいいです.
d)ノードを遍歴し,層ごとにデータを得,最後にpQueue->pHeadで得られたポインタデータが層ごとに出力される結果である.

QUEUE* traverse_node_by_layer(TREE_NODE* pNode)
{
	QUEUE* pQueue;
	if(NULL ==pNode)
		return NULL;

	pQueue = create_queue_for_tree(pNode);
	assert(NULL != pQueue);

	/*          */
	insert_node_into_queue(pQueue, pNode);
	pNode = get_node_from_queue(pQueue);

	while(pNode){
		if(pNode->left)
			insert_node_into_queue(pQueue, pNode->left);

		if(pNode->right)
			insert_node_into_queue(pQueue, pNode->right);

		pNode = get_node_from_queue(pQueue);
	}

	return pQueue;
}

拡張セクション:
上記の方法では、キューの階層別出力を実現できますが、ノード構造でデータの階層別アクセスを直接実現したい場合はどうすればいいですか?実は2歩で行けます:1)既存のTREEで_NODEはprevとnextを追加します.(2)先ほど得られたpQueue->pHeadの結果に従って,prevとnextを順に付与すればよい.友達が分かったか?