You need to enable JavaScript to run this app. 链表实现BST的节点邻接关系检测功能异常求助
优惠活动
大模型
产品
解决方案
定价
更多

链表实现BST的节点邻接关系检测功能异常求助

你代码的问题出在Adjacent私有成员函数的实现上,存在两个逻辑错误:

  1. 子节点匹配条件多余:你在检查当前节点的子节点是否是目标节点时,强制要求当前节点的左右子节点都不为空才进行匹配。如果节点只有左孩子或者只有右孩子,就会直接跳过检查逻辑,自然检测不到相邻关系。
  2. 递归遍历逻辑错误:原代码用else if判断右子树的遍历条件,只要左子树存在,就永远不会遍历右子树,右子树上的所有相邻关系都无法检测。

修复方案

替换原有的Adjacent函数实现即可:

template <typename T>
void BST<T>::Adjacent(const string & u, const string& v, std::unique_ptr<TreeNode>& node ) {
    // 节点为空或者已经找到匹配就直接返回,避免无效遍历
    if (node == nullptr || adjacent_found) {
        return;
    }
    // 检查左孩子是否匹配
    if (node->left != nullptr) {
        if ((node->name == u && node->left->name == v) || (node->name == v && node->left->name == u)) {
            adjacent_found = true;
            return;
        }
        Adjacent(u, v, node->left);
    }
    // 检查右孩子是否匹配
    if (node->right != nullptr) {
        if ((node->name == u && node->right->name == v) || (node->name == v && node->right->name == u)) {
            adjacent_found = true;
            return;
        }
        Adjacent(u, v, node->right);
    }
}

其他可选优化

你类中的leaves、edges是成员变量,每次调用get_leaves、get_edges时如果不清空,多次调用会出现重复数据,建议修改对应接口:

template <typename T>
vector<string> BST<T>::get_leaves() {
    leaves.clear();
    extract_leaf_nodes(this->root);
    return leaves;
}

template <typename T>
vector<pair<string,string>> BST<T>::get_edges() {
    edges.clear();
    edge_retrieval(this->root);
    return edges;
}

另外注意你给出的测试用例中,v2和v10并不是父子关系,本身就不相邻,如果是v3和v10才是相邻关系,可以自己验证下。

内容的提问来源于stack exchange,提问作者Lachlan Alcott

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.21 09:36:05