常见算法之二叉树遍历

全文概要


所谓遍历二叉树,就是遵从某种次序,顺着某一条搜索路径访问二叉树中的各个结点,使得每个结点均被访问一次,而且仅被访问一次。本文详细介绍了二叉树的前序(又称先序)、中序和后序遍历的规则及其算法实现。本文全部代码示例可从此处获得。

遍历的定义


“遍历”,即访问到二叉树中的所有结点,且每个结点仅被访问一次。“访问”的含义可以很广,如:输出结点的信息、修改结点的数据之等,但一般要求这种访问不破坏原来数据之间的逻辑结构。

本文中”访问“规定为输出当前遍历结点元素值,定义打印函数如下:

12345

template <class ElemType>void Print(ElemType e){ cout << e;}

实际上,“遍历”是任何数据结构均有的公共操作,二叉树是非线性结构,每个结点最多有两个后继,则存在如何遍历,即按什么样的搜索路径遍历的问题。这样就必须规定遍历的规则,按此规则遍历二叉树,最后得到二叉树中所有结点组成的一个线性序列。

二叉树的遍历类型


根据二叉树的结构特征,可以有三类搜索路径:先上而下的按层次遍历、先左(子树)后右(子树)的遍历、先右(子树)后左(子树)的遍历。设访问根结点记作 $D$,遍历根左子树记作 $L$,遍历根的右子树记作 $R$,则可能的遍历次序有:$DLR、LDR、LRD、DRL、RDL、RLD$ 及层次遍历。若规定先左后右,则只剩下4种遍历方式:$DLR、LDR、LRD$ 及层次遍历,根据根结点被遍历的次序,通常称 $DLR、LDR和LRD$ 这3种遍历为前序遍历、中序遍历和后序遍历。

给出如下二叉树实例:

则其不同方式的遍历序列分别为:

  • 层次遍历结果序列:ABCDEFG
  • 前序遍历结果序列:ABDGCEF
  • 中序遍历结果序列:DGBAECF
  • 后序遍历结果序列:GDBEFCA

后文依次介绍了层次遍历以及前序、中序和后序算法实现,其中用到的两个二叉树相关的数据结构 BinTreeBinTreeNode 可参见此篇

为简化二叉树遍历代码实现,给出以下二叉树的结点结构:

12345678

