欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

c++ 先序构建二叉树

程序员文章站 2022-04-14 09:39:18
二叉树首先要解决构建问题,才能考虑后续的遍历,这里贴出通过先序构建二叉树,同时包含四种二叉树的遍历方法(先序,中序,后序,逐层) 第一、定义BinaryTreeNode 类 1 #include 2 #include 3 #include 4 ......

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

第一、定义binarytreenode 类

c++ 先序构建二叉树
 1 #include <iostream>
 2 #include <string>
 3 #include <queue>
 4 using namespace std;
 5 
 6 template<typename t >class binarytree;
 7 template <typename t> class binarytreenode {
 8 public:
 9     friend class binarytree<t>;
10     binarytreenode() {
11         data = null;
12         lchild = rchild = null;
13     }
14     binarytreenode(t newdata) {
15         this->data = newdata;
16         lchild = rchild = null;
17     }
18     t getdata() {
19         return data;
20     }
21     binarytreenode<t> * getleftnode() {
22         return lchild;
23     }
24     binarytreenode<t> * getrightnode() {
25         return rchild;
26     }
27     t data;
28     binarytreenode<t>* lchild;
29     binarytreenode<t>* rchild;
30 private:
31 
32 };
view code

 

第二、定义binarytree 类

c++ 先序构建二叉树
  1 template <typename t> class binarytree {
  2 public:
  3     binarytreenode<t> *root;
  4     char* p;
  5     binarytree() { root = null; }
  6     binarytree(t data) {
  7         root = new binarytreenode<t>(data);
  8         root->lchild = null;
  9         root->rchild = null;
 10     }
 11     ~binarytree() {
 12         delete root;
 13     }
 14 
 15     //构建二叉树并返回
 16     binarytreenode<t>* createtree() {
 17         binarytreenode<int>* bt = null;
 18         char t;
 19         cin >> t;
 20         if (t == '#')
 21         {
 22             return null;
 23         }
 24         else {
 25             int num = t - '0';
 26             bt = new binarytreenode<t>(num);
 27             bt->lchild = createtree();
 28             bt->rchild = createtree();
 29         }
 30         return bt;
 31     }
 32 
 33     //先序构建二叉树
 34     binarytreenode<t>* precreatetree() {
 35         binarytreenode<int>* bt = null;
 36         if (this->root == null)
 37         {
 38             cout << "请输入根节点(#代表空树):";
 39         }
 40         else {
 41             cout << "请输入节点(#代表空树):";
 42         }
 43         char t;
 44         cin >> t;
 45         if (t == '#')
 46         {
 47             return null;
 48         }
 49         else {
 50             int num = t - '0';
 51             bt = new binarytreenode<t>(num);
 52             if (this->root == null)
 53             {
 54                 this->root = bt;
 55             }
 56             cout << bt->data << "的左孩子";
 57             bt->lchild = precreatetree();
 58 
 59             cout << bt->data << "的右边孩子";
 60             bt->rchild = precreatetree();
 61         }
 62         return bt;
 63     }   
 64 
 65     void preodertraversal(binarytreenode<t> *bt);  //先序遍历
 66     void inordertraversal(binarytreenode<t> *bt);  //中序遍历
 67     void postordertraversal(binarytreenode<t> *bt);//后序遍历
 68     void leveltraversal(binarytreenode<t> *bt);    //逐层遍历
 69 
 70 private:
 71 
 72 };
 73 
 74 template <typename t>
 75 void binarytree<t>::preodertraversal(binarytreenode<t> *bt) {
 76     if (bt)
 77     {
 78         cout << bt->data;
 79         binarytree<t>::preodertraversal(bt->getleftnode());
 80         binarytree<t>::preodertraversal(bt->getrightnode());
 81     }
 82 }
 83 
 84 template <typename t>
 85 void binarytree<t>::inordertraversal(binarytreenode<t> *bt) {
 86     if (bt)
 87     {
 88         binarytree<t>::inordertraversal(bt->getleftnode());
 89         cout << bt->data;
 90         binarytree<t>::inordertraversal(bt->getrightnode());
 91     }
 92 }
 93 
 94 template <typename t>
 95 void binarytree<t>::postordertraversal(binarytreenode<t> *bt) {
 96     if (bt)
 97     {
 98         binarytree<t>::postordertraversal(bt->getleftnode());
 99         binarytree<t>::postordertraversal(bt->getrightnode());
100         cout << bt->data;
101     }
102 }
103 
104 template <typename t>
105 void binarytree<t>::leveltraversal(binarytreenode<t> *bt) {
106 
107     queue<binarytreenode<t>*> que;
108     que.push(bt);
109     while (!que.empty())
110     {
111         binarytreenode<t>* proot = que.front();
112         que.pop();
113         cout << proot->data;
114 
115         if (proot->lchild != null)
116         {
117             que.push(proot->lchild);//左孩子入队
118         }
119         if (proot->rchild != null)
120         {
121             que.push(proot->rchild);//右孩子入队
122         }
123     }
124 }
view code

 

第三、主程序运行

c++ 先序构建二叉树
 1 #include "pch.h"
 2 #include <iostream>
 3 #include "binarytree.h"
 4 
 5 int main()
 6 {
 7     //场景测试2
 8     binarytree<int> btree;
 9     btree.precreatetree();//先序构建二叉树
10     cout << "先序遍历:";
11     btree.preodertraversal(btree.root); cout << endl;//先序遍历    
12     cout << "中序遍历:";
13     btree.inordertraversal(btree.root); cout << endl;//中序遍历
14     cout << "后序遍历:";
15     btree.postordertraversal(btree.root); cout << endl;//后序遍历
16     cout << "逐层序遍历:";
17     btree.leveltraversal(btree.root);
18 
19 }
view code

最终测试运行截图

c++ 先序构建二叉树