目录
节点定义
二叉树
前序遍历
递归
非递归
中序遍历
递归
非递归
后序遍历
递归
非递归1
非递归2
非递归3
非递归4
层序遍历
序列相同的二叉树
节点定义 template<typename T>class TreeNode {public: T data; TreeNode<T>* left, * right; TreeNode() :left(nullptr), right(nullptr) {} TreeNode(const T& data) :data(data), left(nullptr), right(nullptr) {}}; 二叉树 #include<iostream>#include<algorithm>#include<stack>#include<queue>#include<vector>#include<string>using namespace std;template<typename T>class BinaryTree {private: TreeNode<T>* root; void destroy(TreeNode<T>**); void pre_order_traversal(TreeNode<T>*)const; void in_order_traversal(TreeNode<T>*)const; void post_order_traversal(TreeNode<T>*)const ;public: BinaryTree(); void pre_order_traversal()const; void pre_order_traversal_non_recursive()const; void in_order_traversal()const; void in_order_traversal_non_recursive()const; void post_order_traversal()const; void post_order_traversal_non_recursive()const; void post_order_traversal_non_recursive2()const; void post_order_traversal_non_recursive3()const; void post_order_traversal_non_recursive4()const; void level_order_traversal()const;}; 前序遍历 递归 /** * 前序遍历 */template<typename T>void BinaryTree<T>::pre_order_traversal()const{ if (this->root != nullptr) { pre_order_traversal(this->root); } cout << endl;} 非递归 /** * 非递归前序遍历 */template<typename T>void BinaryTree<T>::pre_order_traversal_non_recursive()const{ stack<TreeNode<T>*> s; TreeNode<T>* p = this->root; while (p != nullptr || !s.empty()) { //一直向左子树访问 while (p) { cout << p->data << ' '; if (p->right != nullptr) { //存储右子树 s.push(p->right); } p = p->left; } if (!s.empty()) { //右子树 p = s.top(); s.pop(); } } cout << endl;} 中序遍历 递归 /** * 中序遍历 */template<typename T>void BinaryTree<T>::in_order_traversal()const{ if (this->root != nullptr) { in_order_traversal(this->root); } cout << endl;} 非递归 /** * 非递归中序遍历 */template<typename T>void BinaryTree<T>::in_order_traversal_non_recursive()const{ stack<TreeNode<T>*> s; TreeNode<T>* p = this->root; while (p != nullptr || !s.empty()) { //压入当前节点 while (p != nullptr) { s.push(p); p = p->left; } //左子树已经访问完了，开始访问根 if (!s.empty()) { p = s.top(); s.pop(); cout << p->data << ' '; //右子树 p = p->right; } } cout << endl;} 后序遍历 递归 /** * 后序遍历 */template<typename T>void BinaryTree<T>::post_order_traversal()const{ if (this->root != nullptr) { post_order_traversal(this->root); } cout << endl;} 非递归1 /** * 非递归后序遍历 */template<typename T>void BinaryTree<T>::post_order_traversal_non_recursive()const{ stack<TreeNode<T>*> s; TreeNode<T>* p = this->root, *pre = nullptr; while (p != nullptr || !s.empty()) { //压入当前节点 while (p!=nullptr) { s.push(p); p = p->left; } p = s.top(); //如果没有右子树或者右子树已经访问过了，那么就可以访问根节点 if (p->right == nullptr || p->right == pre) { cout << p->data << ' '; pre = p; s.pop(); p = nullptr; } else { //访问右子树 p = p->right; } } cout << endl;} 非递归2 /** * 非递归后序遍历 */template<typename T>void BinaryTree<T>::post_order_traversal_non_recursive2()const{ stack<TreeNode<T>*> s; TreeNode<T>* p = this->root, * pre = nullptr; if (p == nullptr)return; s.push(p); while (!s.empty()) { p = s.top(); //没有左子树和右子树，或者上次访问的的节点是左子树或右子树 if ((p->left == nullptr && p->right == nullptr) || ((p->left == pre || p->right == pre) && pre != nullptr)) { cout << p->data << ' '; pre = p; s.pop(); } else { //先压入右子树，再压入左子树，这样取的时候是反过来的 if (p->right != nullptr) { s.push(p->right); } if (p->left != nullptr) { s.push(p->left); } } } cout << endl;} 非递归3 /** * 非递归后序遍历 */template<typename T>void BinaryTree<T>::post_order_traversal_non_recursive3()const{ stack<TreeNode<T>*> s; TreeNode<T>* p = this->root, *pre = nullptr; //一直往左子树访问 while (p != nullptr) { s.push(p); p = p->left; } while (!s.empty()) { p = s.top(); //如果右子树为空或者访问过，则可以访问根 if (p->right == nullptr || p->right == pre) { cout << p->data << ' '; s.pop(); pre = p; } else { //访问右子树 p = p->right; //一直往左子树访问 while (p) { s.push(p); p = p->left; } } } cout << endl;} 非递归4 /** * 非递归后序遍历 */template<typename T>void BinaryTree<T>::post_order_traversal_non_recursive4()const{ stack<TreeNode<T>*> s; //当前节点的右子树是否访问过的栈 stack<bool> visited; bool flag; TreeNode<T>* p = this->root; while (p != nullptr || !s.empty()) { //一直往左子树访问 while (p) { s.push(p); //还没有访问过右子树 visited.push(false); p = p->left; } p = s.top(); flag = visited.top(); //右子树为空或访问过了 if (p->right == nullptr || flag) { cout << p->data << ' '; s.pop(); visited.pop(); p = nullptr; } else { p = p->right; visited.pop(); //访问过右子树 visited.push(true); } } cout << endl;} 层序遍历 /** * 层序遍历 */template<typename T>void BinaryTree<T>::level_order_traversal()const{ queue<TreeNode<T>*> q; if (this->root != nullptr) { q.push(this->root); } TreeNode<T>* p; while (!q.empty()) { p = q.front(); q.pop(); cout << p->data << ' '; if (p->left != nullptr) { q.push(p->left); } if (p->right != nullptr) { q.push(p->right); } } cout << endl;} 序列相同的二叉树
前序遍历和后序遍历相同的二叉树
TLR
LRT
显然只有根节点
前序遍历和中序遍历相同的二叉树
TLR
LTR
---去掉L----->
TR
显然：非叶子结点只有右子树的二叉树
中序遍历和后序遍历相同的二叉树
LTR
LRT
---去掉R----->
LT
显然：非叶子结点只有左子树的二叉树