二叉树存储坐标完成合并后搜索功能失效问题排查求助

你代码里的问题主要集中在三个核心逻辑错误：

• 坐标比较逻辑不符合二叉搜索树要求
  你当前使用||（或）判断节点走向的逻辑完全错误：

  // 错误写法
  if (i < current.y || j < current.x) // 往左走
  else if (i > current.y || j > current.x) // 往右走
  

  这种逻辑会导致大量坐标的插入路径和查询路径不一致：比如当前节点是(9,8)（x=9，y=8），要查询的节点是(8,5)，y=5<8满足第一个判断，会往左走；但如果插入时的父节点是(0,2)，x=8>0、y=5>2满足第二个判断，会往右走，自然出现节点存在但搜不到的情况。
  二叉搜索树的比较规则必须是全序的，比如优先按y排序，y相等再按x排序，正确的判断逻辑应该是：

  // 正确写法示例
  if (i < current.y || (i === current.y && j < current.x)) // 往左走
  else if (i > current.y || (i === current.y && j > current.x)) // 往右走
  

• 合并函数逻辑完全错误
  你当前的merge函数直接把第二棵树的根节点整体挂载到第一棵树的子节点位置，完全没有处理第二棵树的子节点，第二棵树的原有结构是适配自身根节点的排序规则的，挂载到第一棵树后整个子树的有序性全部被破坏，哪怕比较逻辑正确也会出现搜索失败的问题。
  正确的合并逻辑应该是遍历第二棵树的所有节点，逐个调用第一棵树的add方法插入，保证所有节点都符合第一棵树的排序规则。
• 变量作用域污染问题
  1. add方法没有定义参数，直接使用全局变量i、j取值，写法不规范且极易出现值被覆盖的问题。
  2. search方法里的current变量没有加var/let声明，会自动变成全局变量，多次调用搜索会互相干扰。
  3. 最后搜索使用的i、j是第二棵树插入循环最后一次赋值的值，若要验证所有节点存在，应该遍历所有节点逐一搜索。

function binarytree() {
  this.root = null;
  // 新增参数接收x,y
  this.add = function(x, y) {
    var node = {
      x: x,
      y: y,
      left: null,
      right: null
    };
    var current;
    if (this.root == null) this.root = node;
    else {
      current = this.root;
      while (1) {
        // 修正比较逻辑
        if (y < current.y || (y === current.y && x < current.x)) {
          if (current.left == null) {
            current.left = node;
            break;
          } else current = current.left;
        } else if (y > current.y || (y === current.y && x > current.x)) {
          if (current.right == null) {
            current.right = node;
            break;
          } else current = current.right;
        } else break;
      }
    }
  }

  this.search = function(i, j) {
    var found = false;
    // 声明局部current
    var current = this.root;
    while (!found && current) {
      if (i < current.y || (i === current.y && j < current.x)) current = current.left;
      else if (i > current.y || (i === current.y && j > current.x)) current = current.right;
      else found = true;
    }
    return found;
  }

  // 保留原print逻辑
  this.print = function(no) {
    if (no) {
      this.print(no.left);
      this.print(no.right);
      console.log(no.x, no.y);
    }
  }

  // 内置遍历节点方法，供合并使用
  this.traverse = function(callback, no) {
    if (no) {
      this.traverse(callback, no.left);
      callback(no.x, no.y);
      this.traverse(callback, no.right);
    }
  }
}

// 重写合并函数
function merge(tree1, tree2) {
  tree2.traverse(function(x, y) {
    tree1.add(x, y);
  }, tree2.root);
}

// 测试代码
var tree = new binarytree();
var tree2 = new binarytree();
// 存储第二棵树的所有节点用于验证
var testNodes = [];

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

for (x = 0; x < 4; x++) {
  let i = Math.floor(Math.random() * 10);
  let j = Math.floor(Math.random() * 10);
  tree2.add(j, i);
  testNodes.push({x:j, y:i});
}

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

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

// 验证所有第二棵树的节点都能搜到
testNodes.forEach(node => {
  if (tree.search(node.y, node.x)) {
    console.log(`FOUND VALUES ${node.x} AND ${node.y}`);
  } else {
    console.log(`VALUES ${node.x} AND ${node.y} NOT FOUND`);
  }
})

内容的提问来源于stack exchange，提问作者visionary