c++ - 合并两个二叉搜索树

Question

可能重复：
我如何合并两个二叉树

我是树代码的新手，有人要求我编写一个代码，通过编写一个函数来合并两个二叉搜索树

void mergeBst (BST & othertree)

此函数将接收另一个 Bst 并将该树中的所有非冗余值插入到当前树中，您能告诉我该怎么做吗？

Answer 1

使用两棵树创建两个排序列表。这将是 O(m+n)。然后合并两个保持顺序的排序列表。(O(m+n)) 使用合并的列表创建组合树。(O(m+n))

或者简单地为输入树中的每个节点，找到将节点插入源树的位置。然后插入它。

我如何合并两个二叉树

如何有效地合并两个 BST？

Answer 2

将树 B 合并到树 A ( A.mergeBst(B))：

比较 B 的根和 A 的根。
如果 B 的根更大，则合并B.left到 A，其余的 B 到A.right。
如果小于，则合并B.right到 A 中，将 B 的其余部分合并到A.left.
如果它们相等，则合并B.left到A.left，B.right到A.right，并丢弃 B 的根。

Answer 3

考虑两个二叉搜索树：

1. Source - 您将在其上迭代的 BST
2. Target - 您希望添加源值的 BST

有一个非常简单的算法。

对于源搜索中的每个“值”，如果它们在目标中，则丢弃它们，如果不插入它们。

编辑：“迭代”我的意思是：http ://en.wikipedia.org/wiki/Tree_traversal

预购迭代：

1. 访问根。
2. 遍历左子树。
3. 遍历右子树。