先序和中序遍历的二叉树

Question

如何从这些前/中顺序遍历中获取树：

Pre: A,B,D,E,C,F,G,H 在：E，D，B，A，G，F，H，C

编辑：我的答案

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

Answer 1

编辑：
更正，

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

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

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 是根，因为它启动了预序。使用中序将节点排列在 A 的左侧和右侧。B 是第二个节点（前序），A 的左侧（中序），依此类推。

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

基本上，使用预序来选择下一个节点，并按序查看它是在父节点的左侧还是右侧。

编辑（2011 年 4 月 18 日）：

为了展示这个过程的机械性，我提供了这个伪代码：

// 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

技巧是使用有序序列来确定节点是否添加到它的父级，例如：

// 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])

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

Answer 2

这是一种以非常简单的方式实现这一目标的数学方法：

使用的语言：Java

`
/*
从给定的中序和先序遍历构造二叉树的算法。
以下是使用的术语：

i ：表示提供的中序数组

p ：表示提供的前序数组

beg1 ：中序数组的起始索引

beg2 ：前序数组的起始索引

end1 ：中序数组的结束索引

end2 ：前序数组的结束索引

*/

public static void ConstructionTree(Node root, int[] i, int[] p, int beg1, int end1, int beg2, int end2)

{

if(beg1==end1 && beg2 == end2)
{
    root.data = i[beg1];
}
else if(beg1<=end1 && beg2<=end2)
{
    root.data = p[beg2];
    int mid = search(i, (int) root.data);
    root.left=new Node();
    root.right=new Node();
    constructTree(root.left, i, p, beg1, mid-1, beg2+1, beg2+mid-beg1);
    System.out.println("Printing root left : " + root.left.data);
    constructTree(root.right, i, p, mid+1, end1, beg2+1+mid-beg1, end2);
    System.out.println("Printing root left : " + root.right.data);
}

}

`

您需要通过以下代码调用该函数：

int[] i ={4,8,7,9,2,5,1,6,19,3,18,10}; //Inorder
int[] p ={1,2,4,7,8,9,5,3,6,19,10,18}; //Preorder
Node root1=new Node();
constructTree(root1, i, p, 0, i.length-1, 0, p.length-1);

如果您需要更详细的解释代码请在评论中提及。我很乐意提供帮助:)。

Answer 3

下面是 C# 中的一个工作实现

public static class TreeUtil
{
   public static BinarySearchTree<T> FromTraversals<T>(T[] preorder, T[] inorder)
   {
       if (preorder == null) throw new ArgumentNullException("preorder");
       if (inorder == null) throw new ArgumentNullException("inorder");
       if (preorder.Length != inorder.Length) throw new ArgumentException("inorder and preorder have different lengths");

       int n = preorder.Length;
       return new BinarySearchTree<T>(FromTraversals(preorder, 0, n - 1, inorder, 0, n - 1));
   }

   public static BinaryTreeNode<T> FromTraversals<T>(T[] preorder, int pstart, int pend, T[] inorder, int istart, int iend)
   {
       if (pstart > pend) return null;

       T rootVal = preorder[pstart];
       int rootInPos;
       for (rootInPos = istart; rootInPos <= iend; rootInPos++) //find rootVal in inorder
           if (Comparer<T>.Default.Compare(inorder[rootInPos], rootVal) == 0) break;

       if (rootInPos > iend)
           throw new ArgumentException("invalid inorder and preorder inputs");

       int offset = rootInPos - istart;
       return new BinaryTreeNode<T>(rootVal)
           {
               Left = FromTraversals(preorder, pstart + 1, pstart + offset, inorder, istart, istart + offset - 1),
               Right = FromTraversals(preorder, pstart + offset + 1, pend, inorder, istart + offset + 1, iend),
           };
   }
}

这是 BinarySearchTree 和 BinaryTreeNode的一种可能实现T>。一些测试：

[TestMethod]
public void TestGenerationFromTraversals()
{
  var preorder = new[] {1, 2, 4, 5, 3};
  var inorder = new[] {4, 2, 5, 1, 3};
  AssertGenerationFromTraversal(preorder, inorder);

  var preorder2 = new[] { 'A', 'B', 'D', 'E', 'C', 'F' };
  var inorder2 = new[] { 'D', 'B', 'E', 'A', 'F', 'C' };
  AssertGenerationFromTraversal(preorder2, inorder2);
}

private static void AssertGenerationFromTraversal<T>(T[] preorder, T[] inorder)
{
  var tree = BinarySearchTreeUtil.FromTraversals(preorder, inorder);

  var treeInorder = new List<T>();
  tree.TraverseInOrder(treeInorder.Add);
  var treePre = new List<T>();
  tree.TraversePreOrder(treePre.Add);

  Assert.IsTrue(preorder.SequenceEqual(treePre));
  Assert.IsTrue(inorder.SequenceEqual(treeInorder));
}