深度优先搜寻( 二 ) _生活百科

那幺我们在搜寻一个树的时候，从一个节点开始，能首先获取的是它的两个子节点。例如：“ A B C D E F G”A是第一个访问的，然后顺序是B和D、然后是E 。然后再是C、F、G 。那幺我们怎幺来保证这个顺序呢？这里就应该用堆叠的结构，因为堆叠是一个先进后出的顺序。通过使用C++的STL ，下面的程式能帮助理解：“ const int TREE_SIZE = 9; std::stack<node*> visited, unvisited; node nodes[TREE_SIZE]; node* current; for( int i=0; i<TREE_SIZE; i++) //初始化树 { nodes[i].self = i; int child = i*2+1; if( child<TREE_SIZE ) //Left child nodes[i].left = &nodes[child]; else nodes[i].left = NULL; child++; if( child<TREE_SIZE ) //Right child nodes[i].right = &nodes[child]; else nodes[i].right = NULL; } unvisited.push(&nodes[0]); //先把0放入UNVISITED stack while(!unvisited.empty()) //只有UNVISITED不空 { current=(unvisited.top()); //当前应该访问的 unvisited.pop(); if(current->right!=NULL) unvisited.push(current->right); // 把右边压入因为右边的访问次序是在左边之后 if(current->left!=NULL) unvisited.push(current->left); visited.push(current); cout<<current->self<<endl; }”举例这道题来举例（迷宫）1111010101010111记录起点为（1,1）找到所有的到（4,4）的路径.pascal程式如下：constb:array[1..4,1..4]of integer=(（1,1,1,1）,(0,1,0,1）,(0,1,0,1）,(0,1,1,1）);c:array[1..4,1..2]of -1..1=((0,1）,(0,-1）,（1,0),(-1,0));vara:array[1..16,1..2]of integer;procedure print;vari,j:integer;beginfor i:=1 to 4 dobeginfor j:=1 to 4 dowrite(b[i,j]:3）;writeln;end;writeln('--------------');end;procedure try(k:integer);vari:integer;beginif (a[k,1]=4）and(a[k,2]=4） thenbeginprint;exit;end;for i:=1 to 4 dobegina[k+1,1]:=a[k,1]+c[i,1];a[k+1,2]:=a[k,2]+c[i,2];if (a[k+1,1]>=1） and (a[k+1,1]<=4 )and (a[k+1,2]>=1） and (a[k+1,2]<=4） and（b[a[k+1,1],a[k+1,2]]=1） thenbeginb[a[k+1,1],a[k+1,2]]:=2;try(k+1）;b[a[k+1,1],a[k+1,2]]:=1;end;end;end;begina[1,1]:=1;a[1,2]:=1;b[1,1]:=2;try（1）;end.