c++ - 搜索一棵树并计算您经过的城镇的距离

Question

这两个函数一起应该返回您必须经过的总距离才能直接到达节点。目前，它不适用于更长更复杂的事情。然而，简单的事情工作得很好。

    int Stree::distance(string origin_city, string destination_city)
{
    int total_distance = 0;
    Node *new_root = m_root;
    new_root = find_node(m_root, origin_city);
    total_distance = get_distance(new_root, total_distance, destination_city);
    return total_distance;
}

int Stree::get_distance(Node* cur, int distance, string destination)
{
    Node *tmp = cur;
    if(cur == NULL)
        return 0;
    if(cur->m_city == destination || tmp->m_city == destination)
    {
        //cout << distance + cur->m_parent_distance << endl;
        return distance += cur->m_parent_distance;
    }
    if(tmp->m_left != NULL)
    {
        //cout << "checking left" << endl;
        tmp = cur->m_left;
        return get_distance(cur->m_left, distance, destination) ;
    }
    else
    {
        //cout << "checking right" << endl;
        return get_distance(cur->m_right, distance, destination);
    }
}

Answer 1

只是一个猜测：我认为你的代码可以循环的唯一方法应该是当树包含循环时 - 即根本不是树。

试试这个调试助手：

#include <vector>
#include <algorithm>
#include <stdexcept>
using namespace std;
...
static vector<Node*> visited;

int Stree::get_distance(Node* cur, int distance, string destination)
{
    if (find(visited.begin(), visited.end(), cur) != visited.end())
        throw runtime_error("looping " + cur->m_city);

    Node *tmp = cur;
    if(cur == NULL)
        return 0;

    int ret;
    visited.push_back(cur);
    if(cur->m_city == destination || tmp->m_city == destination)
    {
        //cout << distance + cur->m_parent_distance << endl;
        ret = distance += cur->m_parent_distance;
    }
    if(tmp->m_left != NULL)
    {
        //cout << "checking left" << endl;
        tmp = cur->m_left;
        ret = get_distance(cur->m_left, distance, destination) ;
    }
    else
    {
        //cout << "checking right" << endl;
        ret = get_distance(cur->m_right, distance, destination);
    }

    visited.pop_back();
    return ret;
}