转换二叉树 - > BST（保持原始树形状）

我有一棵二叉树某种形状。我想将它转换成BST搜索树相同形状。可能吗？转换二叉树 - > BST（保持原始树形状）

我试过类似的方法 -

做阶的二叉树&放内容穿越到一个数组。然后将此映射到BST中并记住该条件（左值为< = root < =右val）。这适用于某些情况，但对其他人无效。

P.S .:我看看这个 - Binary Trees question. Checking for similar shape。但很容易比较两个BST在形状上的相似性。

2010-08-20 Srikar Appalaraju

简短的回答是：你不能。 BST要求节点遵循左边< =当前<的规则。在你链接的例子中：http://upload.wikimedia.org/wikipedia/commons/f/f7/Binary_tree.svg，如果你尝试使用相同的shap来构建BST，你会发现你不能。

但是，如果你想舒展BST的定义，以便它允许左< =当前< =权（注意，这里目前< =权限被允许，并列为对更严格的定义），您可以。对所有元素进行排序并将它们粘贴到一个数组中。现在进行按顺序遍历，用数组中的每个元素替换节点上的值。这里有一些伪代码：

// t is your non-BST tree, a is an array containing the sorted elements of t, i is the current index into a 
index i = 0 
create_bst(Tree t, Array a) 
{ 
    if(t is NIL) 
    return; 
    create_bst(t->left, a) 
    t->data = a[i] 
    i++ 
    create_bst(t->right, a) 
}

但结果不是真正的BST。如果你想要一个真实的BST尽可能接近原始形状，那么你再次将这些元素放入一个有序数组中，但是这次将它们插入到BST中。插入它们的顺序由原始树的子树的大小来定义。这里有一些伪代码：

// left is initially set to 0 
create_true_bst(Tree t, BST bt, array a, index left) 
{ 
    index i = left + left_subtree(t)->size 
    bt->insert(a[i]) 
    if(left_subtree(t)->size != 0) 
    { 
    create_true_bst(t->left, bt, a, left) 
    create_true_bst(t->right, bt, a, i + 1) 
    } 
}

但是这并不能保证形状是相同的。

来源

2010-08-20 15:39:12

如果您正确实施，则描述的方法可以保证正常工作。二叉树上的遍历顺序是唯一的，并定义了元素的顺序。如果通过价值元素进行排序，然后根据该排序他们坚持的话，那将永远是真实的，

left subtree <= root <= right subtree

为每个节点，因为这是你遍历的顺序，并考虑到你按顺序对它们进行了排序。

来源

2010-08-20 14:11:38

我试过了。也许我在做一些简单的错误。让我们看看这里提供的二叉树 - http://upload.wikimedia.org/wikipedia/commons/f/f7/Binary_tree.svg 在按顺序遍历后，我得到了（2,7,5,6,11， 2,5,4,9）作为阵列。在排序之后呢？不排序会使一切增加吗？然后BST最终会成为一个链表？ – 2010-08-20 14:36:47

排序得到（2,2,4,5,5,6,7,9,11）。按照您在树中读取它们的相同顺序放置，即2→2→7→2→5→4→6→5→11→5→2→6→5→7， 4-> 9,9-> 11。那么你的树看起来像6，L（2，L（2），R（5，L（5），R（5））），R（9，L（7），R（11））。 – 2010-08-20 17:54:58

我只是做两个按顺序遍历。在第一次遍历中，从树中获取值并将它们放入堆中。在第二个中，从堆中获取值并将其放入树中。这运行在O（n＆middot; log n）时间和O（n）空间。

来源

2010-08-20 14:48:23 Svante

提取树的所有元素，然后对其进行排序，然后使用递归inorder过程来替换值。

来源

2013-11-22 12:16:01 user3021620

转换二叉树 - > BST（保持原始树形状）

回答

相关问题