二叉搜索树的深度&广度优先遍历 C++实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了二叉搜索树的深度&广度优先遍历 C++实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1631字，纯文字阅读大概需要3分钟。

内容图文

实际上树和图的广度&深度优先遍历方法十分类似，所以今天针对树的遍历方法实现进行详细分析，并且树的遍历在笔试中也是非常常见的一种方法，并且《剑指Offer》中的许多面试题用到了这两种遍历方法进行不同需求的算法实现。

深度优先遍历

深度优先遍历：借助递归算法不断遍历当前遍历到节点的左右子节点，对于树这个数据结构根据左子节点、右子节点和当前节点的遍历顺序该搜索算法又可分为前序、中序和后序遍历，其中中序遍历可以达到排序的效果。

具体的遍历顺序如下图所示：

依次为 前序，后序，中序遍历。

代码实现如下：

// 前序遍历
void preOrder() {
    preOrder(root);
}

// 对以node为根的二叉搜索树进行前序遍历
void preOrder(Node *node) {
    if (node != nullptr) {
        std::cout << node->key << " ";
        preOrder(node->left);
        preOrder(node->right);
    }
}

// 中序遍历
void inOrder() {
    inOrder(root);
}

// 对以node为根的二叉搜索树进行中序遍历
void inOrder(Node *node) {
    if (node != nullptr) {
        inOrder(node->left);
        std::cout << node->key << " ";
        inOrder(node->right);
    }
}

// 后序遍历
void postOrder() {
    postOrder(root);
}

// 对以node为根的二叉搜索树进行后序遍历
void postOrder(Node *node) {
    if (node != nullptr) {
        postOrder(node->left);
        postOrder(node->right);
        std::cout << node->key << " ";
    }
}

广度优先搜索

广度优先搜索：实际上就是层序遍历，顾名思义从上到下一层一层的遍历，树的广度优先搜索是借助队列这个数据结构达到层序遍历的效果，及将已遍历的节点的子节点加入队列，并且出队进行遍历，保证了上层数据优先遍历。

具体的遍历顺序如下图所示，即先遍历黄色节点，再遍历绿色节点，最终遍历蓝色节点。

// 层序遍历
void levelOrder() {
    std::queue<Node *> q;
    q.push(root);
    while (!q.empty()) {
        Node *node = q.front();
        q.pop();
        std::cout << node->key << " ";
        if (node->left)
            q.push(node->left);
        if (node->right)
            q.push(node->right);
    }
}

内容总结

以上是互联网集市为您收集整理的二叉搜索树的深度&广度优先遍历 C++实现全部内容，希望文章能够帮你解决二叉搜索树的深度&广度优先遍历 C++实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端