美文网首页
2020-08-31二叉树遍历

2020-08-31二叉树遍历

作者: 猫KK | 来源:发表于2020-08-31 15:26 被阅读0次

迭代方式遍历二叉树

1.前序遍历(根左右)

/**
 * 前序遍历
 * @tparam T
 * @param root
 * @param visit
 */
template<class T>
void startOrder(TreeNode<T> *root, void (visit)(T)) {
    //循环到底的情况
    if (root == NULL) {
        return;
    }
    //输出根节点
    visit(root->data);
    //遍历左节点
    startOrder(root->left, visit);
    //遍历右节点
    startOrder(root->right, visit);
}

2.中序遍历(左根右)

/**
 * 中序遍历
 * @tparam T
 * @param root
 * @param visit
 */
template<class T>
void centerOrder(TreeNode<T> *root, void (visit)(T)) {
    if (root == NULL) {
        return;
    }
    //先遍历左节点
    centerOrder(root->left, visit);
    visit(root->data);
    centerOrder(root->right, visit);
}

3.后序遍历(左右根)

/**
 * 后序遍历
 * @tparam T
 * @param root
 * @param visit
 */
template<class T>
void endOrder(TreeNode<T> *root, void (visit)(T)) {
    if (root == NULL) {
        return;
    }
    endOrder(root->left, visit);
    endOrder(root->right, visit);
    visit(root->data);
}

4.层序遍历

/**
 * 层序遍历
 * @tparam T
 * @param root
 * @param visit
 */
template<class T>
void levelOrder(TreeNode<T> *root, void (visit)(T)) {
    if (root == NULL) {
        return;
    }
    //借助队列实现层序遍历
    queue<TreeNode<T> *> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode<T> *node = q.front();
        q.pop();

        visit(node->data);

        TreeNode<T> *left = NULL;
        if ((left = node->left)) {
            q.push(left);
        }
        TreeNode<T> *right = NULL;
        if ((right = node->right)) {
            q.push(right);
        }
    }
}

相关文章

  • 二叉树 基础操作

    二叉树的使用 二叉树结构 先序创建二叉树 DFS 先序遍历二叉树 中序遍历二叉树 后序遍历二叉树 BFS 层次遍历...

  • 关于二叉树的算法题

    前序遍历中序遍历后序遍历判断是否是平衡二叉树判断是否是对称二叉树判断二叉树高度按照层遍历二叉树判断二叉树宽度

  • 二叉树遍历

    二叉树 二叉树的存储结构 前序遍历 中序遍历 后序遍历 遍历代码 反转二叉树 深入学习二叉树 二叉树-你必须要懂!...

  • 二叉树操作

    树节点 逐行顺序解析二叉树 前序遍历二叉树 中序遍历二叉树 后序遍历二叉树 删除指定数值的节点 前序遍历顺序存储的...

  • 数据结构与算法之二叉树遍历(七)

    目录 前序遍历中序遍历后序遍历层序遍历遍历方式的选择条件根据遍历结果重构二叉树翻转二叉树计算二叉树的高度判断一棵树...

  • 二叉树三种遍历Swift代码实现

    二叉树的三种遍历 二叉树 前序遍历 中序遍历 后序遍历 另外 不得不说,得到二叉树的前序遍历和中序遍历的结果或者后...

  • 二叉树的遍历

    二叉树的遍历 二叉树遍历 分为前序遍历、中序遍历和后序遍历。 前序遍历 (DLR) 先访问根节点,然后前序遍历左子...

  • 前端二叉树

    (一)构造二叉树 (二)中序遍历 (三)前序遍历 前序遍历可以复制二叉树,效率比重新构造二叉树高 (四)后序遍历 ...

  • 数据结构:树的实现和遍历(c++)

    (一)二叉树的遍历——递归实现 二叉树常见的遍历方式分为前序遍历、中序遍历和后序遍历。 1 前序遍历 前序遍历也叫...

  • leetcode 144 145 94

    二叉树遍历 前序遍历 中序遍历 后序遍历

网友评论

      本文标题:2020-08-31二叉树遍历

      本文链接:https://www.haomeiwen.com/subject/bngusktx.html