c++經典例題之如何構建先序二叉樹

這篇文章給大家分享的是有關c++經典例題之如何構建先序二叉樹的內容。小編覺得挺實用的，因此分享給大家做個參考。一起跟隨小編過來看看吧。

二叉樹首先要解決構建問題，才能考慮后續的遍歷，這里貼出通過先序構建二叉樹，同時包含四種二叉樹的遍歷方法（先序，中序，后序，逐層）

第一、定義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:

};

View Code

第二、定義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 == '#')
        {
            return NULL;
        }
        else {
            int num = t - '0';
            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 == '#')
        {
            return NULL;
        }
        else {
            int num = t - '0';
            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);//右孩子入隊
        }
    }
}

View Code

第三、主程序運行

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

}

View Code

最終測試運行截圖

感謝各位的閱讀！關于c++經典例題之如何構建先序二叉樹就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！