无序二叉树遍历

Unordered Binary Tree Traversal

对于class,我必须创建一个状态对象的二叉树,每个状态对象都包含一个常驻对象的二叉树,组织居住在每个状态的人。我正在尝试搜索给定州的最年长居民;然而,居民是按字母顺序排列在树中的,这对我的搜索毫无帮助。因此,我必须遍历整个居民树,更新保存最年长者的节点,并在树完全遍历后 return 它。我有我的代码的第一部分,但我仍然坚持如何编写递归的其余部分。

状态树的方法:

node <Person*> * findoldest (int obd, node <Person*> * oldest, node <Person*> * n)
{   
    //FINAL WORKING CODE
    if (root == NULL)
        return NULL;

    if (n == NULL)
        return NULL;

    else
    {
        if (n->data->birthday < obd)
        {
            obd = n->data->birthday; 
            oldest = n; 
        }
        node <Person*> * o_left = findoldest(obd, oldest, n->left);
        node <Person*> * o_right = findoldest(obd, oldest, n->right);
        node <Person*> * res;
        if (o_right && o_left)
            if (o_right->data->birthday < o_left->data->birthday)
                res = o_right;
            else
                res = o_left;
        else
            res = (o_right != NULL ? o_right : o_left);
        if (res && oldest)
            if (res->data->birthday < oldest->data->birthday)
                return res;
            else
                return oldest;
        else 
            return ((res != NULL ? res : oldest));
    }
}

然后public "wrapper"状态树方法:

node <Person*> * findoldest ()
{   int oldest_bday = root->data->birthday; 
    node <Person*> * oldest_person = root;
    findoldest(oldest_bday, oldest_person, root); 
}

这是您需要的伪代码:

node <Person*> * findoldest (node <Person*> * n)
{
    if n->right != null :
        right_oldest = findoldest(n->right)

    if n->left != null:
        left_oldest = findoldest(n->left)

    return the node that has max value in (right_oldest.data.birthday, left_oldest.data.birthday, n.data.birthday)

}

基本上,它与您上一个 post 的答案相同。

right_old = findoldestn(n->right);
left_old = findoldestn(n->left);

然后找出 left/right 和当前值之间最旧的值,以及 return 那个值。这可以用

来实现
res = (right_old->age > left_old->age ? right_old : left_old);
finalRet = (res->age > oldest->age ? res : oldest);
return (finalRet);

或等同于 if 符号:

    if (right_old->age >left_old->age)
        res = right_old;
    else
        res = left_old;
    if (res->age > oldest->age)
        finalRes = res;
    else
        finalRes = oldest;

顺便说一句,我比较懒,variable->age相当于variable->data->birthday