【5.2】二叉树的抽象数据类型

抽象数据类型:

  • 逻辑结构 + 运算
  • 针对整棵树
    • 初始化二叉树
    • 合并两棵二叉树
  • 围绕结点
    • 访问某个结点的左子结点、右子结点、父结点
    • 访问结点存储的数据

一、二叉树结点ADT

二、遍历二叉树

  • 遍历 (或称周游,traversal)
    • 系统地访问数据结构中的结点
    • 每个结点都正好被访问到一次
  • 二叉树的结点的 线性化

2.1 深度优先遍历二叉树

三种深度优先遍历的递归定义:

  1. 前序法 (tLR次序,preorder traversal)。 访问根结点; 按前序遍历左子树; 按前序遍历右子树。
  2. 中序法 (LtR次序,inorder traversal)。 按中序遍历左子树; 访问根结点; 按中序遍历右子树。
  3. 后序法 (LRt次序,postorder traversal)。 按后序遍历左子树; 按后序遍历右子树; 访问根结点。

表达式二叉树:

深度优先遍历二叉树(递归):

思考

前、中、后序哪几种结合可以恢复二叉树的结构?

已知某二叉树的中序序列为 {A, B, C, D, E, F, G}, 后序序列为 {B, D, C, A, F, G, E};,则其前序序列为 ____________________。

2.2 DFS遍历二叉树的非递归算法

  • 递归算法非常简洁——推荐使用
    • 当前的编译系统优化效率很不错了
  • 特殊情况用栈模拟递归
    • 理解编译栈的工作原理
    • 理解深度优先遍历的回溯特点
    • 有些应用环境资源限制不适合递归

非递归前序遍历二叉树

思想:

  • 遇到一个结点,就访问该结点,并把此结点的非空右结点推入栈中,然后下降去遍历它的左子树;
  • 遍历完左子树后,从栈顶托出一个结点,并按照它的右链接指示 的地址再去遍历该结点的右子树结构。

非递归中序遍历二叉树

  • 遇到一个结点
    • 把它推入栈中
    • 遍历其左子树
  • 遍历完左子树
    • 从栈顶托出该结点并访问之
    • 按照其右链地址遍历该结点的右子树

非递归后序遍历二叉树

  • 左子树返回 vs 右子树返回 ?
  • 给栈中元素加上一个特征位
    • Left 表示已进入该结点的左子树, 将从左边回来
    • Right 表示已进入该结点的右子树, 将从右边回来

非递归后序遍历二叉树算法

二叉树遍历算法的时间代价分析

  • 在各种遍历中,每个结点都被访问且 。只被访问一次,时间代价为O(n)
  • 非递归保存入出栈(或队列)时间
    • 前序、中序,某些结点入/出栈一次, 不超过O(n)
    • 后序,每个结点分别从左、右边各入/出 一次, O(n)

深搜:栈的深度与树的高度有关

  • 最好 O(log n)
  • 最坏 O(n)

思考

  • 非递归遍历的意义?
    • 后序遍历时,栈中结点有何规律?
    • 栈中存放了什么?
  • 前序、中序、后序框架的算法通用性?
    • 例如后序框架是否支持前序、中序访问?
  • 若支持,怎么改动?

2.2 宽度优先搜索

从二叉树的第 0 层(根结点)开始,自上至下 逐层遍历;在同一层 中,按照 从左到右 的顺序对结点逐一访问。

例如:A B C D E F G H I

二叉树遍历算法的时间代价分析

  • 在各种遍历中,每个结点都被访问且 只被访问一次,时间代价为O(n)
  • 非递归保存入出栈(或队列)时间
    • 宽搜,正好每个结点入/出队一次,O(n)
  • 宽搜:与树的最大宽度有关
    • 最好 O(1)
    • 最坏 O(n)

思考

试比较宽搜与非递归前序遍历算法框架

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学