Heim Backend-Entwicklung C#.Net-Tutorial Klassisches C++-Beispiel: Aufbau eines Binärbaums vor der Bestellung

Klassisches C++-Beispiel: Aufbau eines Binärbaums vor der Bestellung

Apr 20, 2019 pm 05:31 PM
c++

In diesem Artikel führt Sie der Herausgeber durch die Konstruktion von vorbestellten Binärbäumen in klassischem C++. Freunde, die daran interessiert sind, sollten dies gemeinsam überprüfen!

Das Konstruktionsproblem eines Binärbaums muss zuerst gelöst werden, bevor eine anschließende Durchquerung in Betracht gezogen werden kann. Hier ist ein Beitrag zum Aufbau eines Binärbaums durch Vorbestellung, der auch vier Methoden zur Durchquerung von Binärbäumen enthält (Vorbestellung, Inorder, Postorder). , Schicht für Schicht)

Definieren Sie zunächst die BinaryTreeNode-Klasse

#include <iostream>
#include <string>
#include <queue>
using namespace std;

template<typename T >class BinaryTree;
template <typename T> class BinaryTreeNode {
public:
    friend class BinaryTree<T>;
    BinaryTreeNode() {
        data = NULL;
        lChild = rChild = NULL;
    }
    BinaryTreeNode(T newdata) {
        this->data = newdata;
        lChild = rChild = NULL;
    }
    T getData() {
        return data;
    }
    BinaryTreeNode<T> * getLeftNode() {
        return lChild;
    }
    BinaryTreeNode<T> * getRightNode() {
        return rChild;
    }
    T data;
    BinaryTreeNode<T>* lChild;
    BinaryTreeNode<T>* rChild;
private:

};
Nach dem Login kopieren

Code anzeigen

Zweitens: BinaryTree-Klasse definieren