template <class ElemType>struct BinTreeNode{ ElemType val; // 结点关键码 BinTreeNode *leftChild; // 左孩子结点 BinTreeNode *rightChild; // 右孩子结点 BinTreeNode(ElemType v) : val(v), leftChild(nullptr), rightChild(nullptr) {} // 构造函数};

在调用本文中实现的遍历算法时,函数指针参数 Visit 即传入 Print 函数名即可。

层次遍历(Level-Order Traversal)


层次遍历是先访问层次小的所有结点,即从根结点开始,同一层次从左到右访问,然后再访问下一层次的结点。根据层次遍历的定义,除根结点外,每个结点都处于其双亲结点的下一层次,而指向每个结点的指针都记录在其双亲结点中,因此为了找到各结点,需将已经访问过的结点的孩子结点保存下来。使用一个 队列 来存储已访问过的结点的孩子结点。初始将根结点入栈,每次要访问的下一个结点都是队列上取出指向结点的指针,每访问完一个结点后,如果它有左孩子、右孩子结点,则将它的左、右孩子结点入队,如此重复,直到队列为空,则遍历结束。

下面给出二叉树层次遍历具体实现:

123456789101112131415161718192021

template <class ElemType>void LevelOrderTraverse(BinTreeNode<ElemType> *root, void (*Visit)(ElemType &)){ // 操作结果:层次遍历二叉树 if (root == nullptr) // 二叉树为空,结束算法 return; queue<BinTreeNode<ElemType> *> q; // 辅助队列 BinTreeNode<ElemType> *node = root; // 从根结点开始进行层次遍历 q.push(node); while (!q.empty()) { // 队列非空,说明还有结点未访问 node = q.front(); q.pop(); (*Visit)(node->val); if (node->leftChild != nullptr) // 左孩子非空 q.push(node->leftChild); // 左孩子入队 if (node->rightChild != nullptr) // 右孩子非空 q.push(node->rightChild); // 右孩子入队 }}

前序遍历(Pre-Order Traversal)


二叉树的前序遍历定义如下: 如果二叉树为空,则算法结束。 否则:

  1. 访问根结点(D)
  2. 前序遍历左子树(L)
  3. 前序遍历右子树(R)

前序遍历也称为先序遍历,就是按照“根-左子树-右子树”的次序遍历二叉树。

前序遍历算法分为递归和非递归实现。

递归遍历


1234567891011

template <class ElemType>void RecursionPreOrderTraverse(BinTreeNode<ElemType> *root, void (*Visit)(ElemType &)){ // 操作结果:前序遍历以root为根的二叉树(递归) if (root != nullptr) { (*Visit)(root->val); // 访问根结点 PreOrderTraverse(root->leftChild, Visit); // 递归访问左子树 PreOrderTraverse(root->rightChild, Visit); // 递归访问右子树 }}

非递归遍历


1234567891011121314151617181920

template <class ElemType>void NonRecursionPreOrderTraverse(BinTreeNode<ElemType> *root, void (*Visit)(ElemType &)){ // 操作结果:前序遍历以root为根的二叉树(非递归) if (root == nullptr) // 二叉树为空,结束算法 return; stack<BinTreeNode<ElemType> *> s; // 辅助栈 BinTreeNode<ElemType> *p; // 当前遍历结点指针 s.push(root); while (!s.empty()) // 栈非空 { p = s.top(); s.pop(); Visit(p->val); // 结点出栈即被访问 if (p->rightChild != nullptr) s.push(p->rightChild); if (p->leftChild != nullptr) s.push(p->leftChild); }}

中序遍历(In-Order Traversal)


二叉树的中序遍历定义如下: 如果二叉树为空,则算法结束。 否则:

  1. 中序遍历左子树(L)
  2. 访问根结点(D)
  3. 中序遍历右子树(R)

中序遍历就是按照“左子树-根-右子树”的次序遍历二叉树。

中序遍历算法分为递归和非递归实现。

递归遍历


1234567891011

template <class ElemType>void RecursionInOrderTraverse(BinTreeNode<ElemType> *root, void (*Visit)(ElemType &)){ // 操作结果:中序遍历以r为根的二叉树 if (root != nullptr) { InOrderTraverse(root->leftChild, Visit); // 递归访问左子树 (*Visit)(root->val); // 访问根结点 InOrderTraverse(root->rightChild, Visit); // 递归访问右子树 }}

非递归遍历


1234567891011121314151617181920212223242526

template <class ElemType>void NonRecursionInOrderTraverse(BinTreeNode<ElemType> *root, void (*Visit)(ElemType &)){ // 操作结果:中序遍历以root为根的二叉树(非递归) if (root == nullptr) // 二叉树为空,结束算法 return; stack<BinTreeNode<ElemType> *> s; // 辅助栈 BinTreeNode<ElemType> *p = root; // 当前遍历结点指针 do { while (p != nullptr) // 遍历指针未到最左下结点,则不空 { s.push(p); // 该子树沿途结点进栈 p = p->leftChild; // 遍历指针前进到左孩子结点 } if (!s.empty()) // 栈不空时退栈 { p = s.top(); s.pop(); Visit(p->val); // 结点出栈即被访问 p = p->rightChild; // 遍历指针前进到右孩子结点 } } while (p != nullptr || !s.empty()); // p非空即本轮循环访问的结点还有右孩子 或 栈中还有结点}

后序遍历(Post-Order Traversal)


二叉树的前序遍历定义如下: 如果二叉树为空,则算法结束。 否则:

  1. 后序遍历左子树(L)
  2. 后序遍历右子树(R)
  3. 访问根结点(D)

后序遍历就是按照“左子树-右子树-根”的次序遍历二叉树。

后序遍历算法分为递归和非递归实现。

递归遍历


1234567891011

template <class ElemType>void RecursionPostOrderTraverse(BinTreeNode<ElemType> *root, void (*Visit)(ElemType &)){ // 操作结果:后序遍历以r为根的二叉树 if (root != nullptr) { PostOrderTraverse(root->leftChild, Visit); // 递归访问左子树 PostOrderTraverse(root->rightChild, Visit); // 递归访问右子树 (*Visit)(root->val); // 访问根结点 }}

非递归遍历


123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354

enum Tag{ L, R};template <class ElemType>struct StackNode{ // 在后序遍历非递归实现所用栈结点类定义 BinTreeNode<ElemType> *ptr; // 指向树结点的指针 Tag tag; // 该结点的退栈标记 StackNode(BinTreeNode<ElemType> *N = nullptr) : ptr(N), tag(L) {} // 构造函数};template <class ElemType>void NonRecursionPostOrderTraverse(BinTreeNode<ElemType> *root, void (*Visit)(ElemType &)){ // 操作结果:后序遍历以root为根的二叉树(非递归) if (root == nullptr) // 二叉树为空,结束算法 return; stack<StackNode<ElemType>> s; // 辅助栈 StackNode<ElemType> w; BinTreeNode<ElemType> *p = root; // 当前遍历结点指针 do { while (p != nullptr) { w.ptr = p; w.tag = L; s.push(w); p = p->leftChild; } bool shouldContinue = true; while (shouldContinue && !s.empty()) { w = s.top(); s.pop(); p = w.ptr; switch (w.tag) { case L: w.tag = R; s.push(w); shouldContinue = false; p = p->rightChild; break; case R: Visit(p->val); break; } } } while (!s.empty());}

参考资料


[1]数据结构(用面向对象方法与C++语言描述) - 殷人昆主编

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android机动车

数据结构——遍历二叉树

二叉树的遍历:是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。

9610
来自专栏算法与数据结构

PTA 带头结点的单链表就地逆置(10 分)

本题要求编写函数实现带头结点的单链线性表的就地逆置操作函数。L是一个带头结点的单链表,函数ListReverse_L(LinkList &L)要求在不新开辟节点...

30970
来自专栏李家的小酒馆

二叉树的前、中、后遍历(递归/非递归)

二叉树的遍历 ? 二叉树的前序遍历 访问根结点,先序遍历左子树,先序遍历右子树 遍历基本步骤为先根结点,然后左子树,然后右子树, 需要注意的是这个遍历需要类似于...

24700
来自专栏决胜机器学习

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

535100
来自专栏Java Web

数据结构与算法(3)——树(二叉、二叉搜索树)树LeetCode相关题目整理

树是一种类似于链表的数据结构,不过链表的结点是以线性方式简单地指向其后继结点,而树的一个结点可以指向许多个结点;数是一种典型的非线性结构;树结构是以表达具有层次...

23720
来自专栏王硕

原 B树C语言代码实现

737100
来自专栏用户画像

4.5.1 二叉排序树

二叉排序树的查找时从根结点开始,沿着某一分支逐层向下进行比较比较的过程。若二叉排序树非空,将给定值与根结点的关键字比较,若相等,则查找成功;若不等,则当根结点的...

11430
来自专栏mathor

LeetCode222. 完全二叉树的节点个数

 常规思路,遍历整棵树,时间复杂度O(N),但是有一种时间复杂度小于O(N)的做法  首先遍历头结点右子树的最左边界,如果最左边界不为空,说明头结点的左子...

15030
来自专栏xingoo, 一个梦想做发明家的程序员

B树 B-树 B+树 B*树

B树 即二叉搜索树:        1.所有非叶子结点至多拥有两个儿子(Left和Right);        2.所有结点存储一个关键字;        3...

20870
来自专栏mukekeheart的iOS之旅

二叉树的基本概念和遍历

一、二叉树的基本概念 平衡二叉树:如果一棵树不为空,并且其中所有的子树都满足各自的左子树与右子树的高度差都不超过1。(空树是平衡二叉树)  1 //判断二叉树...

261100

扫码关注云+社区

领取腾讯云代金券