算法-如何合并两个二分查找树。

算法-如何合并两个二分查找树。

瑾兮 发布于 2017-02-03 字数 53 浏览 1155 回复 2

空间和时间复杂度不好估计,当然求一个最优思路。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

夜无邪 2017-04-28 2 楼

分享一个递归算法:

template<class T>
class BinaryTree
{
struct Node
{
T data;
Node * left, * right;
} * root;
public:
void add(const T & value);
void combine(Node * r);
};

template<class T>
void BinaryTree<T>::combine(Node * r)
{
if(r == 0)return;
if(r->left != 0)combine(r->left);
if(r->right != 0)combine(r->right);
add(r->data);
}

泛泛之交 2017-04-20 1 楼

分三步:
1.将二叉树转换成已序链表。
2.将两个已序链表合并成一个链表。
3.将合并后的链表再次转换成二叉查找树。