二叉树--普通二叉树的创建和遍历
T_eternity 人气:1用 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__
加载全部内容