专栏首页本立2道生二叉树的遍历回顾

二叉树的遍历回顾

目录

  • 写在前面
  • 递归式遍历
  • 先序遍历的迭代版本
  • 中序遍历的迭代版本
  • 后序遍历的迭代版本
  • 层次遍历
  • 小结
  • 参考

写在前面

本文重点在于复习并总结 二叉树每种遍历方式的递归与迭代实现,图片和示例代码均来自《邓俊辉-数据结构》

向量vector链表list线性结构,其中的元素具有天然的直接前驱直接后继

二叉树binary tree半线性结构,其元素不存在天然的直接前驱和后继,但可以通过附加某种约束,将其线性化。

线性化的方法称之为遍历traversal,具体地,遍历指的是

按照事先约定的某种规则和次序,对所有节点各访问一次且仅一次。

根据约束(规则、次序)的不同,可以分为 先序中序后序遍历以及层次遍历,根据实现方式的不同,又可分为 递归式遍历迭代式遍历

简化二叉树的数据结构为

#define BinNodePosi(T) BinNode<T>*
template <typename T> struct BinNode {
    T data;
    BinNodePosi(T) parent;
    BinNodePosi(T) lChild; 
    BinNodePosi(T) rChild;
};

得益于递归的简洁性,先对先序、中序和后序遍历的递归实现一探究竟。

递归式遍历

二叉树可以递归地定义,根节点、左子树和右子树,左右子树也可以分别是一棵二叉树。

令当前根节点为V,左孩子和右孩子分别为L和R,对于当前这个局部,访问的次序有VLR、LVR、LRV 共3种,根据V所在的访问次序,分别称之为先序、中序和后续。

因为L和R也是树,VLR、LVR和LRV可以对L和R进一步展开,展开时也是按相应的先序、中序和后续方式访问。L和R被当成新的V,形成递归。

对应到代码上,三种遍历方式的递归实现可套用同一个代码模板,区别只在于访问V的位置不同

template <typename T, typename VST> //元素类型、操作器
void traversal(BinNodePosi(T) x, VST& visit) { //二叉树后序遍历算法(递归)
    if (!x) return;
    // visit(x->data); // 先序遍历
    traversal(x->lChild, visit);
    // visit(x->data); // 中序遍历
    traversal(x->rChild, visit);
    // visit(x->data); // 后序遍历
}

3种方式对应的遍历路径如下,

通过先序、中序和后序遍历,线性化得到的序列分别为VLR、LVR和LRV的彻底展开,序列中每个局部也都符合先序、中序和后序的次序。

下面看一下,不同遍历的迭代实现,在于洞察不同规则下访问路径的特点。

先序遍历的迭代版本

先序遍历为VLR的完全展开,先访问当前节点,如果有左子树,先访问左子树,访问完左子树再右子树。

相当于如下过程,

  • 如果有左侧通路,就沿着左侧通路自顶向下访问沿途节点,先遇到的节点先访问,直到最左侧走到头
  • 再自底向上,以同样的方式遍历右子树

如下图所示

需要逆序记录最左侧通路上节点的右孩子,恰好适合用栈实现,代码如下:

//从当前节点出发,沿左分支不断深入,直至没有左分支的节点;沿途节点遇到后立即访问
template <typename T, typename VST> //元素类型、操作器
static void visitAlongLeftBranch(BinNodePosi(T) x, VST& visit, Stack<BinNodePosi(T)>& S) {
    while (x) {
        visit(x->data); //讵问弼前节点
        S.push(x->rChild); //右孩子入栈暂存(可优化:通过判断,避免空的右孩子入栈)
        x = x->lChild; //沿左分支深入一层
    }
}

template <typename T, typename VST> //元素类型、操作器
void travPre(BinNodePosi(T) x, VST& visit) { //二叉树先序遍历算法(迭代版)
    Stack<BinNodePosi(T)> S; //辅助栈
    while (true) {
        visitAlongLeftBranch(x, visit, S); //从当前节点出发,逐批访问
        if (S.empty()) break; //直到栈空
        x = S.pop(); //弹出下一批的起点
    }
}

中序遍历的迭代版本

中序遍历为LVR的完全展开,访问完左子树,再访问当前节点,然后右子树。

流程如下:

  • 如果有左侧通路,沿着左侧通路自顶向下,沿途节点仅路过不访问,至最左侧走到头(没有左孩子的节点)
  • 再自底向上,访问沿途各节点及其右子树

如下图所示,

逆序记录路过的节点,也用栈,代码如下,

template <typename T> //从当前节点出发,沿左分支不断深入,直至没有左分支的节点
static void goAlongLeftBranch(BinNodePosi(T) x, Stack<BinNodePosi(T)>& S) {
	//当前节点入栈后随即向左侧分支深入,迭代直到无左孩子
	while (x) { S.push(x); x = x->lChild; } // 该行可合并到调用函数中,以简化代码
}

template <typename T, typename VST> //元素类型、操作器
void travIn(BinNodePosi(T) x, VST& visit) { //二叉树中序遍历算法
    Stack<BinNodePosi(T)> S; //辅助栈
    while (true) {
         goAlongLeftBranch(x, S); //从当前节点出发,逐批入栈
         if (S.empty()) break; //直至所有节点处理完毕
         x = S.pop(); visit(x->data); //弹出栈顶节点并讵问
         x = x->rChild; //转向右子树
    }
}

后序遍历的迭代版本

后序遍历为LRV的完全展开,如果有左子树先遍历左子树,遍历完左子树,再遍历右子树,最后访问当前节点。

流程如下,

  • 与先序和中序遍历不同,不再只沿着左侧通路,而是优先左侧通路,左侧到头后走右侧,直至叶子节点中最左侧的那个
  • 再自底向上,访问沿途各节点

