c++先序二叉树的构建详解

#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: };

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);//右孩子入队    }  }}

#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); }