二进制文件中的搜索坐标无法正常工作

Question

我需要在二叉树中插入很多坐标，有时还要合并它们。我正在测试该程序一段时间，发现搜索功能有时不起作用。

在这个例子中，我创建了两个二叉树，将它们合并并搜索了一些坐标，但是没有找到插入树中的坐标：

First tree:
0 2
9 8
7 0
6 0
Second tree:
3 2
8 5
4 1
5 6
Merged trees:
3 2
8 5
4 1
5 6
0 2
9 8
7 0
6 0
VALUES 8 and 5 NOT FOUND

有人可以帮我解决这个问题吗？

代码如下：

function binarytree()
{
  this.root = null;
  this.add = function()
  {
    var node = {
                 x : j,
                 y : i,
                 left : null,
                 right : null
               };
    var current;
    if (this.root == null) this.root = node;
      else {
             current = this.root;
             while (1)
             {
               if (i < current.y || j < current.x) {
                  if (current.left == null) {
                      current.left = node;
                      break;
                  }
                   else current = current.left;
               }
               else if (i > current.y || j > current.x) {
                       if (current.right == null) {
                           current.right = node;
                           break;
                       }
                       else current = current.right;
                    }
                    else break;
             }
           }
  }

  this.search = function(tree, i, j) {
    var found = false;
    current = tree.root;
    while (!found && current) {
      if (i < current.y || j < current.x) current = current.left;
        else if (i > current.y || j > current.x) 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.x, no.y);
    }
  }
}

function merge(tree, tree2) {
    if (tree2.x < tree.x || tree2.y < tree.y) {
        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;
        }
    }
}
  var i, j;
  var tree = new binarytree();
  var tree2 = new binarytree();

  for (x = 0; x < 4; x++)
  {
     i = Math.floor(Math.random() * 10);
     j = Math.floor(Math.random() * 10);
     tree.add();
  }

  for (x = 0; x < 4; x++)
  {
     i = Math.floor(Math.random() * 10);
     j = Math.floor(Math.random() * 10);
     tree2.add();
  }

  console.log("First tree:");
  tree.print(tree.root);
  console.log("Second tree:");
  tree2.print(tree2.root);

  merge(tree.root,tree2.root);
  console.log("Merged trees:");
  tree.print(tree.root);

  if (tree.search(tree, i, j) == true) console.log("FOUND VALUES " + j + " AND " + i);
    else console.log("VALUES " + j + " AND " + i + " NOT FOUND");

Answer 1

正如您在 deleted question 中已经提到的，您需要为此使用 KD 树，因为普通的二叉搜索树适用于一维值，而不是二维值。

您的代码中存在几个问题：

将点分成两类的方式不是传递操作。假设你在一棵树中有两个点：(0, 0) 和 (10, -5)，那么第二个点将存储在根的 left 属性中。这是因为 -5 小于 0。现在我们有了第二棵有两个点的树：(4, 4) 和 (10, -5)。出于同样的原因，该树将具有与第一个相同的结构。您的 merge 函数会将第二棵树放在第一棵树根的 right 属性中。这是因为 (4, 4) 被认为是 (0, 0) 的“右”。现在请注意这是多么不一致：现在我们在合并树的左右子树中都有一个 (10, -5)！发生这种情况是因为您比较点的方式不是传递比较。
以上是主要问题，但也要注意 if (i < current.y || j < current.x) 平均在 75% 的情况下是正确的。这是这个比较方法不对的第二个原因。

在 KD 树中比较 2D 点的方法是交替与 X 坐标或 Y 坐标进行比较。所以在树的顶层你会比较 Y 坐标来决定是向左还是向右，在下一层你会比较 X 坐标。然后再次更深一层，您将再次比较 Y 坐标，...等

其他一些说明：

使用class语法
也为节点实例创建构造函数
不要在方法中打印，而是定义一个生成器来生成所有值，以及一个 toString 方法并在主程序中打印该字符串。
避免使用全局变量：您的 add 方法应该将 i 和 j 作为参数，并且您应该始终声明变量（您没有使用 var current在 search 中，也不是在主代码中的 x 和 y 中）：如果您想编写可靠的代码，这是至关重要的。考虑使用 "use strict"，它会提醒您此类问题。
add 和 search 将使用类似的方式在树中导航，因此将它们共有的代码放在一个单独的函数中，我们可以将其称为 locate .
据我所知，没有办法按照您想象的方式合并 KD 树，您可以决定将第二棵树的“其余部分”放在第一棵树的叶节点下。所以我建议只迭代第二棵树的节点并将它们一个一个地插入到第一棵树中。

这是建议的代码：

"use strict"; // To help avoid all kinds of problems

class Node { // Use a class for creating node instances
    constructor(i, j) {
        this.x = i;
        this.y = j;
        this.left = null;
        this.right = null;
    }
    * inorder() { // Generator to visit all nodes
        if (this.left) yield * this.left.inorder();
        yield [this.x, this.y];
        if (this.right) yield * this.right.inorder();
    }
}

class BinaryTree {
    constructor() {
        this.root = null;
    }
    locate(i, j) { // A common function to avoid code repetition
        if (this.root == null) return [null, "root"];
        let current = this.root;
        let axis = "x";
        let otherAxis = "y";
        while (true) {
            // alternate the axis:
            [axis, otherAxis, i, j] = [otherAxis, axis, j, i];
            if (i < current[axis]) {
                if (current.left == null) return [current, "left"];
                current = current.left;
            } else if (i > current[axis] || j != current[otherAxis]) {
                if (current.right == null) return [current, "right"];
                current = current.right;
            } else { // point is already in the tree
                return [current, "equal"]; 
            }
        }
    }
    add(i, j) { // this method should have parameters
        if (this.root == null) {
            this.root = new Node(i, j); // Use constructor for creating node
        } else {
            const [current, side] = this.locate(i, j);
            if (side !== "equal") {
                current[side] = new Node(i, j);
            }
        }
    }
    search(i, j) {
        const [_, side] = this.locate(i, j);
        return side === "equal";
    }
    * inorder() {
        if (this.root) yield * this.root.inorder();
    }
    mergeWith(otherTree) {
        // Insert all the other nodes one by one:
        for (let point of otherTree.inorder()) {
            this.add(...point);
        }
    }
    toString() { // Don't print, but produce string
        return JSON.stringify(Array.from(this.inorder()));
    }
}

const tree = new BinaryTree();
for (const point of [[0, 2], [9, 8], [7, 0], [6, 0]]) tree.add(...point);
const tree2 = new BinaryTree();
for (const point of [[3, 2], [8, 5], [4, 1], [5, 6]]) tree2.add(...point);
console.log("First tree:");
console.log(tree.toString());
console.log("Second tree:");
console.log(tree2.toString());
tree.mergeWith(tree2);
console.log("Merged trees:");
console.log(tree.toString());

// Check that all points are found:
for (const point of tree.inorder()) {
    console.log(...point, tree.search(...point));
}

二进制文件中的搜索坐标无法正常工作

Search coordinates in a binary not working correctly

javascript

binary-tree

coordinates