个性化阅读
专注于IT技术分析

离散数学遍历二叉树

点击下载

遍历意味着访问树的所有节点。有三种遍历二叉树的标准方法。这些如下:

  1. 预购遍历
  2. 邮购遍历
  3. 有序遍历

1.预遍历:二叉树的预遍历是一个递归过程。一棵树的遍历遍历为

  • 参观树的根。
  • 遍历左子树。
  • 遍历右侧子树。

2.后序遍历:二叉树的后序遍历是一个递归过程。一棵树的后置遍历为

  • 以后置顺序遍历左侧子树。
  • 以后置顺序遍历右边的子树。
  • 参观树的根。

3.有序遍历:二叉树的有序遍历是一个递归过程。树的有序遍历为

  • 按顺序遍历左侧子树。
  • 参观树的根。
  • 按顺序遍历右侧子树。

示例:确定二叉树的前序, 后序和有序遍历, 如图所示:

离散数学遍历二叉树

解决方案:树的预排序, 后排序和有序遍历如下:

Preorder 1 2 3 4 5 6 7 8 9 10 11
Postorder 3 5 4 2 7 10 9 11 8 6 1
Inorder 3 2 5 4 1 7 6 9 10 8 11

演算法

(a)给出树的有序和预序遍历时绘制唯一二叉树的算法:

  1. 我们知道二叉树的根是其预定顺序中的第一个节点。画出树的根。
  2. 要查找根节点的左子节点, 首先, 使用顺序遍历在二叉树的左子树中查找节点。 (在顺序遍历中留给根节点的所有节点都是左子树的节点)。之后, 通过选择左子树的预遍历中的第一个节点来获得根的左子节点。画左孩子。
  3. 以相同的方式, 使用顺序遍历在二叉树的右子树中查找节点。然后, 通过选择右子树的预遍历中的第一个节点来获得右子级。画一个合适的孩子。
  4. 对每个新节点重复步骤2和3, 直到未按预定顺序访问每个节点。最后, 我们获得一棵唯一的树。

示例:当有序遍历和预遍历遍历如下时, 绘制唯一的二叉树:

Inorder B A D C F E J H K G I
Preorder A B C D E F G H J K I

解决方案:我们知道二叉树的根是预遍历中的第一个节点。现在, 检查A, 在有序遍历中, 左A的所有节点都是左子树的节点, 而右A的所有节点都是右子树的节点。阅读预购中的下一个节点, 并检查其相对于根节点的位置(如果它在根节点的左侧), 则将其绘制为左子节点, 否则将其绘制为右子节点。对每个新节点重复上述过程, 直到读取了遍历遍历的所有节点, 最后我们得到了二叉树, 如图所示:

离散数学遍历二叉树

(b)在给出树的有序和后序遍历时绘制唯一二叉树的算法:

  1. 我们知道二叉树的根是其后序中的最后一个节点。画出树的根。
  2. 要找到根节点的右子节点, 首先, 使用顺序遍历在二叉树的右子树中找到节点。 (在顺序遍历中, 根节点右边的所有节点都是右边子树的节点)。之后, 通过选择右子树的后序遍历中的最后一个节点来获得根的右子节点。画一个合适的孩子。
  3. 以相同的方式, 使用顺序遍历在二叉树的左子树中查找节点。然后, 通过选择左子树的后序遍历中的最后一个节点来获得左孩子。画左孩子。
  4. 对每个新节点重复步骤2和3, 直到在后继订购中未访问每个节点为止。访问最后一个节点后, 我们获得了唯一的树。

示例:为给定的Inorder绘制唯一的二叉树, Postorder遍历如下所示:

Inorder 4 6 10 12 8 2 1 5 7 11 13 9 3
Postorder 12 10 8 6 4 2 13 11 9 7 5 3 1

解决方案:我们知道二叉树的根是后遍历中的最后一个节点。因此, 在根节点中一个。

现在, 检查有序遍历, 我们知道根在中心, 因此, 在有序遍历中留在根节点上的所有节点都是左子树的节点, 而在根节点右边的所有节点都是正确的子树。

现在, 从后顺序遍历中从后面访问下一个节点, 并检查其在顺序遍历中的位置, 如果它在根的左侧, 则将其绘制为左子节点, 如果它在右侧, 则将其绘制为右子节点。

对每个新节点重复上述过程, 我们获得如图2所示的二叉树:

离散数学遍历二叉树

(c)将通用树转换为二叉树的算法

  1. 从根节点开始, 树的根也是二叉树的根。
  2. 树中根节点的第一个子节点C1(从左开始)是二叉树中根节点的左子节点C1, C1的兄弟节点是C1的右子节点, 依此类推。
  3. 对每个新节点重复步骤2。

示例:将如图所示的以下树转换为二叉树。

离散数学遍历二叉树

解决方案:树的根是二叉树的根。因此, A是二叉树的根。现在B成为二叉树中A的左孩子, C成为B的右孩子, D成为C的右孩子, E成为二叉树中D的右孩子, 类似地应用算法, 我们得到二叉树如图:

离散数学遍历二叉树

赞(0)
未经允许不得转载:srcmini » 离散数学遍历二叉树

评论 抢沙发

评论前必须登录!