Wie rekursiv alle Knoten in einem binären Suchbaum mit Stringstream C++

Question

Ich drucke den Inhalt aller Knoten in meinem binären Suchbaum mit einem Stringstream und Rekursion. Das Problem ist, dass wenn ich diesen Code verwende, nur der Inhalt der Wurzel angezeigt wird. Ich weiß, der Grund ist, dass jedes Mal, wenn ich die Funktion InOrder (BSTNode * bst_node) rekursiv aufruft, meine Stringstream-Variable erneut erstellt wird. Was kann ich mit meinem Code tun, um dieses Problem zu beheben, während weiterhin ein Stringstream für die Ausgabe verwendet wird?

Dies ist mein Code:

string BSTree::InOrder(BSTNode* bst_node) { 
    stringstream ss; 
    if (root_ == NULL) { 
    return ""; 
    } else { 
    if (bst_node->GetLeftChild() != NULL) { 
     InOrder(bst_node->GetLeftChild()); 
    } 
    ss << bst_node->GetContents() << " "; 
    if (bst_node->GetRightChild() != NULL) { 
     InOrder(bst_node->GetRightChild()); 
    } 
    } 
    return ss.str(); 
} 

Answer 1

etwas wie das vielleicht?

string BSTree::InOrder(BSTNode* bst_node) 
{ 
    if (!bst_node) 
    return ""; 
    ostringstream ss; 
    ss << InOrder(bst_node->GetLeftChild()); 
    ss << bst_node->GetContents() << " "; 
    ss << InOrder(bst_node->GetRightChild()); 
    return ss.str(); 
} 

oder können Sie rund um die gleiche Instanz von string passieren:

void BSTree::InOrderImpl(BSTNode* bst_node, ostringstream &ss) 
{ 
    if (bst_node) 
    { 
    InOrderImpl(bst_node->GetLeftChild(), ss); 
    ss << bst_node->GetContents() << " "; 
    InOrderImpl(bst_node->GetRightChild(), ss); 
    } 
} 

string BSTree::InOrder(BSTNode* bst_node) 
{ 
    ostringstream ss; 
    InOrder(bst_node, ss); 
    return ss.str(); 
} 

Answer 2

Meine Klacks für diesen - passieren den string als Argument durch Verweis auf diese Methode:

static stringstream existingSSreference; 
string BSTree::InOrder(BSTNode* bst_node, stringstream & ss = existingSSreference) { 

    if (root_ == NULL) { 
    return ""; 
    } else { 
    if (bst_node->GetLeftChild() != NULL) { 
     InOrder(bst_node->GetLeftChild(), ss); 
    } 
    ss << bst_node->GetContents(); 
    if (bst_node->GetRightChild() != NULL) { 
     InOrder(bst_node->GetRightChild(), ss); 
    } 
    } 
    return ss.str(); 
} 

und entweder möchten Sie den stringstream deklarieren, bevor Sie die Methode verwenden:

oder es verwenden, ohne Arbeit sollte es

string myResult = bstreeObj->InOrder(bstNode); 

dies vorbei. Definieren Sie den Stringstream besser außerhalb der Funktion und übergeben Sie ihn beim Aufruf der Funktion.

EDIT

Wie von Ajay wies darauf hin, kann ein Referenz Argument nicht Standardwert haben, es sei denn wir eine tatsächliche vorhandene Instanz als Standard übergeben (damit wir die Möglichkeit, halten das zweite Argument weglassen) .

Answer 3

Einfach: definiert nur eine Hilfsfunktion, wo stringstream als Argument übergeben wird:

void BSTree::InOrder(BSTNode *root, std::stringstream &ss) 
{ 
    if (root == nullptr) { return; } 
    InOrder(root->GetLeftChild(), ss) 
    ss << root->GetContents() << " "; 
    InOrder(root->GetRightChild(), ss) 
} 

string BSTree::InOrder(BSTNode* bst_node) { 
    stringstream ss; 
    InOrder(bst_node, ss); 
    return ss.str(); 
} 

Beachten Sie, dass die Instanziierung nur ein stringstream wo der ganze Baum geworfen wird, ist wahrscheinlich viel effizienter als ein stringstream für jeden Knoten der Instanziierung Ihr Baum (wie es passiert, wenn Sie die Dienstprogrammfunktion als etwas definieren, das einen Knoten nimmt und einen String zurückgibt).