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

概述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++视频教程 总结

以上是内存溢出为你收集整理的c++经典例题之先序二叉树的构建全部内容，希望文章能够帮你解决c++经典例题之先序二叉树的构建所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。