二叉树前序中序后序层序遍历（递归和非递归）
程序员文章站
2022-05-16 14:21:51
...
目录
节点定义
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
显然：非叶子结点只有左子树的二叉树