前言

本文主要使用C++ 实现二叉树的遍历：

  1. 前序，中序，后序遍历的递归和非递归实现
  2. 层序遍历
  3. 深度优先遍历

结点数据结构

1
2
3
4
5
6
7
// Definition for binary tree
 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

前序遍历

递归实现

1
2
3
4
5
6
7
void preOrder(TreeNode* root){
    if(root != NULL){
        cout << root->val << " ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

非递归实现

思路：

  1. 初始化一个栈用于存储结点指针
  2. 若结点非空，访问其值，然后将该结点push入栈。并将左孩子置为当前结点。
  3. 若结点为空，那么将当前结点置为栈顶结点的右孩子，并弹出栈顶结点。
  4. 重复2，3，直到栈为空或者无结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void preOrder(TreeNode* root){
    if(root == NULL) return;
    stack<TreeNode*> S;
    TreeNode* node = root;
    while(node!=NULL || !S.empty()){
    	if(node != NULL)}{
       		 cout << node->val << " "; 
 			 S.push(node);
        	  node = node->left;
    	}
    	else{
        	node = S.top()->right;
             S.pop();
    	}  
    }
}

中序遍历

递归实现

1
2
3
4
5
6
7
void preOrder(TreeNode* root){
    if(root != NULL){
        preOrder(root->left);
        cout << root->val << " ";
        preOrder(root->right);
    }
}

非递归实现

思想同前序遍历一致，利用栈来实现，唯一不同之处就是访问结点的顺序是在结点出栈的时候才进行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void preOrder(TreeNode* root){
    if(root == NULL) return;
    stack<TreeNode*> S;
    TreeNode* node = root;
    while(node!=NULL || !S.empty()){
    	if(node != NULL)}{
 			 S.push(node);
        	  node = node->left;
    	}
    	else{
            cout << node->val << " "; 
        	node = S.top()->right;
             S.pop();
    	}  
    }
}

后续遍历

递归实现

1
2
3
4
5
6
7
void preOrder(TreeNode* root){
    if(root != NULL){
        preOrder(root->left);
        preOrder(root->right);
        cout << root->val << " ";
    }
}

非递归实现

难！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//后序遍历
void PostOrderWithoutRecursion(BTNode* root)
{
	if (root == NULL)
		return;
	stack<BTNode*> s;
	//pCur:当前访问节点，pLastVisit:上次访问节点
	BTNode* pCur, *pLastVisit;
	//pCur = root;
	pCur = root;
	pLastVisit = NULL;
	//先把pCur移动到左子树最下边
	while (pCur)
	{
		s.push(pCur);
		pCur = pCur->lchild;
	}
	while (!s.empty())
	{
		//走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
		pCur = s.top();
		s.pop();
		//一个根节点被访问的前提是：无右子树或右子树已被访问过
		if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
		{
			cout << setw(4) << pCur->data;
			//修改最近被访问的节点
			pLastVisit = pCur;
		}
		/*这里的else语句可换成带条件的else if:
		else if (pCur->lchild == pLastVisit)//若左子树刚被访问过，则需先进入右子树(根节点需再次入栈)
		因为：上面的条件没通过就一定是下面的条件满足。仔细想想！
		*/
		else
		{
			//根节点再次入栈
			s.push(pCur);
			//进入右子树，且可肯定右子树一定不为空
			pCur = pCur->rchild;
			while (pCur)
			{
				s.push(pCur);
				pCur = pCur->lchild;
			}
		}
	}
	cout << endl;
}
--------------------- 
作者：苏叔叔 
来源：CSDN 
原文：https://blog.csdn.net/zhangxiangDavaid/article/details/37115355 
版权声明：本文为博主原创文章，转载请附上博文链接！

层次优先遍历

使用队列来实现，每访问一个结点就将该结点左右孩子（如果有）加入队列末尾，然后将结点从队头弹出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void levelOrder(TreeNode* root){
    if(root == NULL) return;
    queue<TreeNode*> Q;
    Q.push(root);
    while(!Q.empty()){
        TreeNpde* node = Q.front();
        Q.pop();
        cout << node->val << " ";
        if(node->left != NULL)
            Q.push(node->left);
        if(node->right != NULL)
            Q.push(node->right);
    }
}

深度优先遍历

使用栈来实现，原理同前序，中序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
void depthOrder(TreeNode* root){
    if(root == NULL) return;
    stack<int> S;
    S.push(root);
    while(!S.empty()){
       	TreeNode* node = S.pop();
       	cout << node->val << " ";
        if(node->left != NULL)
            S.push(node->left);
        if(node->right != NULL)
            S.push(node->right);
    }
}