元のツリーのサブツリー

Question

私は次のことを試みているときに問題が発生しています： （1）元のツリーのルートの左のサブツリーで最大の情報フィールドを見つけよう （2）元のツリーのルートの右サブツリー。

私のコードはコンパイルされますが、実行時にエラーが発生し、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; 
}