二叉树--普通二叉树的创建和遍历
用 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__
版权声明：本文为teternity原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。