Question

深度优先搜索的C++的实现

Answer 1

定义一个结构体来表达一个NODE的结构： struct Node  {    int self; //数据     node *left; //左节点     node *right; //右节点  };那么我们在搜索一个树的时候，从一个节点开始，能首先获取的是它的两个子节点。 例如： “                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;       }”