遍历二叉树

二叉树

前言

二叉树的遍历主要有深度优先遍历和广度优先遍历,深度优先遍历是优先访问一个子树上的所有节点,访问的属性是竖向的,而广度优先遍历则是优先访问同一层的所有节点,访问属性是横向的。

深度优先遍历

深度优先遍历主要有三种顺序:

  • 前序遍历 —— 根左右
  • 中序遍历 —— 左根右
  • 后序遍历 —— 左右根

这三种遍历顺序用递归可以很容易实现,主要讲的是非递归的实现方法。而要使用迭代的方法来遍历二叉树,需要用到栈的特性。

前序遍历(非递归C++)

算法:

  1. 根节点入栈
  2. 访问栈顶元素并将其出栈
  3. 将左右子树入栈,由于访问顺序是"根左右",且使用的是栈,因此右子树先于左子树入栈
  4. 重复步骤2、3,直到栈为空
void preOrder(BTNode* root) {
    stack<BTNode*> S;
    BTNode* cur = NULL;
    if(root == NULL)
        return;
    S.push(root);   //根节点入栈
    while(!S.empty()) {
        //访问顺序"根左右"
        cur = S.top();
        cout<<""<<cur->data<<"\n";
        //出栈访问过的节点
        S.pop();
        //先入栈右子树,这样就可以先访问左子树
        if(cur->right != NULL)
            S.push(cur->right);
        if(cur->left != NULL)
            S.push(cur->left);
    }
}

中序遍历(非递归C++)

算法:

  1. 根节点入栈
  2. 遍历左孩子节点,入栈,直到左子树为空
  3. 访问栈顶节点并将栈顶节点出栈
  4. 对右子树进行步骤2、3,访问当前节点的右子树
  5. 重复步骤2、3、4,直到栈空
void midOrder(BTNode* root) {
    stack<BTNode*> S;
    BTNode* cur = NULL;
    if(root == NULL)
        return;
    S.push(root);   //根节点入栈
    cur = root;
    while(!S.empty()) {
        //访问顺序"左根右"
        while(cur) {    //将左孩子依次入栈
            S.push(cur);
            cur = cur->left;
        }
        //访问最左孩子
        cur = S.top();
        cout<<""<<cur->data<<"\n";
        S.pop();
        //对右子树进行一样的操作
        cur = cur->right;
    }
}

层次遍历

层次遍历就是广度优先遍历,需要使用队列的特性FIFO

算法:

  1. 根节点入队
  2. 若队列非空,出队一个元素并访问,接着将其左右孩子入队
  3. 重复步骤2直至队空
void levelOrder(BTNode* root) {
    queue<BTNode*> Q;
    if(root == NULL)
        return;
    BTNode* cur = root;
    Q.push(root);
    while(!Q.empty()) {
        //访问队首元素
        cur = Q.front();
        cout<<cur->data<<"\n";
        Q.pop();
        /*将左右孩子入队*/
        if(cur->left != NULL)
            Q.push(cur->left);
        if(cur->right != NULL)
            Q.push(cur->left);
    }
}

热门相关:都市狐仙养成记   霸宠天下:腹黑帝君妖娆后   拳罡   锦绣医妃之庶女凰途   唐土万里