二叉树的几种遍历算法及其实现（C/C++）

Reply Share

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树的子树有左右之分，次序不能颠倒。这里对二叉树的几种遍历算法做一下整理，供大家学习。

二叉树的几种遍历算法及其实现（C/C++）

基本结构

二叉树一般采用链式存储结构，结构体中包括data域和两个子树的指针域，其定义如下：

1
2
3
4
5
typedef struct BiTNode{
	int data;  //数据域
	struct BiTNode *lchild; //左子树
	struct BiTNode *rchild; //右子树
}BiTNode,*BiTree;

二叉树的遍历

二叉树的遍历，指的是按照一定的规则和顺序走遍二叉树的所有结点，使得每个节点都被访问一次，而且只被访问一次。
基本的遍历方法有先序、中序和后序遍历算法，并且都有递归和非递归之分。这三种方法的递归算法实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//先序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
    	Visit(T);    //Visit(T)为访问当前节点的操作，如输出该节点的值等
    	PreOrder(T->lchild); //访问左子树
    	PreOrder(T->rchild); //访问右子树
	}
}
//中序遍历
void InOrder(BiTree T){
	if(T!=NULL){
		InOrder(T->lchild);
		Visit(T);
		InOrder(T->rchild);
	}
}
//后序遍历
void PostOrder(BiTree T){
	if(T!=NULL){
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		Visit(T);		
	}
}

对应地，给出以上算法的非递归算法：

先序遍历：
访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素为T,出栈，再先序遍历T的右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void PreOrder(BiTree T){
	stack<BiTree> stack;
	//定义一个指针，用来遍历二叉树
	BiTree p=T;
	//栈不为空或者p不为空时循环
	while(p||!stack.empty()){
		if(p!=NULL){
			//当前节点入栈
			stack.push(p);
			Visit(p);
			//遍历左子树
			p=p->lchild;
		}
		else{    
			p=stack.top();
			stack.pop();  //出栈
			p=p->rchild;
		}	
	}
}

中序遍历
先将T（根节点）入栈，遍历左子树；遍历完左子树返回时，出栈，访问T->data,出栈，再先序遍历T的右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void InOrder(BiTree T){
	stack<BiTree> stack;
	//定义一个遍历二叉树的指针
	BiTree p=T;
	//栈不为空或者p不为空时循环
	while(p|| !stack.empty()){
		if(p!=NULL){
			stack.push(p); //入栈
			p=p->lchild;   //遍历左子树
		}
		else{
			//出栈，访问根节点
			p=stack.top();
			Visit(p);
			stack.pop();
			//访问右子树
			p=p->rchild;
		}
	}
}

后序遍历
T为要遍历树的根指针，后序遍历要求先遍历完左右子树，再访问根结点。

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
//后序遍历(非递归)  
typedef struct BiTNodePost{  
    BiTree biTree;  
    char tag;  
}BiTNodePost,*BiTreePost;  
  
void PostOrder2(BiTree T){  
    stack<BiTreePost> stack;  
    //p是遍历指针  
    BiTree p = T;  
    BiTreePost BT;  
    //栈不空或者p不空时循环  
    while(p != NULL || !stack.empty()){  
        //遍历左子树  
        while(p != NULL){  
            BT = (BiTreePost)malloc(sizeof(BiTNodePost));  
            BT->biTree = p;  
            //访问过左子树  
            BT->tag = 'L';  
            stack.push(BT);  
            p = p->lchild;  
        }  
        //左右子树访问完毕访问根节点  
        while(!stack.empty() && (stack.top())->tag == 'R'){  
            BT = stack.top();  
            //退栈  
            stack.pop();  
            BT->biTree;  
            printf("%c ",BT->biTree->data);  
        }  
        //遍历右子树  
        if(!stack.empty()){  
            BT = stack.top();  
            //访问过右子树  
            BT->tag = 'R';  
            p = BT->biTree;  
            p = p->rchild;  
        }  
    } 
}

广度优先（层次遍历）算法和深度优先遍历
除了上述几种遍历算法之外(从本质上讲，先序、中序、后序遍历都属于深度优先遍历)，还有广度优先算法和深度优先遍历，这里给出这两个算法的实现
广度优先
思路：从顶向下，从左至右的顺序来逐层访问每个结点，这里需要用到的存储结构为 队列 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void LevelOrder(BiTree T){
	BiTree p=T;
	queue<BiTree> queue;
	//根结点入队
	queue.push(p);
	//队列不为空时循环
	while(!queue.empty()){
		//对头元素出列
		p=queue.front();
		//访问p指向的结点
		Visit(p);
		queue.pop();

		if(p->lchild!=NULL){ //左子树不为空，将左子树入队
			queue.push(p->lchild);
		}
		if(p->rchild!=NULL){  //右子树不为空，将右子树入队
			queue.push(p->rchild);
		}
	}
}

深度优先
思路：先遍历根结点，接着遍历左子树，最后遍历右子树，这里借助 栈 来实现深度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void DepthOrder(BiTree T){
	stack<BiTree> stack;
	BiTree p=T;
	stack.push(p);

	while(!stack.empty()){
		p=stack.top();
		Visit(p);   //遍历根结点
		stack.pop(); //出栈

		if(p->rchild){ //右子树入栈
			stack.push(p->rchild);
		}
		if(p->lchild){  //左子树入栈
			stack.push(p->lchild);
		}
	}
}

1