二叉树深度遍历和广度遍历

本人已迁移博客至掘进，以后会在掘进平台更新最新的文章也会有更多的干货，欢迎大家关注！！！https://juejin.im/user/588993965333309

在二叉树排序中，还存在另外两种排序，二叉树深度优先遍历和广度优先遍历。建议大家找纸币和纸，建议手写一下，哪怕是伪代码。大约花费大家5-15分钟，欢迎指正！！！

案例

二叉树深度遍历和广度遍历

对于上面二叉树，如果面试官：

广度优先排序

要求从上向下从左到右依次打印出来，也就是ABCDEFG，看到这个要求可能想到广度优先排序（宽度优先排序或者横向优先搜索）是从根结点开始沿着树的宽度搜索遍历。可以利用队列实现这个排序：

是从根结点开始，沿着树的宽度遍历树的节点，A第一个访问，紧接着将A的两个孩子BC进队列，当B出队列时，然后B的两个孩子DE进去，C出队列，C的两个孩子FG进入，最后将DEFG输出。

//广度优先遍历
void breadthFirstSearch(Tree root){
    queue<Node *> nodeQueue;  //使用C++的STL标准模板库
    nodeQueue.push(root);
    Node *node;
    while(!nodeQueue.empty()){
        node = nodeQueue.front();
        nodeQueue.pop();
        printf(format, node->data);
        if(node->lchild){
            nodeQueue.push(node->lchild);  //先将左子树入队
        }
        if(node->rchild){
            nodeQueue.push(node->rchild);  //再将右子树入队
        }
    }
}

深度优先搜索

深度优先搜索：沿着树的深度遍历树的所有节点，尽可能搜索树的分支，当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。
如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

所以深度优先排序的结果为：ABDECFG

A是第一个被访问的，然后顺序变为BD，然后E，接着为C，FG

先遍历了根结点后，再左子树，最后右子树；我们可以借助栈，栈的顺序是后进先出，可以让右子树压栈，然后再对左子树压栈。代码如下：

//深度优先遍历
void depthFirstSearch(Tree root){
    stack<Node *> nodeStack;  //使用C++的STL标准模板库
    nodeStack.push(root);
    Node *node;
    while(!nodeStack.empty()){
        node = nodeStack.top();
        printf(format, node->data);  //遍历根结点
        nodeStack.pop();
        if(node->rchild){
            nodeStack.push(node->rchild);  //先将右子树压栈
        }
        if(node->lchild){
            nodeStack.push(node->lchild);  //再将左子树压栈
        }
    }
}

原文链接: https://www.cnblogs.com/guohai-stronger/p/9396070.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/278481

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

二叉树深度遍历和广度遍历

相关推荐