Summe jeder Verzweigung in einer binären Suchstruktur

Question

Meine Aufgabe besteht darin, die Summe aller Knoten in jeder Verzweigung in einem binären Suchbaum mithilfe der Rekursion zu ermitteln und sie mit einem Benutzereingabewert zu vergleichen. Wenn der Benutzereingabewert mit einer Summe aus einem der Zweige übereinstimmt, sollte die Funktion den Wert true zurückgeben.

Mit anderen Worten, die Summe von 24 + 32 + 21 + 14 = 91. Die Summe von 32 + 24 + 28 + 25 = 109. Die Summe von 32 + 24 + 28 + 31 = 115 usw. Ich habe viele verschiedene Methoden ausprobiert, kann aber nicht herausfinden, wie man jeden Zweig genau durchläuft. Bis jetzt konnte ich nur die Summe der am weitesten links liegenden Zweige durchqueren.

Ich verwende die Methode des Subtrahierens jedes Knotens vom Benutzereingabewert. Wenn der Wert an einem Leaf-Knoten 0 erreicht, stimmt die Benutzereingabe eindeutig mit der Knotensumme dieses Zweiges im Baum überein.

Die besonderen Punkte der Schwierigkeit für mich sind, wenn der Zweig divergiert, wie an den Knoten [24] und [28]. Ich bekomme eindeutig etwas sehr einfaches falsch, aber ich kann es nicht herausfinden.

Unten ist der komprimierte Code, den ich bisher geschrieben habe, in Form von zwei Begleitmethoden (auch für die Zuweisung erforderlich).

Was mache ich falsch, und wie kann ich meinen Code reparieren, um die Summe der einzelnen Zweige auf dem Baum zu finden? Vielen Dank im Voraus. Ich entschuldige mich für Fehler in meinem Format oder fehlende Informationen.

Answer 1

Das ist falsch:

if (node->getLeftSide() != nullptr) 
{ 
    node = node->getLeftSide(); //advance to next Left node 
    result = findBranchSum(node, value); //recursive call using new node 
} 
if (node->getRightSide() != nullptr) 
{ 
    node = node->getRightSide(); //advance to next Right node 
    result = findBranchSum(node, value); //recursive call using new node 
} 

, weil Sie nach links und dann nach rechts Ast der linken (node durch Ihre Zuordnung geändert wird), wenn es vorhanden ist! Wechseln Sie zu:

if (node->getLeftSide() != nullptr) 
{ 
    result = findBranchSum(node->getLeftSide(), value); 
} 
if (node->getRightSide() != nullptr) 
{ 
    result = findBranchSum(node->getRightSide(), value); 
} 

Ihre Rückkehr Wertmanagement auch defekt ist, ändern Sie es an:

if (node->getLeftSide() != nullptr) 
{ 
    result = findBranchSum(node->getLeftSide(), value); 
} 
if (!result && node->getRightSide() != nullptr) // cut exploration if previous was correct... 
{ 
    result = findBranchSum(node->getRightSide(), value); 
} 
return result; 

, wenn Sie bei der ersten richtigen Zweig stoppen müssen.

Answer 2

Ich könnte etwas wie das folgende versuchen.

bool IsLeaf(Node const * node) { 
    return node && !node->left && !node->right; 
} 

bool CheckPathSum(Node const * node, int const target, int const sum_so_far) { 
    if (!node) return false; 
    int const sum = sum_so_far + node->element; 
    if IsLeaf(node) && (sum == target) return true; 
    return CheckPathSum(node->left, target, sum) || 
     CheckPathSum(node->right, target, sum); 
} 

Call as 
CheckPathSum(root, target, 0);