首页 > > 程序设计 > C/C++ >

二叉树--普通二叉树的创建和遍历

2020-01-30 16:01:19来源：博客园阅读 ()

二叉树--普通二叉树的创建和遍历

用 C++ 封装的普通的二叉树，涉及二叉树的创建，先序遍历（递归、非递归），中序遍历（递归、非递归），后序遍历（递归、非递归），层序遍历。

使用 STL std::queue 以及先序方法创建二叉树，使用成员 nullVal 代表空。

先序、中序、后序三种非递归使用 STL std::stack 辅助实现。

层序遍历使用 STL std::queue 辅助实现。

环境 win10 + VS2019。

源文件 main.cpp：

 1 #include <iostream>
 2 #include <queue>
 3 #include "BinaryTree.h"
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     queue<char> qu({ 'a','b','c',0,0,'d','e',0,0,'f','g',0,0,0,'h','i',0,0,'j',0,0 });
 9     BinaryTree<char> binTree(0, qu);
10 
11     cout << "preorderTraversal:\n\t";
12     binTree.preorderTraversal();
13     cout << "\n\npreorderTraversal_non_recursive:\n\t";
14     binTree.preorderTraversal_non_recursive();
15     cout << "\n\ninorderTraversal:\n\t";
16     binTree.inorderTraversal();
17     cout << "\n\ninorderTraversal_non_recursive:\n\t";
18     binTree.inorderTraversal_non_recursive();
19     cout << "\n\npostorderTraversal:\n\t";
20     binTree.postorderTraversal();
21     cout << "\n\npostorderTraversal_non_recursive:\n\t";
22     binTree.postorderTraversal_non_recursive();
23     cout << "\n\nlevelTraversal:\n\t";
24     binTree.levelTraversal();
25     cout << endl;
26 
27     return 0;
28 }

头文件 "BinaryTree.h"：

  1 #pragma once
  2 #ifndef __BINARYTREE_H__
  3 #define __BINARYTREE_H__
  4 
  5 
  6 #include <queue>
  7 #include <stack>
  8 template<typename _Ty>
  9 class BinaryTree
 10 {
 11 private:
 12     struct Node
 13     {
 14         _Ty data;
 15         Node* left = nullptr;
 16         Node* right = nullptr;
 17         Node(const _Ty& _data) :data(_data) {}
 18     };
 19 
 20 public:
 21     BinaryTree(const _Ty& _val) :nullVal(_val) {}
 22     BinaryTree(const _Ty& _val, std::queue<_Ty>& _qu) :nullVal(_val) { creatTree(_qu, root); }
 23     ~BinaryTree() { clear(root); }
 24     void clear() { clear(root); }
 25     size_t size() const { return size_n; }
 26     Node* getRoot() const { return root; }
 27     void setNullValue(const _Ty& _val) { nullVal = _val; }
 28     void creatTree(std::queue<_Ty>& _qu) { if (root != nullptr) clear(root); creatTree(_qu, root); }
 29     void preorderTraversal() const { preorderTraversal(root); }
 30     void inorderTraversal() const { inorderTraversal(root); }
 31     void postorderTraversal() const { postorderTraversal(root); }
 32     void levelTraversal() const { levelTraversal(root); }
 33     void preorderTraversal_non_recursive() const { preorderTraversal_non_recursive(root); }
 34     void inorderTraversal_non_recursive() const { inorderTraversal_non_recursive(root); }
 35     void postorderTraversal_non_recursive() const { postorderTraversal_non_recursive(root); }
 36 
 37 private:
 38     void creatTree(std::queue<_Ty>&, Node*&);
 39     void clear(Node*&);
 40     void preorderTraversal(Node*) const;
 41     void inorderTraversal(Node*) const;
 42     void postorderTraversal(Node*) const;
 43     void levelTraversal(Node*) const;
 44     void preorderTraversal_non_recursive(Node*) const;
 45     void inorderTraversal_non_recursive(Node*) const;
 46     void postorderTraversal_non_recursive(Node*) const;
 47 
 48 private:
 49     _Ty nullVal;
 50     size_t size_n = 0;
 51     Node* root = nullptr;
 52 };
 53 
 54 template<typename _Ty>
 55 void BinaryTree<_Ty>::creatTree(std::queue<_Ty>& _qu, Node*& _node)
 56 {
 57     if (_qu.empty()) return;
 58     if (_qu.front() == nullVal)
 59     {
 60         _qu.pop();
 61         return;
 62     }
 63     _node = new Node(_qu.front());
 64     _qu.pop();
 65     ++size_n;
 66     creatTree(_qu, _node->left);
 67     creatTree(_qu, _node->right);
 68 }
 69 
 70 template<typename _Ty>
 71 void BinaryTree<_Ty>::clear(Node*& _node)
 72 {
 73     if (_node == nullptr) return;
 74     clear(_node->left);
 75     clear(_node->right);
 76     delete _node;
 77     _node = nullptr;
 78     --size_n;
 79 }
 80 
 81 template<typename _Ty>
 82 void BinaryTree<_Ty>::preorderTraversal(Node* _node) const
 83 {
 84     if (_node == nullptr) return;
 85     std::cout << _node->data << " ";
 86     preorderTraversal(_node->left);
 87     preorderTraversal(_node->right);
 88 }
 89 
 90 template<typename _Ty>
 91 void BinaryTree<_Ty>::inorderTraversal(Node* _node) const
 92 {
 93     if (_node == nullptr) return;
 94     inorderTraversal(_node->left);
 95     std::cout << _node->data << " ";
 96     inorderTraversal(_node->right);
 97 }
 98 
 99 template<typename _Ty>
