链表实现BST的节点邻接关系检测功能异常求助
你代码的问题出在Adjacent私有成员函数的实现上,存在两个逻辑错误:
- 子节点匹配条件多余:你在检查当前节点的子节点是否是目标节点时,强制要求当前节点的左右子节点都不为空才进行匹配。如果节点只有左孩子或者只有右孩子,就会直接跳过检查逻辑,自然检测不到相邻关系。
- 递归遍历逻辑错误:原代码用
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
相关产品推荐
相关产品推荐

