KING

function bfs(vertex v){
  create a queue Q
  enqueue v into Q
  mark v as visited
  while Q is not empty{
      use temp to store Q.top
      dequeue the top vertex from Q
      for each adjacent w in temp{
          mark w as visited
          enqueue w into Q
      }
  }
}

function dfs(vertex v){
  mark v as visited //把点标记为已经访问过了
  for each node adjacent to v //对这个点的所有邻接点进行搜索
      if node is unvisited  //如果从左到右，找到这个点没有被访问过
          dfs(node) //递归调用
      //如果这个点访问过了
          //那么向右移，继续搜索
}

#define Element char
typedef struct Node{
  Element data;
  struct Node *left;
  struct Node *right;
}*Tree;
int i = 0;
//按照先序遍历建树
void construct_tree(Tree &root, Element data[]){
  Element e = data[i++];
  if(e == '#')
      root = NULL;
  else{
      root = new Node();
      root -> data = e;
      construct_tree(root -> left, data); //递归建立左子树
      construct_tree(root -> right, data); //递归建立右子树
  }   
}
void bfs(Tree root){  
  queue<Node *> q;
  q.push(root);
  while(!q.empty()){
      Node *temp = q.front();
      q.pop();
      cout<<temp -> data;
      if(temp -> left)
          q.push(temp -> left);
      if(temp -> right)
          q.push(temp -> right);
  }
}
void dfs(Tree root){
  stack<Node *> s;
  s.push(root);
  while(!s.empty()){
      Node *temp = s.top();
      s.pop();
      cout<<temp -> data;
      //因为stack是先进后出，所以先把right压进去
      if(temp -> right)
          s.push(temp -> right);
      if(temp -> left)
          s.push(temp -> left);
  }
}
int main(){
  //#表示没有左子树或者右子树
  //             A
  //           /   \
  //          B     C
  //        /  \   /  \
  //      D    E   F   G
  Element data[15] = {'A','B','D','#','#','E','#','#','C','F','#','#','G','#','#'};
  Tree tree;
  construct_tree(tree, data);
  //bfs
  cout<<"result of bfs: ";
  bfs(tree);
  cout<<endl;
  //dfs
  cout<<"result of dfs: ";
  dfs(tree);
  cout<<endl;
  return 0;
}