c++中如何构建一个先序二叉树

这篇文章主要讲解了"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++中如何构建一个先序二叉树"的内容了，经过本文的学习后，相信大家对c++中如何构建一个先序二叉树这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是，小编将为大家推送更多相关知识点的文章，欢迎关注！