二叉树的四大遍历方法（前中后、层次遍历）（包括typedef 树节点）

• 转载代码：
• 前中后递归遍历
• 前序和中序的迭代写法
• • 前序：
  • 中序
  • • 中序题解

typedef struct BiTNode {
	char data;
	struct BiTNode *rchild, *lchild;
	bool isfirst = true;
}BiTNode, *BiTree ;
 
//创建二叉树
void DLR_DG_createTree(BiTree &T) {
	char c;
	cin >> c;
	if (c == '#')T = NULL;
	else {
		T = new BiTNode;
		T->data = c;
		DLR_DG_createTree(T->lchild);
		DLR_DG_createTree(T->rchild);
	}
}
//先序递归
void DLR_DG_printTree(BiTree T) {
	if (T!=NULL)
	{
		cout << T->data << " ";
		DLR_DG_printTree(T->lchild);
		DLR_DG_printTree(T->rchild);
	}
}
//中序递归
void LDR_DG_printTree(BiTree T) {
	if (T != NULL)
	{
		LDR_DG_printTree(T->lchild);
		cout << T->data << " ";		
		LDR_DG_printTree(T->rchild);
	}
}
//后序递归
void LRD_DG_printTree(BiTree T) {
	if (T != NULL)
	{
		LRD_DG_printTree(T->lchild);
		LRD_DG_printTree(T->rchild);
		cout << T->data << " ";
	}
 
}
 
//先序非递归
void DLR_printTree(BiTree T) {
	stack s;
	if (T == NULL)return;
	BiTree p = T;
	while (!s.empty() || p != NULL) {
		if (p) {
			cout << p->data << " ";
			s.push(p);
			p = p->lchild;
		}
		else {
			p = s.top();
			s.pop();	    
			p = p->rchild;
		}
	}
}
//中序非递归
void LDR_printTree(BiTree T) {
	stack s;
	if (T == NULL)return;
	BiTree p = T;
	while (!s.empty() || p != NULL) {
		if (p) {
			s.push(p);
			p = p->lchild;
		}
		else {
			p = s.top();
			s.pop();
			cout << p->data << " ";
			p = p->rchild;
		}
	}
}
//后序非递归方法一
void LRD_printTree(BiTree T) {
	stack s;
	if (T == NULL)return;
	BiTNode* p = T;
 
	while ( !s.empty()||p != NULL )
	{
		if (p)
		{
			s.push(p);
			p = p->lchild;
		}
		else 
		{
			p = s.top();
			if (p->isfirst == false) {
				cout << p->data << " ";
				s.pop();
				p = NULL;
			}
			else {
				p->isfirst = false;
				p = p->rchild;
			}
		}
	}
}
//后序非递归方法二
void LRD_1_printTree(BiTree T) {
	stack s;
	if (T == NULL)return;
	BiTree p = T;
	BiTree pre = T;
	while (!s.empty() || p != NULL)
	{
		if (p)
		{
			s.push(p);
			p = p->lchild;			
		}
		else
		{
			p = s.top();
			if (p->rchild== pre || p->rchild == NULL) {
				cout << p->data << " ";
				s.pop();
				pre = p;
				p = NULL;
			}
			else
			{
				p = p->rchild;
			}
		}
	}
}
//层次
void CC_printTree(BiTree T) {
	queue Q;
	Q.push(T);
	BiTree p;
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();
		cout << p->data<<" ";
		if (p->lchild) Q.push(p->lchild);
		if (p->rchild) Q.push(p->rchild);
	}
}
 
 
int main() {
	BiTree T;
	cout << "先序遍历创建二叉树" << endl;
	DLR_DG_createTree(T);
 
	cout << "递归先序遍历：";
	DLR_DG_printTree(T);
	cout << endl;
 
	cout << "递归中序遍历：" ;
	LDR_DG_printTree(T);
	cout << endl;
 
	cout << "递归后序遍历：" ;
	LRD_DG_printTree(T);
	cout << endl;
 
	cout << "层次遍历：";
	CC_printTree(T);
	cout << endl;
 
	cout << "中序遍历：";
	LDR_printTree(T);
	cout << endl;
 
	cout << "先序遍历：";
	DLR_printTree(T);
	cout << endl;
 
	cout << "后序遍历：";
	LRD_printTree(T);
	cout << endl;
}
 

递归思想代码都非常类似
前序：

class Solution {
public:
    void traversal(TreeNode* cur, vector& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector preorderTraversal(TreeNode* root) {
        vector result;
        traversal(root, result);
        return result;
    }
};

中序：

  void traversal(TreeNode* cur, vector& vec) {
        if (cur == NULL) return;
        traversal(cur->left, vec);  // 左
        vec.push_back(cur->val);    // 中
        traversal(cur->right, vec); // 右
    }

后序：

void traversal(TreeNode* cur, vector& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
}

由于前序和中序的迭代写法很类似就放在一起了
非递归的三组先中后，有相同的结构

stack s;
BiTree p = T;
while (!s.empty() || p != NULL)
{
    if (p)....
    else....
}

不同的地方在于只需要按照逻辑修改if和else里面的代码就好了。

把握住中序遍历的思想（如下所示），就把握住了先序遍历（只是访问的顺序不一样）：
根节点和所有左子入栈
出栈，访问出栈节点
出栈节点的第一个右节点入栈
访问这个右节点的所有左孩子

class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
    vectorres;
    stack stack;
    while(!stack.empty()||root!=NULL){
       if(root){
           stack.push(root);
           res.push_back(root->val);
           root=root->left;
       }
       else{
           TreeNode* temp=stack.top();
           stack.pop();
           root=temp->right;
       }

    }
    return res;
    }
};

class Solution {
public:
    void inorder(TreeNode *root,vector &res){
        stack stack;
        while(root!=NULL||!stack.empty()){
        if(root!=NULL) {
            stack.push(root);
            root=root->left;
        }
        else {
            TreeNode* temp=stack.top();
            stack.pop();
            res.push_back(temp->val);
            root=temp->right;
        }
        }
 
    }
    vector inorderTraversal(TreeNode* root) {
    vector res;
    inorder(root,res);
    return res;
    }
};

https://blog.csdn.net/qq_52934831/article/details/119121225?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163280647116780265457877%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=163280647116780265457877&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_blogfirst_rank_v2~rank_v29-1-119121225.pc_v2_rank_blog_default&utm_term=%E4%B8%AD%E5%BA%8F&spm=1018.2226.3001.4450