javascript - 如何在 javascript 中合并两棵树？

Question

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

下面的树:

 4
5 6

可以合并到下面的树中:

 2
1 3

...结果:

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

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

错误

...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 的赋值将以某种方式执行 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 语法...并在原型(prototype)上定义方法，而不是在每个实例上定义
• 定义一个迭代器以按顺序访问节点
• 避免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();