如下图所示,

因为输出是以LRV的次序输出,所以入栈时需按VRL入栈,逆序记录沿途各节点及其右孩子和左孩子,同时,需要判断,代码如下

template <typename T> //在以S栈顶节点为根的子树中,找到最高左侧可见叶节点
static void gotoHLVFL(Stack<BinNodePosi(T)>& S) { //沿递所遇节点依次入栈
    while (BinNodePosi(T) x = S.top()) //自顶而下,反复检查当前节点(即栈顶)
        if (HasLChild(*x)) { //尽可能向左
            if (HasRChild(*x)) S.push(x->rChild); //若有右孩子,优先入栈
            S.push(x->lChild); //然后才转至左孩子
        } else //实不得已
            S.push(x->rChild); //才向右
    S.pop(); //返回之前,弹出栈顶的空节点
}

template <typename T, typename VST>
void travPost(BinNodePosi(T) x, VST& visit) { //二叉树的后序遍历(迭代版)
    Stack<BinNodePosi(T)> S; //辅助栈
    if (x) S.push(x); //根节点入栈
    while (!S.empty()) {
        if (S.top() != x->parent) //若栈顶非当前节点的父亲(则必为其右兄),此时需
        	gotoHLVFL(S); //在以其右兄为根的子树中,找到HLVFL(相当于递归深入其中)
        x = S.pop(); visit(x->data); //弹出栈顶(即前一节点的后继),并访问
    }
}

层次遍历

层次遍历,也就是所谓的广度优先遍历,顾名思义,按“先上后下、先左后右”的顺序逐层访问。

如下图所示,

根节点,左孩子,右孩子,左孩子的左孩子,左孩子的右孩子,右孩子的左孩子,右孩子的右孩子……先访问的节点,其孩子在下一层也是先访问,适合使用队列,在节点出列时将其左右孩子入列。代码如下,

template <typename T> template <typename VST> //元素类型、操作器
void BinNode<T>::travLevel(VST& visit) { //二叉树局次遍历算法
    Queue<BinNodePosi(T)> Q; //辅助队列
    Q.enqueue(this); //根节点入队
    while (!Q.empty()) { //在队列再次变空之前,反复迭代
        BinNodePosi(T) x = Q.dequeue(); visit(x->data); //取出队首节点并讵问
        if (HasLChild(*x)) Q.enqueue(x->lChild); //左孩子入队
        if (HasRChild(*x)) Q.enqueue(x->rChild); //右孩子入队
    }
}

小结

二叉树的遍历,

  • 先序、中序和后序遍历,是对VLR、LVR和LRV的完全展开
  • 递归版本,使用同一模板实现,只是访问当前数据的代码放置位置不同
  • 迭代版本,三者均可以通过辅助栈实现,根据VLR、LVR和LRV推导出遍历路径,将该路径上待访问的节点逆序压栈,出栈时需考虑对右子树进行同样的遍历
  • 层次遍历,比较简单,使用辅助队列,父辈先访问的,其孩子在子辈也先访问,出列的同时将孩子入列

参考

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数字图像处理,计算机视觉,计算机图形学,计算摄影

    计算机视觉(Computer Vision, CV),输入为图像或图像序列,输出为某种信息或描述,目的在于理解图像,获得语义信息。比如目标识别任务,输入一张图片...

    李拜六不开鑫
  • 电脑护眼设置:蓝色光波过滤

    本人高度近视,因此平时使用电脑时总会关注如何护眼,安卓手机上使用了app “蓝色光波过滤”,感觉不错,就想看看PC上有没有相应的软件,找倒是找到了,不过需要先安...

    李拜六不开鑫
  • 人脸检测中,如何构建输入图像金字塔

    在文章《特征,特征不变性,尺度空间与图像金字塔》中我们初步谈到了图像金字塔,在这篇文章中将介绍如何在人脸检测任务中构建输入图像金子塔。

    李拜六不开鑫
  • 如何根据二叉树的两种遍历方式重建二叉树(理论篇)

    我们知道,二叉树有三种不同的遍历方式:先序遍历,中序遍历和后序遍历。这三种遍历方式本质上是根据根节点的位置来命名的。根节点在前面,就是先序遍历;根节点在中间,就...

    青南
  • 遍历

    前序遍历(DLR),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。

    Centy Zhao
  • 二叉树---(3)前序遍历,中序遍历,后序遍历

            很多朋友在刚开始接触二叉树时,对前序遍历,中序遍历,后序遍历这三个遍历方式不太了解,很多博客中,上来就是实现方式,并没有清晰的阐述这三种遍历的步...

    IT云清
  • 5.2二叉搜索树遍历(前序、中序、后序、层次、广度优先遍历)

    前言:在上一节中,我们对树及其相关知识做了了解,对二叉搜索树做了基本的实现,下面我们继续完善我们的二叉搜索树。

    wfaceboss
  • 二叉树的遍历:先序中序后序遍历的递归与非递归实现及层序遍历

      对于一种数据结构而言,遍历是常见操作。二叉树是一种基本的数据结构,是一种每个节点的儿子数目都不多于2的树。二叉树的节点声明如下: 1 typedef str...

    llhthinker
  • 图的深度遍历和广度遍历

    图的深度遍历和广度遍历都不算很难像极了二叉树的前序遍历和层序遍历,如下面的图,可以用右边的邻接矩阵进行表示,假设以顶点0开始对整幅图进行遍历的话,两种遍历方式的...

    233333
  • 爬虫课程(四)|深度优先和广度优先算法

    黄小怪

扫码关注云+社区

领取腾讯云代金券