原始树的子树

Question

当我尝试执行以下操作时遇到问题： (1) 找到原树根的左子树中最大的info字段 (2)找到原树根的右子树中最小的info字段。

我的代码可以编译，但执行时会出现错误，并且我不清楚 maxleftsubtree() 和 minrightsubtree() 函数中发生了什么。任何建议将不胜感激。

我当前的代码：

#include <iostream>
#include <string>

using namespace std;

class Tnode {
    public:
        Tnode *left;
        string info;
        Tnode *right;
        Tnode(string info = "", Tnode* left = NULL, Tnode* right = NULL) :
            info(info), left(left), right(right) {}
};
class BST {
    public:
        BST() : theroot(NULL) {}
        void insert(string x);
        void inorderprint();
        void preorderprint();
        void postorderprint();
        void maxstring();
        void minstring();
        void maxleftsubtree();
        void minrightsubtree();
    private:
        void inorderprint(Tnode *p);
        void preorderprint(Tnode *p);
        void postorderprint(Tnode *p);
        void maxstring(Tnode *p);
        void minstring(Tnode *p);
        void maxleftsubtree(Tnode *p);
        void minrightsubtree(Tnode *p);
        void insertleft(Tnode *place, string newval);
        void insertright(Tnode *place, string newval);
        Tnode *theroot;
};

// add a new node (with x as info) to tree that has theroot as root
void BST::insert(string x)
{
    // if the tree is initially empty, put x at the root
    if (theroot==NULL) {
        theroot = new Tnode(x);
        return;
    }

    Tnode *p, *q;

    // otherwise, find where x belongs in the tree
    p = theroot;
    q = theroot;
    while ( q != NULL) {
        p = q;
        if (x < p-> info)
            q = p-> left;
        else
            q = p-> right;
    }

    // to get here, we found the correct place to store x,
    // as a child of node p        Q: is it left or right?

    if (x < p-> info)
        insertleft(p,x);
    else
        insertright(p,x);

    return;

}

//insert a new node (with info newval) as left child of place
void BST::insertleft(Tnode *place, string newval)
{
    Tnode *p = new Tnode(newval);

    place -> left = p;
    return;

}

//insert a new node (with info newval) as right child of place
void BST::insertright(Tnode *place, string newval)
{
    Tnode *p = new Tnode(newval);

    place -> right = p;
    return;

}
......................
...............
...............

//
//
void BST::maxleftsubtree()
{
    maxleftsubtree(theroot);
}

//
//
void BST::minrightsubtree()
{
    minrightsubtree(theroot);
}

.....................................
.................................
.........................

//
//
void BST::maxleftsubtree(Tnode *p)
{
    while (p -> left)
        p = p -> right;
    cout << p -> info << " \n";
    return;
}

//
//
void BST::minrightsubtree(Tnode *p)
{
    while (p -> right)
        p = p -> left;
    cout << p -> info << " \n";
    return;
}

Answer 1

您的 maxleftsubtree(maxtrightsubtree) 函数存在错误。首先选择根的左（右）子树，沿着右（左）分支走到终点。这是修改后的版本：

void BST::maxleftsubtree(Tnode *p)
{
    Tnode* left = NULL;
    if (p != NULL) {
        left = p->left;
    }
    if (left != NULL) {
        while (left->right) 
            left = left -> right;
        cout << left -> info << " \n";
    }
    return;
}