二叉树的前序 中序 后续 递归与非递归 C++

#include <iostream>
#include<vector>
#include<stack>
#include<algorithm>
#include<set>
#include<set>
#include<queue>
#include<map>
#include<unordered_map>
using namespace std;


//二叉树的三种遍历，递归与非递归
struct TreeNode
{
	int val;
	struct	TreeNode *left;
	struct	TreeNode *right;
	TreeNode(int v) :val(v), left(nullptr), right(nullptr) {};//构造函数
};
void visit(TreeNode *root)
{
	cout << root->val << " ";
}

void pre_order1(TreeNode *root) {//先序遍历递归
	if (root != nullptr) {
		visit(root);
		pre_order1(root->left);
		pre_order1(root->right);
	}

}
void pre_order2(TreeNode *root) {//先序遍历非递归
	if (root == nullptr)
		return;
	stack<TreeNode*>s;
	TreeNode *p = root;
	while (!s.empty() || p) {//这个while 一定要记住
		while (p) {//这个while  一定要记住
			visit(p);
			s.push(p);
			p = p->left;
		}
		if (!s.empty()) {//这个if  一定要记住
			TreeNode *temp = s.top();
			s.pop();
			if (temp->right)
				p = temp->right;
		}
	}
}

void in_order1(TreeNode *root) {//中序遍历递归
	if (root != nullptr) {
		in_order1(root->left);
		visit(root);
		in_order1(root->right);
	}
}


void in_order2(TreeNode *root) {//中序遍历非递归
	if (root == nullptr)
		return;
	stack<TreeNode*>s;
	TreeNode *p = root;
	while (!s.empty() || p) {//这个while 一定要记住
		while (p) {//这个while  一定要记住
			s.push(p);
			p = p->left;
		}
		if (!s.empty()) {//这个if  一定要记住
			TreeNode *temp = s.top();
			visit(temp);
			s.pop();
			if (temp->right)
				p = temp->right;
		}
	}
}


void lrd_order1(TreeNode *root) {//后序遍历递归
	if (root != nullptr) {
		lrd_order1(root->left);
		lrd_order1(root->right);
		visit(root);
	}
}

void lrd_order2(TreeNode *root) {//后序遍历非递归
	if (root == nullptr)
		return;
	stack<pair<TreeNode*, int>>s;
	TreeNode *p = root;
	while (!s.empty() || p) {//这个while 一定要记住
		while (p) {//这个while  一定要记住
			s.push(make_pair(p, 0));
			p = p->left;
		}
		if (!s.empty()) {
			pair<TreeNode*, int> temp = s.top();
			s.top().second++;//访问次数加一
			if (s.top().second > 1) {//已经访问结点两次，就要删除结点了
				visit(s.top().first);
				s.pop();
				p = nullptr;//为空的时候  这时候 又回溯到  top, 此时 
				//为空的话，没有 左子树和右子树同样会为2
			}
			else
				p = temp.first->right;//这个右子树可能为空，为空 就代表要出栈父节点，
			//个while不执行，直接到该if分支，此时计数器就为2了
		}
	}
}
int main() {
	/*  这棵树长这样            
                               1
				  /   \
				 2     3
				/ \   / \
			       4  5   N  6
 */
	TreeNode *root = new TreeNode(1);
	root->left = new TreeNode(2);
	root->right = new TreeNode(3);
	root->left->left = new TreeNode(4);
	root->left->right = new TreeNode(5);
	root->right->right = new TreeNode(6);
	pre_order1(root);
	cout << endl;
	pre_order2(root);
	cout << endl;
	in_order1(root);
	cout << endl;
	in_order2(root);
	cout << endl;
	lrd_order1(root);
	cout << endl;
	lrd_order2(root);
	return 0;
}