Wie zeichne BST mit Rekursion in diesem Format?

Question

void printGivenLevel(node *root, int level, int side, int x, int y) 
{ 
    if(root == NULL) 
    return; 

    if(level == 1) 
    { 
    gotoxy(x, y); 
    cout << root->data; 
    } 
    else if(level > 1) 
    { 
     if(y<=2) 
     { 
     printGivenLevel(root->left, level-1, 1, x-4, y); 
     printGivenLevel(root->right,level-1, 2, x+4, y); 
     } 
     else 
     { 
     printGivenLevel(root->left, level-1, 1, x-2, y); 
     printGivenLevel(root->right,level-1, 2, x+2, y); 
     } 
    } 
} 
void print(node *root) 
{ 
    int h = height(root); 
    int i; 
    int side = 0; // Use 1 for left and 2 for right 
    int x = 42; //42 is the center of console 

    for(i=1;i<=h;i++) 
    { 
    printGivenLevel(root, i, side, x, i); 
    cout << endl; 
    } 

    } 

I c bin mit ++ und brauchen die BST wie diese output .Die obigen Code nur auf Ebene formatieren kann 1. Ich nicht den Unterstrich noch enthalten waren, weil ich zum ersten Mal die Räume zu beheben versuchte. Ich suche nach einer Möglichkeit, dies zu formatieren, ohne etwas zu komplizierte wie Warteschlangen zu verwenden, und ich benutze auch Turbo C++ jede Hilfe wird geschätzt. Danke

Answer 1

Da Sie versäumt, eine MCVE zum Zeitpunkt der Erstellung dieser Antwort zur Verfügung zu stellen, habe ich nur mein eigenes gemacht.

Von Ihrer Frage, versichere ich, dass Ihr Hauptproblem die Rekursion zum Funktionieren bringt. Der Code, den ich in dieser Antwort zur Verfügung stelle, sollte Ihnen einen Einblick geben, wie Sie dieses Problem lösen können.

Es gibt immer noch einen Mangel: Jeder Knoten des Baumes wird in einer separaten Zeile gedruckt.

---

Code:

#include <iostream> 
#include <memory> 
#include <string> 

struct Node 
{ 
    Node(Node* l, Node* r, std::string d) : left(l), right(r), data(d) {} 
    std::unique_ptr<Node> left; 
    std::unique_ptr<Node> right; 
    std::string data; 
}; 

void printTree(Node& root, int minx, int maxx) 
{ 
    auto x = ((minx + maxx)/2); 

    auto o = ((x - minx)/2); 
    auto w = std::string(x - o, ' '); 
    auto u = std::string(o, '_'); 
    std::cout << w << u << root.data << u << std::endl; 

    if (root.left != nullptr) 
     printTree(*(root.left), minx, x); 

    if (root.right != nullptr) 
     printTree(*(root.right), x, maxx); 
} 

int main() 
{ 
    auto lrll = new Node{ nullptr, nullptr, "1" }; 
    auto lrlr = new Node{ nullptr, nullptr, "2" }; 
    auto lll = new Node{ nullptr, nullptr, "3" }; 
    auto llr = new Node{ nullptr, nullptr, "4" }; 
    auto lrl = new Node{ lrll, lrlr, "5" }; 
    auto lrr = new Node{ nullptr, nullptr, "6" }; 
    auto ll = new Node{ lll, llr, "7" }; 
    auto lr = new Node{ lrl, lrr, "8" }; 
    auto rl = new Node{ nullptr, nullptr, "9" }; 
    auto rr = new Node{ nullptr, nullptr, "10" }; 
    auto l = new Node{ ll, lr, "11" }; 
    auto r = new Node{ rl, rr, "12" }; 

    auto root = std::make_unique<Node>(l, r, "13"); 
    printTree(*root, 0, 84); 

    return 0; 
} 

Ausgang:

     _____________________13_____________________ 
      __________11__________ 
    _____7_____ 
    __3__ 
      __4__ 
          _____8_____ 
         __5__ 
         _1_ 
          _2_ 
            __6__ 
                __________12__________ 
               _____9_____ 
                    _____10_____ 

---

Hinweis: nicht alle Unterstrichen aufreihen perfekt, weil 84 wird als der anfängliche maximale Wert gewählt (dies tat ich, um die Wurzel an Position 42 zu erhalten).

Jede kann Binärbaum perfekt in der kompaktesten Weise dargestellt werden, indem man die anfängliche korrekt min und max-Wert gemäß folgender Formel wählen:

max - min == 2^(h) mit H == die Höhe des Baumes

Für der Baum (die Höhe 5) in meinem Code verwendet, die perfekte Darstellung erfordert:

max - min == 2^(5) == 32

Als solchen Aufruf printTree() mit jedem min und maximale Werte, die sich um 32 unterscheiden, ergeben eine perfekte und kompakteste Darstellung des Baumes. Zum Beispiel nannte es wie folgt

printTree(*root, 0, 32)

Ergebnisse in der folgenden Ausgabe:

 ________13________ 
    ____11____ 
    __7__ 
_3_ 
    _4_ 
      __8__ 
     _5_ 
     1 
      2 
      _6_ 
        ____12____ 
        __9__ 
          __10__