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

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

第一、定义BinaryTreeNode 类

#include iostream>
    #include string>
    #include queue>
    using namespace std;
    templatetyPEname T >
    class BinaryTree;
    template typename T>
 class BinaryTreeNode {
    public:    friend class BinaryTreeT>
    ;
    BinaryTreeNode() {
            data = NULL;
            lChild = rChild = NULL;
    }
    BinaryTreeNode(T newdata) {
            this->
    data = newdata;
            lChild = rChild = NULL;
    }
    T getData() {
            return data;
    }
        BinaryTreeNodeT>
 * getLeftNode() {
            return lChild;
    }
        BinaryTreeNodeT>
 * getRightNode() {
            return rChild;
    }
        T data;
        BinaryTreeNodeT>
    * lChild;
        BinaryTreeNodeT>
    * rChild;
PRivate:}
    ;
    

View Code

第二、定义BinaryTree 类

template typename T>
 class BinaryTree {
    public:    BinaryTreeNodeT>
     *root;
        char* p;
    BinaryTree() {
     root = NULL;
 }
    BinaryTree(T data) {
            root = new BinaryTreeNodeT>
    (data);
            root->
    lChild = NULL;
            root->
    rChild = NULL;
    }
    ~BinaryTree() {
            delete root;
    }
        //构建二叉树并返回    BinaryTreeNodeT>
* CreateTree() {
            BinaryTreeNodeint>
    * BT = NULL;
            char t;
            cin >
    >
     t;
        if (t == '#')        {
                return NULL;
        }
        else {
                int num = t - '0';
                bt = new BinaryTreeNodeT>
    (num);
                bt->
    lChild = CreateTree();
                bt->
    rChild = CreateTree();
        }
            return bt;
    }
        //先序构建二叉树    BinaryTreeNodeT>
* PreCreateTree() {
            BinaryTreeNodeint>
    * bt = NULL;
            if (this->
root == NULL)        {
                cout  "请输入根节点（#代表空树）:";
        }
        else {
                cout  "请输入节点（#代表空树）:";
        }
            char t;
            cin >
    >
     t;
        if (t == '#')        {
                return NULL;
        }
        else {
                int num = t - '0';
                bt = new BinaryTreeNodeT>
    (num);
                if (this->
root == NULL)            {
                    this->
    root = bt;
            }
                cout  bt->
    data  "的左孩子";
                bt->
    lChild = PreCreateTree();
                cout  bt->
    data  "的右边孩子";
                bt->
    rChild = PreCreateTree();
        }
            return bt;
    }
           void preOderTraversal(BinaryTreeNodeT>
     *bt);
      //先序遍历    void inOrderTraversal(BinaryTreeNodeT>
     *bt);
      //中序遍历    void postOrderTraversal(BinaryTreeNodeT>
     *bt);
    //后序遍历    void levelTraversal(BinaryTreeNodeT>
     *bt);
    //逐层遍历private:}
    ;
    template typename T>
    void BinaryTreeT>
    ::preOderTraversal(BinaryTreeNodeT>
 *bt) {
    if (bt)    {
            cout  bt->
    data;
            BinaryTreeT>
    ::preOderTraversal(bt->
    getLeftNode());
            BinaryTreeT>
    ::preOderTraversal(bt->
    getRightNode());
    }
}
    template typename T>
    void BinaryTreeT>
    ::inOrderTraversal(BinaryTreeNodeT>
 *bt) {
    if (bt)    {
            BinaryTreeT>
    ::inOrderTraversal(bt->
    getLeftNode());
            cout  bt->
    data;
            BinaryTreeT>
    ::inOrderTraversal(bt->
    getRightNode());
    }
}
    template typename T>
    void BinaryTreeT>
    ::postOrderTraversal(BinaryTreeNodeT>
 *bt) {
    if (bt)    {
            BinaryTreeT>
    ::postOrderTraversal(bt->
    getLeftNode());
            BinaryTreeT>
    ::postOrderTraversal(bt->
    getRightNode());
            cout  bt->
    data;
    }
}
    template typename T>
    void BinaryTreeT>
    ::levelTraversal(BinaryTreeNodeT>
 *bt) {
        queueBinaryTreeNodeT>
    *>
     que;
        que.push(bt);
    while (!que.empty())    {
            BinaryTreeNodeT>
    * 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    BinaryTreeint>
     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++视频教程

以上就是c++经典例题之先序二叉树的构建的详细内容，更多请关注其它相关文章！

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！