如何在JavaScript中合并两个树？

Question

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

以下是要合并的二叉树:

 4
5 6

可以合并到以下树中：

 2
1 3

... resulting:

 2
1 3

  4 
 5 6

我放置了二叉树数据结构的代码，但当我在函数中进行名为'merge'的树合并测试时，没有任何反应。第一棵树没有合并到第二棵树中，如果我尝试在函数'merge'中使用console.log，则会出现以下消息：" Uncaught TypeError: tree is null "。

有人可以帮我吗？

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);

- visionary

---

你是指二叉树还是二叉搜索树？同时，请提供出现错误的代码行。 - Abhinav Mathur

期望的输出不清楚，因为4出现在3的正下方。它是左侧还是右侧子依赖关系？由于您的代码实现了二叉搜索，第一棵树的输入（4,5,6）是如何正确的呢？它并不代表BST... - trincot

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是第二棵树的大小。

如果树的大小相当，那么当您在一遍遍历中通过正确的插入点插入新节点时，将获得更好的时间复杂度。这将具有O(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();

- trincot

---

Trincot，你的回答不仅仅是一个简单的答案，而是一个充满细节的详细解释，我们可以从中学到很多！上帝保佑你！ - visionary