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++经典例题之先序二叉树的构建的详细内容，更多内容请关注技术你好其它相关文章！