Binary tree von Preorder und inorder traversal

EDIT:
Korrektur,

Du hast nicht die richtige Antwort, FGH ist auf der linken Seite von C.

Überprüfen, führen Sie einfach die zwei algorithmen vor:

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)

Wissen Sie, dass ist die Wurzel, denn es beginnt die pre-order. Verwenden Sie die in-Reihenfolge zu ordnen Knoten Links und rechts von A. B ist der zweite Knoten (pre-order), und Links von Einer (in-order), und so weiter.

Wissen Sie, dass F,G,H ist Links von C wegen der in-order-Anordnung.

Grundsätzlich verwenden preorder wählen Sie den nächsten Knoten, und um zu sehen, ob es Links oder rechts vom übergeordneten Knoten.

EDIT (18 Apr 2011):

Zeigen, wie mechanischer Prozess ist, biete ich diesen 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

Der trick ist, verwenden Sie die in-order-Reihenfolge, um zu bestimmen, ob ein Knoten Hinzugefügt, um die linke oder die Rechte des übergeordneten, zum Beispiel:

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

Ich bin vorbei ein lamba, aber eine gleichwertige Methode für die übergabe eines comparer tun sollte.

InformationsquelleAutor Andre Artus

Unten ist eine funktionierende Implementierung in 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),
           };
   }
}

Hier ist eine mögliche Implementierung von BinarySearchTree<T> und BinaryTreeNode<T>. Einige tests:

[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));
}

InformationsquelleAutor Ohad Schneider