c++经典例题之如何构建先序二叉树

这篇文章给大家分享的是有关c++经典例题之如何构建先序二叉树的内容。小编觉得挺实用的，因此分享给大家做个参考。一起跟随小编过来看看吧。

创新互联公司-成都网站建设公司，专注网站建设、成都做网站、网站营销推广，国际域名空间，虚拟空间，成都网站托管有关企业网站制作方案、改版、费用等问题，请联系创新互联公司。

二叉树首先要解决构建问题，才能考虑后续的遍历，这里贴出通过先序构建二叉树，同时包含四种二叉树的遍历方法（先序，中序，后序，逐层）

第一、定义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;
    }

    //构建二叉树并返回
    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;
    }

    //先序构建二叉树
    BinaryTreeNode* PreCreateTree() {
        BinaryTreeNode* 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(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);//左孩子入队
        }
        if (proot->rChild != NULL)
        {
            que.push(proot->rChild);//右孩子入队
        }
    }
}

View Code

第三、主程序运行

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

int main()
{
    //场景测试2
    BinaryTree 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++经典例题之如何构建先序二叉树就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到吧！