C++ の古典的な例: プリオーダー バイナリ ツリーの構築

この記事の編集者は、プリオーダー バイナリ ツリーを構築する古典的な C 手法を復習します。興味のある友人は一緒に復習することができます。

バイナリ ツリーの構築問題は、その後の走査を検討する前に、まず解決する必要があります。これは、プレオーダーによるバイナリ ツリーの構築に関する投稿です。これには、4 つのバイナリ ツリー走査方法 (プレオーダー、インオーダー、ポストオーダー) も含まれています、レイヤーごと)

最初に、BinaryTreeNode クラスを定義します

#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:

};

コードの表示

2 番目、BinaryTree クラスの定義

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);//右孩子入队
        }
    }
}

コードの表示

3 番目、メイン プログラムの実行

#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);

}

コードの表示

最終テスト実行のスクリーンショット

関連チュートリアル: C ビデオ チュートリアル

以上がC++ の古典的な例: プリオーダー バイナリ ツリーの構築の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。