如何在 javascript 中合并两棵树？
How can I unite two trees in javascript?
我正在实现一个算法 (Kruslkal)，它需要在 javascript 中合并两个或多个二叉树，例如：
以下树：
4
5 6
可以合并到以下树中：
2
1 3
... 结果：
2
1 3
4
5 6
我放置了二叉树数据结构代码，但是当我在一个名为“merge”的合并树的函数中进行测试时，没有任何反应。第一棵树没有合并到第二棵树中，如果我尝试在函数 '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);
查看您的代码，很明显您处理的不仅仅是任何二叉树，而是二叉 search 树。这些树确保节点的值永远不会小于其左子节点的值，并且永远不会大于其右子节点的值.
因此，您的示例未正确描绘。这不是二叉搜索树：
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
错误
...if I try to use console.log in the function 'merge', the following message appears: "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;
}
}
}
更深层次的问题
但是，虽然上面将执行一棵树与另一棵树的简单连接，但它假定第一棵树的值范围与第二棵树的值范围不重叠。如果存在重叠，此过程将不会生成二叉 search 树。维护 BST 属性 的合并将需要将第二棵树的节点分布在第一棵树的不同位置。
一种方法是获取第二棵树的每个值并在第一棵树上调用 add(value)。这会很好用。它的时间复杂度为 O(nlogm)，其中 m 是第一棵树的大小，n 是第二棵树的大小。
如果树的大小相当，当您一次扫描遍历第一棵树时，您将获得更好的时间复杂度，并在经过正确的插入点时插入新节点。这将具有 O(m+n) 的时间复杂度。
实施
我会对你的代码做很多改动：
- 使用
class 语法...并在原型上定义方法，而不是在每个实例上定义方法
- 定义一个迭代器以按顺序访问节点
- 避免
add和search中的代码重复。
- 定义一个 class 来构造节点对象，而不是为此使用对象文字
- ...其他几项改进
这里是：
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();
我正在实现一个算法 (Kruslkal)，它需要在 javascript 中合并两个或多个二叉树，例如：
以下树：
4
5 6
可以合并到以下树中：
2
1 3
... 结果：
2
1 3
4
5 6
我放置了二叉树数据结构代码，但是当我在一个名为“merge”的合并树的函数中进行测试时，没有任何反应。第一棵树没有合并到第二棵树中，如果我尝试在函数 '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);
查看您的代码，很明显您处理的不仅仅是任何二叉树，而是二叉 search 树。这些树确保节点的值永远不会小于其左子节点的值，并且永远不会大于其右子节点的值.
因此，您的示例未正确描绘。这不是二叉搜索树：
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
错误
...if I try to use console.log in the function 'merge', the following message appears: "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;
}
}
}
更深层次的问题
但是，虽然上面将执行一棵树与另一棵树的简单连接，但它假定第一棵树的值范围与第二棵树的值范围不重叠。如果存在重叠，此过程将不会生成二叉 search 树。维护 BST 属性 的合并将需要将第二棵树的节点分布在第一棵树的不同位置。
一种方法是获取第二棵树的每个值并在第一棵树上调用 add(value)。这会很好用。它的时间复杂度为 O(nlogm)，其中 m 是第一棵树的大小，n 是第二棵树的大小。
如果树的大小相当，当您一次扫描遍历第一棵树时，您将获得更好的时间复杂度，并在经过正确的插入点时插入新节点。这将具有 O(m+n) 的时间复杂度。
实施
我会对你的代码做很多改动：
- 使用
class语法...并在原型上定义方法，而不是在每个实例上定义方法 - 定义一个迭代器以按顺序访问节点
- 避免
add和search中的代码重复。 - 定义一个 class 来构造节点对象，而不是为此使用对象文字
- ...其他几项改进
这里是：
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();