来自先序和中序遍历的二叉树 [英] Binary tree from Preorder and inorder traversal

问题描述

如何从这些 pre/in order 遍历中获取树:

How can I get the tree form these pre/in order traversal:

前:A、B、D、E、C、F、G、H在:E、D、B、A、G、F、H、C

Pre: A,B,D,E,C,F,G,H in:E,D,B,A,G,F,H,C

我的回答

       A
      / 
     B   C
    /     
   D       F
  /       / 
 E       G   H

推荐答案

更正，

您没有正确答案，FGH 在 C 的左侧.

You don't have the correct answer, FGH is to the left of C.

要验证只需针对它运行两个算法:

To verify just run the two algorithms against it:

PreOrder(node)
  if node is null return
  Print(node)
  PreOrder(node.left)
  PreOrder(node.Right)

InOrder(node)
  if node is null return
  InOrder(node.left)
  Print(node)
  InOrder(node.Right)

您知道 A 是根，因为它开始预购.使用 in-order 将节点排列在 A 的左侧和右侧.B 是第二个节点(前序)，A 的左侧是(中序)，依此类推.

You know that A is the root because it starts the pre-order. Use the in-order to arrange nodes to the left and right of A. B is the second node (pre-order), and left of A (in-order), and so on.

你知道 F,G,H 是 C 的左边，因为顺序排列.

You know that F,G,H is left of C because of the in-order arrangement.

基本上是用preorder来选择下一个节点，然后按顺序看是在父节点的左边还是右边.

Basically, use preorder to select the next node, and in-order to see whether it is left or right of the parent node.

编辑(2011 年 4 月 18 日):

为了展示这个过程是多么机械，我提供了这个伪代码:

To show how mechanical the process is I offer this pseudo code:

// Add method on binary tree class -- stock standard
method Add(item, comparer)
  newNode = new Node(item)
  parent = null

  // Find suitable parent
  currentNode = root
  while currentNode is not null
    parent = currentNode
    if comparer(newNode.Key, currentNode.Key) < 0
      currentNode = currentNode.Left
    else 
      currentNode = currentNode.Right

  // Add new node to parent
  if parent is null
    root = newNode
  else if comparer(newNode.Value, parent.Value) < 0 
    parent.Left = newNode
  else 
    parent.Right = newNode

诀窍是使用 in-order 序列来确定一个节点是添加到其父节点的左侧还是右侧，例如:

The trick is to use the in-order sequence to determine whether a node is added to the left or right of its parent, for example:

// Client code
// Input arrays
var preOrder = ["A","B","D","E","C","F","G","H"]
var inOrder  = ["E","D","B","A","G","F","H","C"]
// A collection associating the Key value with its position in the inOrder array
var inOrderMap = GetInOrderMap(inOrder)

// Build tree from pre-order and in-order sequences
foreach (item in preOrder) 
  Add(item, fun (l, r) -> inOrderMap[l] - inOrderMap[r])

我正在传递一个lamba，但任何传递比较器的等效方法都应该这样做.

I'm passing a lamba, but any equivalent method for passing a comparer should do.

这篇关于来自先序和中序遍历的二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！