c++ 先序构建二叉树

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

第一、定义binarytreenode 类

 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 类

  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

 

第三、主程序运行

 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

最终测试运行截图