如何在javascript中统一两个树?

Question

我正在实现一个算法(Kruslkal)，需要在javascript中合并两个或多个二叉树，例如:

下面的树:

4
5 6

可以合并到以下树中:

2
1 3

…结果:

2
1 3
4 
5 6

我把二叉树的数据结构代码，但当我做了一个测试，在一个函数合并树，称为'合并'，什么都没有发生。第一个树没有合并到第二个树中，如果我尝试在'merge'函数中使用console.log，会出现以下消息:">Uncaught TypeError:树为空"。

有人能帮我一下吗?

function binarytree()
{
this.root = null;
this.add = function(value)
{
var node = {
value : value,
left : null,
right : null
};
var current;
if (this.root == null) this.root = node;
else
{
current = this.root;
while (1)
{
if (value < current.value)
{
if (current.left == null)
{
current.left = node;
break;
}
else current = current.left;
}
else if (value > current.value)
{
if (current.right == null)
{
current.right = node;
break;
}
else current = current.right;
}
else break;
}
}
}
this.search =  function(value)
{
var found = false,
current = this.root;
while (!found && current)
{
if (value < current.value) current = current.left;
else if (value > current.value) current = current.right;
else found = true;
}
return found;
}
this.print = function(no)
{
if (no)
{
this.print(no.left);
this.print(no.right);
console.log(no.value);
}
}
}
var tree = new binarytree();
var tree2 = new binarytree();
function merge(tree, tree2)
{
//console.log("tree.value " + tree.value);
if (tree == null) tree = tree2.root;
else if (tree.value < tree2.value) this.merge(tree.left, tree2);
else this.merge(tree.right, tree2);
}
tree.add(1);
tree.add(2);
tree.add(3);
console.log("First tree:");
tree.print(tree.root);
tree2.add(7);
tree2.add(8);
tree2.add(9);
console.log("Second tree:");
tree2.print(tree2.root);
merge(tree.root,tree2.root);
console.log("Merged trees:");
tree.print(tree.root);

Answer 1

查看您的代码，很明显您处理的不仅仅是任何二叉树，而是二进制搜索树。这些树确保节点的值永远不会小于左子节点的值，也永远不会大于右子节点的值。

你的例子因此没有被正确描绘。这不是一个二叉搜索树:

4
5 6

如果是:

5
4 6

此外，您的代码并没有创建这些树。相反，它创建了这些树:

1         and    7
2                8
3                9

如果你想创建更平衡的树，你应该改变插入的顺序。例如:

tree.add(2); // First!
tree.add(1);
tree.add(3);

这将创建:

2
1 3

的错误

…如果我尝试在'merge'函数中使用console.log，会出现以下消息:"Uncaught TypeError: tree is null"

这是预期的，因为您进行递归调用，如this.merge(tree.left, tree2),tree.left可以是null。即使在下一个语句中，您检查这种情况下使用if (tree == null)，所以您得到此错误是正常的。

但是你的代码显示你认为用tree = tree2.root;赋值给tree会以某种方式在tree中执行tree2的附加。但这只是对一个变量的赋值，而不是对树中节点的left或right属性的赋值，所以这个赋值对树没有任何影响。请记住，JavaScript传递值，因此当您将tree.left作为参数传递给函数时，可以确保在函数返回后tree.left仍将引用相同的对象。

简而言之，当您到达一个叶子时，而不是到达一个null时，您应该提前一步进行分配。像这样:

function merge(tree, tree2) {
if (tree2.value < tree.value) {
if (tree.left) {
this.merge(tree.left, tree2);
} else {
tree.left = tree2;
}
} else {
if (tree.right) {
this.merge(tree.right, tree2);
} else {
tree.right = tree2;
}
}
}

更深层次的问题

然而，虽然上面将执行一个简单的树到另一个树的附加，但它假设第一棵树的值的范围与第二棵树的值的范围不重叠。如果有重叠，这个过程将不会产生二叉搜索树。维护BST属性的合并需要将第二棵树的节点分布在第一棵树的不同位置。

一种方法是获取第二个树的每个值，并在第一个树上调用add(value)。这将工作得很好。它的时间复杂度为O(nlogm)，其中m是第一棵树的大小，n是第二棵树的大小。

如果树的大小具有可比性，那么当您在一次扫描中遍历第一个树，在经过正确的插入点时插入新节点时，您将获得更好的时间复杂度。时间复杂度为0 (m+n)。

实施

我会对你的代码做很多修改:

• 使用class语法…并在原型上定义方法，而不是在每个实例上定义方法
• 定义一个迭代器按顺序访问节点
• 避免add和search中的代码重复。
• 定义一个类来构造节点对象，而不是使用对象字面值
• …其他几个改进

在这里:

class Node { // Create a class for this
constructor(value, left=null, right=null) {
this.value = value;
this.left = left;
this.right = right;
}
* inorder() {
if (this.left) yield * this.left.inorder();
yield this.value;
if (this.right) yield * this.right.inorder();
}
}
class BinaryTree { // Use class syntax and PascalCase
constructor() {
this.root = null;
}
add(value) {
let [location, side] = this.locate(value);
if (side) location[side] = new Node(value); // Use constructor instead of plain object literal;
}
locate(value) { // Returns where node is or should be inserted
if (!this.root) return [this, "root"];
let current = this.root;
while (true) {
if (value < current.value) {
if (!current.left) return [current, "left"];
current = current.left;
} else if (value > current.value) {
if (!current.right) return [current, "right"];
current = current.right;
}
else return [current, ""];
}
}
search(value) {
return !this.locate(value)[1];
}
print() { // Use iterator to get the values
for (let value of this.inorder()) console.log(value);
}
* inorder(node) {
if (this.root) yield * this.root.inorder();
}
merge(otherTree) {
let values = otherTree.inorder();
let nextValue = values.next().value;

function recur(node, max) {
while (nextValue !== undefined && nextValue < max) {
if (nextValue < node.value) {
if (!node.left) {
node.left = new Node(nextValue);
nextValue = values.next().value;
}
recur(node.left, node.value);
} else if (nextValue > node.value) {
if (!node.right) {
node.right = new Node(nextValue);
nextValue = values.next().value;
}
recur(node.right, max);
} else {
nextValue = values.next().value;
}
}
}

recur(this.root, Infinity);
}
}
var tree = new BinaryTree();
var tree2 = new BinaryTree();
tree.add(2);
tree.add(4);
tree.add(6);
console.log("First tree:");
tree.print();
tree2.add(1);
tree2.add(3);
tree2.add(5);
console.log("Second tree:");
tree2.print();
tree.merge(tree2);
console.log("Merged trees:");
tree.print();