template <typename T> class BinaryTree {
public:
    BinaryTreeNode<T> *root;
    char* p;
    BinaryTree() { root = NULL; }
    BinaryTree(T data) {
        root = new BinaryTreeNode<T>(data);
        root->lChild = NULL;
        root->rChild = NULL;
    }
    ~BinaryTree() {
        delete root;
    }

    //构建二叉树并返回
    BinaryTreeNode<T>* CreateTree() {
        BinaryTreeNode<int>* bt = NULL;
        char t;
        cin >> t;
        if (t == &#39;#&#39;)
        {
            return NULL;
        }
        else {
            int num = t - &#39;0&#39;;
            bt = new BinaryTreeNode<T>(num);
            bt->lChild = CreateTree();
            bt->rChild = CreateTree();
        }
        return bt;
    }

    //先序构建二叉树
    BinaryTreeNode<T>* PreCreateTree() {
        BinaryTreeNode<int>* bt = NULL;
        if (this->root == NULL)
        {
            cout << "请输入根节点(#代表空树):";
        }
        else {
            cout << "请输入节点(#代表空树):";
        }
        char t;
        cin >> t;
        if (t == &#39;#&#39;)
        {
            return NULL;
        }
        else {
            int num = t - &#39;0&#39;;
            bt = new BinaryTreeNode<T>(num);
            if (this->root == NULL)
            {
                this->root = bt;
            }
            cout << bt->data << "的左孩子";
            bt->lChild = PreCreateTree();

            cout << bt->data << "的右边孩子";
            bt->rChild = PreCreateTree();
        }
        return bt;
    }   

    void preOderTraversal(BinaryTreeNode<T> *bt);  //先序遍历
    void inOrderTraversal(BinaryTreeNode<T> *bt);  //中序遍历
    void postOrderTraversal(BinaryTreeNode<T> *bt);//后序遍历
    void levelTraversal(BinaryTreeNode<T> *bt);    //逐层遍历

private:

};

template <typename T>
void BinaryTree<T>::preOderTraversal(BinaryTreeNode<T> *bt) {
    if (bt)
    {
        cout << bt->data;
        BinaryTree<T>::preOderTraversal(bt->getLeftNode());
        BinaryTree<T>::preOderTraversal(bt->getRightNode());
    }
}

template <typename T>
void BinaryTree<T>::inOrderTraversal(BinaryTreeNode<T> *bt) {
    if (bt)
    {
        BinaryTree<T>::inOrderTraversal(bt->getLeftNode());
        cout << bt->data;
        BinaryTree<T>::inOrderTraversal(bt->getRightNode());
    }
}

template <typename T>
void BinaryTree<T>::postOrderTraversal(BinaryTreeNode<T> *bt) {
    if (bt)
    {
        BinaryTree<T>::postOrderTraversal(bt->getLeftNode());
        BinaryTree<T>::postOrderTraversal(bt->getRightNode());
        cout << bt->data;
    }
}

template <typename T>
void BinaryTree<T>::levelTraversal(BinaryTreeNode<T> *bt) {

    queue<BinaryTreeNode<T>*> que;
    que.push(bt);
    while (!que.empty())
    {
        BinaryTreeNode<T>* proot = que.front();
        que.pop();
        cout << proot->data;

        if (proot->lChild != NULL)
        {
            que.push(proot->lChild);//左孩子入队
        }
        if (proot->rChild != NULL)
        {
            que.push(proot->rChild);//右孩子入队
        }
    }
}
Nach dem Login kopieren

Code anzeigen

Drittens das Hauptprogramm ausführen

#include "pch.h"
#include <iostream>
#include "BinaryTree.h"

int main()
{
    //场景测试2
    BinaryTree<int> btree;
    btree.PreCreateTree();//先序构建二叉树
    cout << "先序遍历:";
    btree.preOderTraversal(btree.root); cout << endl;//先序遍历    
    cout << "中序遍历:";
    btree.inOrderTraversal(btree.root); cout << endl;//中序遍历
    cout << "后序遍历:";
    btree.postOrderTraversal(btree.root); cout << endl;//后序遍历
    cout << "逐层序遍历:";
    btree.levelTraversal(btree.root);

}
Nach dem Login kopieren

Code anzeigen

Screenshot des letzten Testlaufs

Verwandte Tutorials: C++-Video-Tutorial

Das obige ist der detaillierte Inhalt vonKlassisches C++-Beispiel: Aufbau eines Binärbaums vor der Bestellung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Beste grafische Einstellungen
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. So reparieren Sie Audio, wenn Sie niemanden hören können
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: Wie man alles in Myrise freischaltet
4 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Wie implementiert man das Strategy Design Pattern in C++? Wie implementiert man das Strategy Design Pattern in C++? Jun 06, 2024 pm 04:16 PM

Die Schritte zum Implementieren des Strategiemusters in C++ lauten wie folgt: Definieren Sie die Strategieschnittstelle und deklarieren Sie die Methoden, die ausgeführt werden müssen. Erstellen Sie spezifische Strategieklassen, implementieren Sie jeweils die Schnittstelle und stellen Sie verschiedene Algorithmen bereit. Verwenden Sie eine Kontextklasse, um einen Verweis auf eine konkrete Strategieklasse zu speichern und Operationen darüber auszuführen.

Wie implementiert man eine verschachtelte Ausnahmebehandlung in C++? Wie implementiert man eine verschachtelte Ausnahmebehandlung in C++? Jun 05, 2024 pm 09:15 PM

Die Behandlung verschachtelter Ausnahmen wird in C++ durch verschachtelte Try-Catch-Blöcke implementiert, sodass neue Ausnahmen innerhalb des Ausnahmehandlers ausgelöst werden können. Die verschachtelten Try-Catch-Schritte lauten wie folgt: 1. Der äußere Try-Catch-Block behandelt alle Ausnahmen, einschließlich der vom inneren Ausnahmehandler ausgelösten. 2. Der innere Try-Catch-Block behandelt bestimmte Arten von Ausnahmen, und wenn eine Ausnahme außerhalb des Gültigkeitsbereichs auftritt, wird die Kontrolle an den externen Ausnahmehandler übergeben.

Wie verwende ich die C++-Vorlagenvererbung? Wie verwende ich die C++-Vorlagenvererbung? Jun 06, 2024 am 10:33 AM

Durch die Vererbung von C++-Vorlagen können von Vorlagen abgeleitete Klassen den Code und die Funktionalität der Basisklassenvorlage wiederverwenden. Dies eignet sich zum Erstellen von Klassen mit derselben Kernlogik, aber unterschiedlichen spezifischen Verhaltensweisen. Die Syntax der Vorlagenvererbung lautet: templateclassDerived:publicBase{}. Beispiel: templateclassBase{};templateclassDerived:publicBase{};. Praktischer Fall: Erstellt die abgeleitete Klasse Derived, erbt die Zählfunktion der Basisklasse Base und fügt die Methode printCount hinzu, um die aktuelle Zählung zu drucken.

Warum tritt bei der Installation einer Erweiterung mit PECL in einer Docker -Umgebung ein Fehler auf? Wie löst ich es? Warum tritt bei der Installation einer Erweiterung mit PECL in einer Docker -Umgebung ein Fehler auf? Wie löst ich es? Apr 01, 2025 pm 03:06 PM

Ursachen und Lösungen für Fehler Bei der Verwendung von PECL zur Installation von Erweiterungen in der Docker -Umgebung, wenn die Docker -Umgebung verwendet wird, begegnen wir häufig auf einige Kopfschmerzen ...

Was ist die Rolle von CHAR in C -Saiten? Was ist die Rolle von CHAR in C -Saiten? Apr 03, 2025 pm 03:15 PM

In C wird der Zeichenentyp in Saiten verwendet: 1. Speichern Sie ein einzelnes Zeichen; 2. Verwenden Sie ein Array, um eine Zeichenfolge darzustellen und mit einem Null -Terminator zu enden. 3. Durch eine Saitenbetriebsfunktion arbeiten; 4. Lesen oder geben Sie eine Zeichenfolge von der Tastatur aus.

Wie gehe ich mit Thread-übergreifenden C++-Ausnahmen um? Wie gehe ich mit Thread-übergreifenden C++-Ausnahmen um? Jun 06, 2024 am 10:44 AM

In Multithread-C++ wird die Ausnahmebehandlung über die Mechanismen std::promise und std::future implementiert: Verwenden Sie das Promise-Objekt, um die Ausnahme in dem Thread aufzuzeichnen, der die Ausnahme auslöst. Verwenden Sie ein zukünftiges Objekt, um in dem Thread, der die Ausnahme empfängt, nach Ausnahmen zu suchen. Praktische Fälle zeigen, wie man Versprechen und Futures verwendet, um Ausnahmen in verschiedenen Threads abzufangen und zu behandeln.

Speichernutzungs- und Optimierungsstrategien für den lokalen C++-Thread-Speicher Speichernutzungs- und Optimierungsstrategien für den lokalen C++-Thread-Speicher Jun 05, 2024 pm 06:49 PM

TLS stellt jedem Thread eine private Kopie der Daten zur Verfügung, die im Thread-Stack-Bereich gespeichert wird, und die Speichernutzung variiert je nach Anzahl der Threads und der Datenmenge. Zu den Optimierungsstrategien gehören die dynamische Zuweisung von Speicher mithilfe threadspezifischer Schlüssel, die Verwendung intelligenter Zeiger zur Verhinderung von Lecks und die Partitionierung von Daten zur Platzersparnis. Beispielsweise kann eine Anwendung TLS-Speicher dynamisch zuweisen, um Fehlermeldungen nur für Sitzungen mit Fehlermeldungen zu speichern.

Vier Möglichkeiten zur Implementierung von Multithreading in C -Sprache Vier Möglichkeiten zur Implementierung von Multithreading in C -Sprache Apr 03, 2025 pm 03:00 PM

Multithreading in der Sprache kann die Programmeffizienz erheblich verbessern. Es gibt vier Hauptmethoden, um Multithreading in C -Sprache zu implementieren: Erstellen Sie unabhängige Prozesse: Erstellen Sie mehrere unabhängig laufende Prozesse. Jeder Prozess hat seinen eigenen Speicherplatz. Pseudo-MultitHhreading: Erstellen Sie mehrere Ausführungsströme in einem Prozess, der denselben Speicherplatz freigibt und abwechselnd ausführt. Multi-Thread-Bibliothek: Verwenden Sie Multi-Thread-Bibliotheken wie PThreads, um Threads zu erstellen und zu verwalten, wodurch reichhaltige Funktionen der Thread-Betriebsfunktionen bereitgestellt werden. Coroutine: Eine leichte Multi-Thread-Implementierung, die Aufgaben in kleine Unteraufgaben unterteilt und sie wiederum ausführt.

See all articles