二叉树遍历方法

中序遍历

void inOrder(BinaryTree root){
    if (root){
        inOrder(root->lChild);
        cout << root->data << " ";
        inOrder(root->rChild);
    }
}

中序遍历非递归遍历

1. 先扫描根结点的所有左结点，并将他们一一进栈
2. 左结点全部入栈完后，弹出结点p并访问之，p结点赋值为p的右孩子
3. 重复第一步，直至全部结点遍历完

   void inOrderNotRecursive(BinaryTree root){
       SqStack sq;
       initStack(sq);
       TreeNode *p = root, *node;
       while (p || !isEmpty(sq)){
           if (p){
               push(sq, p);
               p = p->lChild;
           } else{
               pop(sq, node);
               cout << node->data << ' ';
               p = node->rChild;
           }
       }
   }

   先序遍历

   void PreOrder(BinaryTree root){
       if(root){
           cout << root->data << " ";
           preOrder(root->lChild);
           preOrder(root->rChild);
       }
   }

   先序非递归遍历

   coming........

   后序遍历

   void PostOrder(BinaryTree root){
       if(root){
           PostOrder(root->lChild);
           PostOrder(root->rChild);
           cout << root->data << " ";
       }
   }

   后序非递归遍历

   若使用堆栈实现后序遍历的非递归算法，根据后序遍历LRN的特点，需要用辅助指针r记录最近访问过的结点。

   void PostOrderNotRecursive(BinaryTree root){
       TreeNode *p = root, *r; //r指针用于记录最近访问过的结点
       initStack(sq);
       while(p || !isEmpy(sq)){
           if(p){ //走向最左端
               push(sq, p);
               p = p ->lChild;
           }else{
               getTop(sq, p);
               if(p -> rChild && p -> rChild != r){ //结点右子树存在，且未被访问过
                   p = p->rChild; //转向右
                   push(sq, p); 
                   p = p->lChild; //走到最左端
               }else{
                   pop(sq, p);
                   cout << p->data << " ";
                   r = p; //记录最近被访问的结点
                   p = NULL; //访问过后置空
               }
           }
   }

   层次遍历

   将根结点入队，然后出队。如果根结点有左孩子，将根结点的左孩子入队，如果根结点有右孩子，将根结点的右孩子入队。然后出队，如此循环直至访问完所有结点

   void levelOrder(BinaryTree root){
       SqQueue sq;
       TreeNode *node;
       initSqQueue(sq);
       enQueue(sq, root);
       while (!isEmpty(sq)){
           deQueue(sq, node);
           cout << node->data << " ";
           if (node->lChild){
               enQueue(sq, node->lChild);
           }
           if (node->rChild){
               enQueue(sq, node->rChild);
           }
       }
   }

本作品采用《CC 协议》，转载必须注明作者和本文链接