這篇文章給大家分享的是有關(guān)c++經(jīng)典例題之如何構(gòu)建先序二叉樹的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考。一起跟隨小編過來看看吧。

公司主營業(yè)務(wù)：做網(wǎng)站、成都網(wǎng)站制作、移動網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。成都創(chuàng)新互聯(lián)公司是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會用頭腦與智慧不斷的給客戶帶來驚喜。成都創(chuàng)新互聯(lián)公司推出蘭陵免費(fèi)做網(wǎng)站回饋大家。

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

第一、定義BinaryTreeNode 類

#include 
#include 
#include 
using namespace std;

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

};

View Code

第二、定義BinaryTree 類

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

    //構(gòu)建二叉樹并返回
    BinaryTreeNode* CreateTree() {
        BinaryTreeNode* bt = NULL;
        char t;
        cin >> t;
        if (t == '#')
        {
            return NULL;
        }
        else {
            int num = t - '0';
            bt = new BinaryTreeNode(num);
            bt->lChild = CreateTree();
            bt->rChild = CreateTree();
        }
        return bt;
    }

    //先序構(gòu)建二叉樹
    BinaryTreeNode* PreCreateTree() {
        BinaryTreeNode* bt = NULL;
        if (this->root == NULL)
        {
            cout << "請輸入根節(jié)點(diǎn)（#代表空樹）:";
        }
        else {
            cout << "請輸入節(jié)點(diǎn)（#代表空樹）:";
        }
        char t;
        cin >> t;
        if (t == '#')
        {
            return NULL;
        }
        else {
            int num = t - '0';
            bt = new BinaryTreeNode(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 *bt);  //先序遍歷
    void inOrderTraversal(BinaryTreeNode *bt);  //中序遍歷
    void postOrderTraversal(BinaryTreeNode *bt);//后序遍歷
    void levelTraversal(BinaryTreeNode *bt);    //逐層遍歷

private:

};

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

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

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

template 
void BinaryTree::levelTraversal(BinaryTreeNode *bt) {

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

        if (proot->lChild != NULL)
        {
            que.push(proot->lChild);//左孩子入隊(duì)
        }
        if (proot->rChild != NULL)
        {
            que.push(proot->rChild);//右孩子入隊(duì)
        }
    }
}

View Code

第三、主程序運(yùn)行

#include "pch.h"
#include 
#include "BinaryTree.h"

int main()
{
    //場景測試2
    BinaryTree btree;
    btree.PreCreateTree();//先序構(gòu)建二叉樹
    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

最終測試運(yùn)行截圖

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)站欄目：c++經(jīng)典例題之如何構(gòu)建先序二叉樹-創(chuàng)新互聯(lián)
URL分享：http://weahome.cn/article/digcij.html