非再帰学習ツリー構造(三)--深広優先検索


深さ優先探索と広さ優先探索は木構造でよく用いられる2つの探索遍歴方式であるが、実際には図に用いられることが多く、深さ優先探索は向図にループがあるか否かを判断するのに用いることができ、広さ優先探索はより有用であり、よく用いられる経路探索アルゴリズムは一般的に広さ優先探索に基づいて構築されるが、dijkstra(ディジェストラ)アルゴリズム、A*アルゴリズムなど、両者の唯一の違いは、A*アルゴリズムにパスウェイトを計算する際に評価関数を加えて広捜の方向を変え、検索を目的地に伸ばし、無駄な検索の数を減らすことだと感じているので、A*アルゴリズムの良し悪しは、その評価関数によって決まる(個人的な感覚だけ).
本題に戻りますが、ここではまず図の遍歴を議論しません.その後、分析する機会があります.まず、比較的簡単な木の深さと広さを見てみましょう.
深搜是:一本筋底式搜索,
広捜とは、最初から次から次へと進む検索です.
直接コードを分析して、前の文章はすでに木を建てる過程を紹介して、私達のここは木を建てる過程に対して多く解釈して、直接深く探して広く探しているコードを見ません

/*BST.c*/
/*            ，             */
/*      */
/**/
void DFS(Node* root)
{
	Stack stack;
	registstack(&stack);
	stack.init_size(&stack, 1000);
	/*       */
	if (NULL == root)
	{
		printf(" empty tree!!!
 ");
		return;
	}

	/*        */
	Node* tmp = root;
	stack.push(&stack, tmp);
	/*        */
	while (!stack.is_empty(&stack))
	{
		tmp = stack.top(&stack);
		stack.pop(&stack);
		printf("%d\t",tmp->val);

		/*              ？         
		                   A
				      /    \
				     B      C
				    /  \    / \
				   D    E  F   G
	           ，A            ，
		     ：     ，A  ，  A  ，   C（    ）  ，
		             B（    ）  ，
		     ： B   （    ）   B     E  ，    D  ，
		                    AB，         CED，
		     ：     ED，D    ，     D，D     ，
		                        ，     CE
		     ：E  ，E      ，             ，
		                C
		     ：C  ， G F  ，     GF
		     ： F  ，F    ，            ，
		                G
		     ： G  ，  G     ，            ，
		                ，      
		*/
		if (tmp->prc)
			stack.push( &stack, tmp->prc  );
		if (tmp->plc)
			stack.push( &stack, tmp->plc  );
	}
}

/*      */
void BFS(Node* root)
{
	Node* tmp = root;

	if (tmp == NULL)
	{
		printf("Tree is empty!!!");
		return;
	}

	Queue queue;/*       	*/
	registerqueue(&queue);
	queue.initqueue(&queue);

	queue.push(&queue, tmp);/*       */
	/*         */
	while (!queue.is_empty(&queue))
	{
		/*       */
		tmp = queue.get(&queue)->val;
		printf("%d\t",tmp->val);
		/*          ，                     
		      A
		    /    \
		   B      C
		  /  \   /  \
		 D    E  F   G
		      ：     ，     A  ，  A    ，   B    ，
		              C    ，   A    
		      ：     ，    BC    ，  B     ，              B，
		               D E    ，B    ，     CDE
		      ：     ，    CDE，     C，    C，  C      FG  ，
		             C  ，         DEFG
		      ：     ，     DEFG，  D  ，  D     ，            ，
		            D  ，     EFG
		      ：E  ，      ，E  ，
		      ：F  ，      ，F  ，
		      ：G  ，      ，G  ，    ，    
		*/
		if (tmp->plc != NULL)
		{
			queue.push(&queue, tmp->plc);
		}
		if (tmp->prc != NULL)
		{
			queue.push(&queue,tmp->prc);
		}
		queue.pop(&queue);
	}
}

以上が深さ優先と広さ優先検索の具体的なコードです.コードは原理を簡単に説明するために使用されます.間違いは、訂正してください.