원본 트리의 하위 트리

Question

시도 할 때 문제가 발생했습니다. (1) 원본 트리 루트의 왼쪽 하위 트리에서 가장 큰 정보 필드를 찾습니다. (2) 원래 트리의 루트의 오른쪽 하위 트리.

내 코드가 컴파일되지만 실행시 오류가 있으며 maxleftsubtree() 및 minrightsubtree() 함수에서 어떤 일이 발생하는지 잘 모르겠습니다. 모든 제안을 부탁드립니다.

내 현재 코드 : 당신의 maxleftsubtree (maxtrightsubtree) 함수에 오류가 있습니다

#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

. 먼저 루트의 왼쪽 (오른쪽) 하위 트리를 선택하고 오른쪽 (왼쪽) 분기를 따라 끝까지 이동해야합니다. 다음은 수정 된 버전입니다.

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; 
}