как перестроить BST, используя результаты прохождения порядка {pre, in, post}

Question

Мы знаем, как проходить предварительный заказ, обратный и последующий заказ. Какой алгоритм реконструирует BST?

Answer 1

Поскольку это BST, in-order можно отсортировать по pre-order или post-order <1>. На самом деле, pre-order или post-order требуется только ....

<1>, если вы знаете, что такое функция сравнения

---

С pre-order и in-order, чтобы построить двоичное дерево

BT createBT(int* preOrder, int* inOrder, int len)
{
    int i;
    BT tree;
    if(len <= 0)
        return NULL;
    tree = new BTNode;
    t->data = *preOrder;
    for(i = 0; i < len; i++)
        if(*(inOrder + i) == *preOrder)
            break;
    tree->left = createBT(preOrder + 1, inOrder, i);
    tree->right = createBT(preOrder + i + 1, inOrder + i + 1, len - i - 1);
    return tree;
}

Обоснование этого:

В предварительном порядке первый узел является корневым. Найти рут в порядке. Тогда дерево можно разделить на левое и правое. Сделай это рекурсивно.

Аналогично для post-order и in-order.

Answer 2

Вот рекурсивное решение Ruby

def rebuild(preorder, inorder)
  root = preorder.first
  root_inorder = inorder.index root
  return root unless root_inorder
  root.left = rebuild(preorder[1, root_inorder], inorder[0...root_inorder])
  root.right = rebuild(preorder[root_inorder+1..-1], inorder[root_inorder+1..-1])
  root
end

И пример

class Node
  attr_reader :val
  attr_accessor :left, :right

  def initialize(val)
    @val = val
  end

  def ==(node)
    node.val == val
  end

  def inspect
    "val: #{val}, left: #{left && left.val || "-"}, right: #{right && right.val || "-"}"
  end
end

inorder = [4, 7, 2, 5, 1, 3, 8, 6, 9].map{|v| Node.new v }
preorder = [1, 2, 4, 7, 5, 3, 6, 8, 9].map{|v| Node.new v }

tree = rebuild(preorder, inorder)
tree
# val: 1, left: 2, right: 3
tree.left
# val: 2, left: 4, right: 5
tree.left.left
# val: 4, left: -, right: 7

Answer 3

Для восстановления бинарного дерева требуется либо предзаказ + порядок, либо порядок + порядок. Как уже указывалось для BST, мы можем реконструировать, используя либо предварительный заказ, либо почтовый заказ, так как сортировка любого из них даст нам порядок.

Вы можете использовать следующую функцию, которая является модификацией кода, заданного @brainydexter, чтобы восстановить дерево без использования статической переменной:

struct node* buildTree(char in[],char pre[], int inStrt, int inEnd,int preIndex){

    // start index > end index..base condition return NULL.
    if(inStrt > inEnd)
        return NULL;

    // build the current node with the data at pre[preIndex].
    struct node *tNode = newNode(pre[preIndex]);

    // if all nodes are constructed return. 
    if(inStrt == inEnd)
        return tNode;

    // Else find the index of this node in Inorder traversal
    int inIndex = search(in, inStrt, inEnd, tNode->data);

    // Using index in Inorder traversal, construct left and right subtress
    tNode->left = buildTree(in, pre, inStrt, inIndex-1,preIndex+1);
    tNode->right = buildTree(in, pre, inIndex+1, inEnd,preIndex+inIndex+1);

    return tNode;
}

Answer 4

Я лично нашел ответ Данте немного сложным для подражания. Я прошел через решение и обнаружил, что он похож на тот, который выложен здесь http://geeksforgeeks.org/?p=6633

Сложность O (N ^ 2).

Вот еще один подход для построения дерева с использованием обхода после заказа: http://www.technicallyidle.com/2011/02/15/build-binary-search-tree-using-post-order-traversal-trace/

Надеюсь, это поможет