二叉树的DFSBFS

广度优先遍历

    BFS，也就是层次遍历，相当于前序。需要借助一个队列，现将二叉树的根节点入队，然后出队，访问该节点，如果它有左子树，则将左子树根节点入队；如果有右子树，则将右子树根节点入队。然后出队，对出队节点访问，如此反复，直到队列为空。

 

void LevelOrder(BiTree root){     InitQueue(Q);               //初始化队列         BiTree p;     EnQueue(Q,root);            //将根节点入队     while(!IsEmpty(Q))          //队列不空循环     {         DeQueue(Q,p);          //访问p所指向节点         visit(p);        if(p->lchild != NULL)              EnQueue(Q,p->lchild);         //左子树不空则左子树入队        if(p->rchild != NULL)              EnQueue(Q，p->rchild);      }}

 

 

 

深度优先遍历

     DFS，遍历了根节点后，就开始遍历左子树，所以右子树肯定最后遍历。我们利用栈的性质，所以先将右子树压栈，然后在对左子树压栈。此时，左子树节点是在top上的，所以可以先去遍历左子树。

 

void DepthFirstTravel(Tree *root)  {      stack<Tree *> s;       s.push(root);           //根节点入栈    while(!s.empty())      {          root = s.top();                //读取根节点        cout << root->data << " ";              s.pop();                   //根节点出栈         if(root->rchild != NULL)          {              s.push(root->rchild);           //先右        }          if(root->lchild != NULL)          {              s.push(root->lchild);           //再左        }        }  }  

 

 

 

==================================

栈空： s.top ==  -1

栈满： s.top == MaxSize -1

入栈： s.data[++s.top] = x ;     //指针先加1，再入栈

出栈： x = s.data[s.top--];        //先出栈，指针再减1

 

队空：Q.front == Q.rear

队满：（Q.rear+1）%MaxSize == Q.front

队列中元素：(Q.rear - Q.front + Maxsize)%MaxSize

==========================

优质相关： https://www.jianshu.com/p/b42bcbb21133