100 void BinaryTree<_Ty>::postorderTraversal(Node* _node) const
101 {
102     if (_node == nullptr) return;
103     postorderTraversal(_node->left);
104     postorderTraversal(_node->right);
105     std::cout << _node->data << " ";
106 }
107 
108 template<typename _Ty>
109 void BinaryTree<_Ty>::levelTraversal(Node* _node) const
110 {
111     if (_node == nullptr) return;
112     std::queue<Node*> nodePointers;
113     nodePointers.push(_node);
114     while (!nodePointers.empty())
115     {
116         Node* cur = nodePointers.front();
117         std::cout << cur->data << " ";
118         if (cur->left != nullptr) nodePointers.push(cur->left);
119         if (cur->right != nullptr) nodePointers.push(cur->right);
120         nodePointers.pop();
121     }
122 }
123 
124 template<typename _Ty>
125 void BinaryTree<_Ty>::preorderTraversal_non_recursive(Node* _node) const
126 {
127     if (_node == nullptr) return;
128     std::stack<Node*> nodePointers;
129     Node* cur = _node;
130     while (cur != nullptr || !nodePointers.empty())
131     {
132         std::cout << cur->data << " ";
133         nodePointers.push(cur);
134         cur = cur->left;
135         while (cur == nullptr && !nodePointers.empty())
136         {
137             cur = nodePointers.top()->right;
138             nodePointers.pop();
139         }
140     }
141 }
142 
143 template<typename _Ty>
144 void BinaryTree<_Ty>::inorderTraversal_non_recursive(Node* _node) const
145 {
146     if (_node == nullptr) return;
147     std::stack<Node*> nodePointers;
148     Node* cur = _node;
149     while (cur != nullptr || !nodePointers.empty())
150     {
151         if (cur->left != nullptr)
152         {
153             nodePointers.push(cur);
154             cur = cur->left;
155         }
156         else
157         {
158             std::cout << cur->data << " ";
159             cur = cur->right;
160             while (cur == nullptr && !nodePointers.empty())
161             {
162                 cur = nodePointers.top();
163                 nodePointers.pop();
164                 std::cout << cur->data << " ";
165                 cur = cur->right;
166             }
167         }
168     }
169 }
170 
171 template<typename _Ty>
172 void BinaryTree<_Ty>::postorderTraversal_non_recursive(Node* _node) const
173 {
174     if (_node == nullptr) return;
175     std::stack<Node*> nodePointers;
176     nodePointers.push(_node);
177     Node* last = nullptr;
178     Node* cur = nullptr;
179     while (!nodePointers.empty())
180     {
181         cur = nodePointers.top();
182         if ((cur->left == nullptr && cur->right == nullptr) || last != nullptr && (last == cur->left || last == cur->right))
183         {
184             std::cout << cur->data << " ";
185             nodePointers.pop();
186             last = cur;
187         }
188         else
189         {
190             if (cur->right != nullptr) nodePointers.push(cur->right);
191             if (cur->left != nullptr) nodePointers.push(cur->left);
192         }
193     }
194 }
195 
196 
197 #endif // !__BINARYTREE_H__