二叉树的递归遍历

对于二叉树T，可以递归定义它的先序遍历、中序遍历和后序遍历，如下所示：

  • PreOrder(T)=T的根结点+PreOrder(T的左子树)+PreOrder(T的右子树)

  • InOrder(T)=InOrder(T的左子树)+T的根结点+InOrder(T的右子树)

  • PostOrder(T)=PostOrder(T的左子树)+PostOrder(T的右子树)+T的根结点

另一棵二叉树

其中，加号表示字符串连接运算。例如，对于如图6-4所示的二叉树，先序遍历为DBACEGF，中序遍历为ABCDEFG。

这3种遍历都属于递归遍历，或者说深度优先遍历（Depth-First Search，DFS），因为它总是优先往深处访问。
提示6-18：二叉树有3种深度优先遍历：先序遍历、中序遍历和后序遍历。

三个例题：
UVa 548 （Tree）
UVA 839 (Not so Mobile)
UVA 699 (The Falling Leaves)

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

  • 二叉树的递归遍历
    二叉树的结构定义 二叉树的遍历 对二叉树的遍历是指访问树的每个结点，且每个结点仅被访问一次。访问是一个抽象的概念，...
    tingshuo123阅读 3,669评论 0赞 0
  • 二叉树的递归遍历（JS实现）
    相关概念 「树的遍历」 指按照一定规则不重复地访问树中所有节点的过程。「访问」指针对节点的操作，如打印节点的值，更...
    nbb3210阅读 5,841评论 0赞 1
  • 二叉树的递归遍历
    【链表存储结构】 【先序遍历】先访问根节点，先序遍历其左子树，先序遍历其右子树。 【中序遍历】 【后序遍历】
    日常表白结衣阅读 1,103评论 0赞 0
  • 数据结构和算法--二叉树的实现
    数据结构和算法--二叉树的实现 几种二叉树 1、二叉树 和普通的树相比，二叉树有如下特点： 每个结点最多只有两棵子...
    sunhaiyu阅读 11,590评论 0赞 14
  • 树与树的表示
    编译环境：python v3.5.0, mac osx 10.11.4 前述内容： 线性表 队列 堆栈 线性结构...
    掷骰子的求阅读 7,391评论 1赞 7

友情链接更多精彩内容