首页 > > 网络编程 > Php编程 >

c++ 先序构建二叉树

2018-12-28 08:05:15来源：博客园阅读 ()

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

第一、定义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 }