图解用栈数据结构对树的遍历

本公众号主要推送关于如何构思算法使之应用到我们的工作中。计算机常用算法思想大致来说有,分而治之,动态规划,贪心算法,搜索算法,回溯 ,训练这些思维的一个很好的平台是Leetcode,不定时推送相关题目图文分析过程。近年来,大数据处理和分布式计算,machine learning and deep learning 的发展,又出现了很多相关算法,那么这些算法又如何应用呢?仅仅因为喜欢算法,所以一直坚持每天学习总结算法。只要每天跟着这个公众号,相信你一定会有收获。请点击上方的蓝字,免费添加公众号,一起进步吧!

图解用栈数据结构对树的前序遍历,中序遍历,后续遍历。

01

树的遍历

所谓遍历 (Traversal) 是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。

02

二叉树遍历

本文以二叉树的遍历为例总结。

二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:

  • 访问结点本身(Node)
  • 遍历该结点的左子树(Left subtree)
  • 遍历该结点的右子树(Right subtree)

根据访问结点操作发生位置不同,命名:

  • 前序遍历 Preorder Traversal :访问根结点的操作发生在遍历其左右子树之前。
  • 中序遍历 Inorder Traversal:访问根结点的操作发生在遍历其左右子树之中间。
  • 后序遍历 Postorder Traversal : 访问根结点的操作发生在遍历其左右子树之后。

二叉树的数据结构定义如下所示:

    public class TreeNode<T>
    {
        public T val { get; set; }
        public TreeNode<T> left { get; set; }
        public TreeNode<T> right { get; set; }
        public TreeNode(T data)
        {
            val = data;
        }
    }

03

前序遍历(栈结构实现)

前序遍历 Preorder Traversal :先访问根结点,然后访问根节点的左子树,最后访问根节点的右子树。

给定如下图所示的二叉树,

那么用栈这种数据结构,如何前序遍历这颗二叉树呢?

首先,我们把代码放在这里,然后分析这个代码是怎么想出来的。

        public static IList<T> PreorderTraversal<T>(
                                   TreeNode<T> root)
        {
            IList<T> rtn = new List<T>();
  if (root == null) return rtn;
            var s = new Stack<TreeNode<T>>();
  s.Push(root);
            TreeNode<T> context = root;
            while (s.Count > 0) {           
  if (context == null)
                    context = s.Peek();
 rtn.Add(s.Peek().val); //访问栈顶元素
 s.Pop();
 if (context.right != null) //左子树入栈
                    s.Push(context.right);
                if (context.left != null)  //右子树入栈
                    s.Push(context.left);
  context = context.left;
            }
            return rtn;
        }

while遍历前,各个变量的状态

  • s 栈有一个节点 1
  • context 上下文变量引用节点 1

第一次遍历,此时栈中含有元素,进入循环体内,上下文为节点 1,不满足 if 条件,访问 节点 1,节点 1 出栈, 节点 1 的右子树不为 null 先入栈,左子树也为 null后入栈, 上下文变量赋值为 左子树节点 2,如下图所示:

context = node2

第二次遍历,访问节点 2,然后节点 2 出栈,节点 2 的左子树不为 null,入栈,此时的 context 被赋值为节点 2的左子树,即为 null

context = null

第三次遍历,会特殊一些了,因为此时的context为 null,注意源码实现中的 if 条件,

if (context == null)

context = s.Peek();

满足了条件,context 被赋值为栈顶节点 4,然后执行逻辑与以上遍历相同,访问栈顶节点 4,显然这个节点 4的左右子树皆为 null,context再次被赋值,且等于 null。

context = null

第四次遍历,依然满足 if 条件,context 被赋值为栈顶节点 3,执行逻辑与上相似,访问栈顶节点 3,节点 3 出栈,节点 3 的右子树为null,左子树不为null,入栈,context再次被赋值为节点 3 的左子树 5

context = node5

第五次遍历,不满足 if 条件了,直接访问节点 5, 然后节点 5 出栈,显然节点 5 左右子树为null,context赋值为node5.left,即为null,并且栈的元素已经空了。

context = null

此时,while (s.Count > 0) 不满足了,退出遍历。

前序遍历总结

前序遍历在遍历前先入栈根节点,context引用根节点,进入遍历后,有一个 if 条件判断context为null吗,如果是说明上文的左子树为null,context需要引用此时栈顶元素,访问栈顶元素,栈顶元素出栈,接下来,首先入栈右子树,然后入栈左子树,context为 context.left 进行迭代。

04

中序遍历

中序遍历,遍历根节点位于遍历左子树和右子树之间,即左子树,根节点,右子树。

中序遍历的源码如下:

        public IList<T> InorderTraversal<T>(TreeNode<T> root)
        {
            IList<T> rtn = new List<T>();
            var s = new Stack<TreeNode<T>>();
            if (root == null) return rtn;
            s.Push(root);
            while (s.Count > 0)
            {
                var context = s.Peek();
                while (context != null) 
                {
                    s.Push(context.left);
                    context = context.left;
                }
                s.Pop();
                if (s.Count == 0)
                    return rtn;
                rtn.Add(s.Peek().val); 
                TreeNode<T> curNode = s.Pop();
                s.Push(curNode.right);
            }
            return rtn;
        }

不妨您先思考一下,这段代码是怎么构思出来的,分析中序遍历,后续遍历图解,敬请关注明天的推送,谢谢。

原文发布于微信公众号 - 算法channel(alg-channel)

原文发表时间:2017-10-25

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

51 Nod 1008 N的阶乘 mod P【Java大数乱搞】

1008 N的阶乘 mod P 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 输入N和P(P为质数),求N! Mod P ...

2776
来自专栏老付的网络博客

Java中的容器

在Java中有常用的三种类型的容器,分别是List 、Map、Set,基于这个三个基本的类型,派生出很多其它的类型,具体关系如下:

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

PTA 循环单链表区间删除 (15 分)

本题要求实现带头结点的循环单链表的创建和单链表的区间删除。L是一个带头结点的循环单链表,函数ListCreate_CL用于创建一个循环单链表,函数ListDel...

2598
来自专栏决胜机器学习

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

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

52410
来自专栏WD学习记录

Python数据结构与算法笔记(4)

前序遍历中,我们首先访问根节点,然后递归地做左侧子树的前序遍历,随后是右侧子树的递归前序。

1212
来自专栏韦弦的偶尔分享

Swift 验证二叉搜索树- LeetCode

对isValidBSTUtil(node.left, min, node.val) && isValidBSTUtil(node.right, node.val...

2084
来自专栏专注 Java 基础分享

深入理解Java常用类-----时间日期

     除了String这个类在日常的项目中比较常用之外,有关时间和日期的操作也是经常遇到的,本篇就讲详细介绍下Java API中对时间和日期的支持。其实在J...

2588
来自专栏猿人谷

线性表简介

学习数据结构 -> 线性表 -> 线性表的介绍     线性表是一种典型的数据结构, 线性结构的基本特点是线性表中的数据元素是有序且有限的, 在线性结构中...

2118
来自专栏Android知识点总结

Java总结之容器家族--Collection

Set的操作比较少,基本上也就是Collection传下来的方法 Set一般基于Map来实现:HashSet、LinkedHashSet、TreeSet的特性...

1622
来自专栏决胜机器学习

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十三) ——动态查找表(二叉排序树) (原创内容,转载请注明来源,谢谢) 一、概念 1、动态查找表特点 当对动态查找表进行查...

53110

扫码关注云+社区

领取腾讯云代金券