算法 – 如何使用{pre,in,post}顺序遍历结果重建BST

我们知道预订,有序和后期遍历.什么算法会重建BST？ 因为它是BST,所以可以从预订单或订单后的顺序排序< 1>.实际上,只需要预购或后订单….

&LT 1为卤素;如果你知道比较函数是什么

从预订和有序,到构建二叉树

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

这背后的理由：

In pre-order, the first node is the root. Find the root in the in-order. Then the tree can be divided into left and right. Do it recursively.

类似于下订单和有序.