多字段（ID/片名/地区）二叉搜索树插入函数运行异常，求排查

问题背景 #

正在实现一个向二叉搜索树插入节点的函数，节点包含ID、电影片名和地区信息。程序可运行但输出结果不符合预期，多次调整未解决；观察到同类问题多使用单个参数作为排序依据，对此存在困惑。

当前代码 #

void BinarySearchTree::insert(string id, string title, string region, Node* currentNode = NULL) {
      if (currentNode == NULL) {
          currentNode = (*this).root; 
      }
   
      if (currentNode == NULL) {
          root = newNode(id, title, region);
          numberNodes++;
      } else if (title == currentNode->movieTitle && id == currentNode->titleID && region == currentNode->region) {
          cout << "Duplicate movie: " << title << " " << id << " " << region << endl;
            
      } else if (title < currentNode->movieTitle || (title == currentNode->movieTitle && id < currentNode->titleID) || (title == currentNode->movieTitle && id == currentNode->titleID && region < currentNode->region)) {
          if (currentNode->left == NULL) {
              currentNode->left = newNode(id, title, region);
              numberNodes++;
          } else {
              insert(id, title, region, currentNode->left);
          }
      } else {
          if (currentNode->right == NULL) {
              currentNode->right = newNode(id, title, region);
              numberNodes++;
          } else {
              insert(id, title, region, currentNode->right);
          }
      }
  }

核心问题排查与修复建议 #

• 优先检查newNode参数匹配
  这是最易引发错误的环节：确保newNode(id, title, region)将参数正确映射到节点成员变量——id赋值给titleID，title赋值给movieTitle，region赋值给region。若参数顺序颠倒（比如将title传给titleID），会导致整个排序逻辑完全混乱，直接引发插入位置错误。

• 重构排序比较逻辑以提升可读性与正确性
  当前用||连接多层级比较条件的写法易混淆，建议拆分为层级递进的判断逻辑，清晰体现“片名优先、其次ID、最后地区”的排序优先级：

  // 替换原有的else if及else分支
  else if (title < currentNode->movieTitle) {
      // 片名更小，插入左子树
      insertOrRecurseLeft(currentNode, id, title, region);
  } else if (title == currentNode->movieTitle) {
      if (id < currentNode->titleID) {
          // 片名相同、ID更小，插入左子树
          insertOrRecurseLeft(currentNode, id, title, region);
      } else if (id == currentNode->titleID) {
          if (region < currentNode->region) {
              // 片名、ID相同，地区更小，插入左子树
              insertOrRecurseLeft(currentNode, id, title, region);
          } else if (region != currentNode->region) {
              // 片名、ID相同，地区更大，插入右子树
              insertOrRecurseRight(currentNode, id, title, region);
          }
          // 地区相等的重复情况已在前面判断
      } else {
          // 片名相同、ID更大，插入右子树
          insertOrRecurseRight(currentNode, id, title, region);
      }
  } else {
      // 片名更大，插入右子树
      insertOrRecurseRight(currentNode, id, title, region);
  }
  
  // 提取重复逻辑为辅助函数，减少代码冗余
  void BinarySearchTree::insertOrRecurseLeft(Node* node, string id, string title, string region) {
      if (node->left == NULL) {
          node->left = newNode(id, title, region);
          numberNodes++;
      } else {
          insert(id, title, region, node->left);
      }
  }
  
  void BinarySearchTree::insertOrRecurseRight(Node* node, string id, string title, string region) {
      if (node->right == NULL) {
          node->right = newNode(id, title, region);
          numberNodes++;
      } else {
          insert(id, title, region, node->right);
      }
  }
  

  这种拆分写法不仅逻辑直观，还能减少重复代码，便于排查某一层级的比较错误。

• 验证字符串比较行为
  C++中string的<运算符基于ASCII字典序进行大小写敏感比较。若业务场景需要忽略大小写或自然排序，需自定义比较函数，否则会出现不符合预期的排序结果（例如大写字母开头的字符串会排在小写字母开头的字符串前面）。

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