Ваш комментарий, который
char[] inorder = (new List<char>() { 'F','B','A','E','H','C','D','I','G'})
char[] preorder = (new List<char>() { 'H', 'B', 'F', 'E', 'A', 'C', 'D', 'G', 'I' })
В частности, тот факт, что inorder не является символом, не означающим, что вы действительно используете несортированное "Двоичное дерево" вместо "Двоичное дерево поиска" , которое подразумевал мой первоначальный ответ.
Так как построить двоичное дерево, которое соответствует заданным inorder и preorder? Идея основана на свойствах preorder и inorder для двоичного дерева поиска, упомянутых в исходном ответе. В частности:
- Если вы вставите значения в BST в порядке, указанном в
preorder, вы получите дерево с этим предзаказом
- Для BST-заказа обход узлов в порядке сортировки
Таким образом, простой способ создать такой BT - это построить его как BST, вставляя значения в порядке preorder и (здесь хитрый бит), используя inorder в качестве порядка сортировки. Другими словами, вы забываете о любой «естественной» сортировке и используете поддельную, которая точно отражает inorder.
Внешняя итерация, очевидно, итеративна. Типичная реализация значения вставки является хвостовой рекурсией, поэтому ее легко преобразовать в итерационный код. Вот полный код:
class BinaryTreeNode<T>
{
public readonly T value;
public BinaryTreeNode<T> left = null;
public BinaryTreeNode<T> right = null;
public BinaryTreeNode(T value)
{
this.value = value;
}
public void InsertValue(T newValue, Comparer<T> comparer)
{
InsertValueNR(this, newValue, comparer);
}
private static void InsertValueNR(BinaryTreeNode<T> start, T newValue, Comparer<T> comparer)
{
for (BinaryTreeNode<T> cur = start; ;)
{
int cmp = comparer.Compare(cur.value, newValue);
if (cmp == 0)
throw new InvalidOperationException("value '" + newValue + "' is duplicated in the tree");
else if (cmp < 0)
{
if (cur.left == null)
{
cur.left = new BinaryTreeNode<T>(newValue);
return;
}
else
cur = cur.left;
}
else
{
if (cur.right == null)
{
cur.right = new BinaryTreeNode<T>(newValue);
return;
}
else
cur = cur.right;
}
}
}
private void InsertValueRecursive(T newValue, Comparer<T> comparer)
{
int cmp = comparer.Compare(value, newValue);
if (cmp == 0)
throw new InvalidOperationException("value '" + newValue + "' is duplicated in the tree");
else if (cmp < 0)
{
if (left != null)
left.InsertValueRecursive(newValue, comparer);
else
left = new BinaryTreeNode<T>(newValue);
}
else
{
if (right != null)
right.InsertValueRecursive(newValue, comparer);
else
right = new BinaryTreeNode<T>(newValue);
}
}
class OrderComparer<T> : Comparer<T>
{
private readonly Dictionary<T, int> positions;
public OrderComparer(List<T> order)
{
positions = new Dictionary<T, int>();
for (int i = 0; i < order.Count; i++)
{
positions[order[i]] = i;
}
}
public override int Compare(T x, T y)
{
return -Comparer<int>.Default.Compare(positions[x], positions[y]);
}
}
public static BinaryTreeNode<T> ConstructTree(List<T> preorder, List<T> inorder)
{
var comparer = new OrderComparer<T>(inorder);
var root = new BinaryTreeNode<T>(preorder[0]);
for (int i = 1; i < preorder.Count; i++)
{
root.InsertValue(preorder[i], comparer);
}
return root;
}
public void PrintPreOrder()
{
PreOrder(ch => Console.Write(ch + " "));
Console.WriteLine();
}
public void PrintInOrder()
{
InOrder(ch => Console.Write(ch + " "));
Console.WriteLine();
}
public void PreOrder(Action<T> visitor)
{
visitor(value);
if (left != null)
left.PreOrder(visitor);
if (right != null)
right.PreOrder(visitor);
}
public void InOrder(Action<T> visitor)
{
if (left != null)
left.InOrder(visitor);
visitor(value);
if (right != null)
right.InOrder(visitor);
}
}
Наиболее важной его частью является пользовательский OrderComparer, который используется вместо «естественного» порядка char. Также я оставил как нерекурсивный InsertValueNR, так и рекурсивный InsertValueRecursive, чтобы показать, как легко преобразовать последнее в первое.
Тестовый пример:
var inorder = new List<char>() { 'F', 'B', 'A', 'E', 'H', 'C', 'D', 'I', 'G' };
var preorder = new List<char>() { 'H', 'B', 'F', 'E', 'A', 'C', 'D', 'G', 'I' };
var root = BinaryTreeNode<char>.ConstructTree(preorder, inorder);
root.PrintInOrder();
root.PrintPreOrder();
Я получаю
F B A E H C D I G
H B F E A C D G I
Оригинальный ответ (для BST)
Примечание : В этом первоначальном ответе предполагалось, что термин "Двоичное дерево" здесь фактически означает "Двоичное дерево поиска" , то есть отсортированное.
Вы уверены, что хотите построить дерево по предварительному заказу и порядку одновременно? Если вы посмотрите на ответ в связанном вопросе, вы можете обнаружить, что один предварительный заказ полностью определяет дерево: вы просто делаете обычные вставки в дерево данных в указанном вами порядке. Тогда вы можете только проверить, соответствует ли он указанному порядку или нет. Вы не можете построить любое другое дерево с таким же предварительным заказом. Но на самом деле вы можете просто проверить, отсортирован ли порядок или нет: если он отсортирован - он совпадет. Если он не отсортирован - это недопустимый порядок для любого дерева.
Что касается порядка, существует очень простой способ построить очень неэффективное, но все еще технически правильное двоичное дерево: поместить первое значение в корень, а затем добавить каждое следующее значение в качестве его правого потомка. Это дерево явно соответствует порядку. Это практически то же самое, что построить дерево, используя порядок в качестве предварительного заказа.
На самом деле вы можете просто сделать произвольную случайную последовательность данных в массиве inorder и вставить их в этом порядке (как если бы это был предварительный порядок). Дело в том, что любое допустимое двоичное дерево с одинаковым содержимым (т. Е. Одинаковым набором значений во всех узлах, но, возможно, с различной внутренней структурой) будет иметь один и тот же порядок следования только по определению этого порядка.