非递归实现二叉树遍历

Posted on | In | | reads times

关于二叉树充满血泪的一天

用非递归的方式实现二叉树，真的死了好多脑细胞，可能是我太菜了吧

题目描述：
用非递归方式编码对一个二叉树的前、中、后、层次遍历。

输入描述：
第一行一个正整数n(1<=n<=100)，表示二叉树有n个结点。
接下来n行，第i行两个整数li,ri (0<=li,ri<=n) ，分别表示第i个结点的左儿子和右儿子，为0代表空。
保证根为1，保证输入为合法二叉树。

输出描述：
输出四行
第一行为二叉树的前序遍历；
第二行为中序遍历；
第三行为后序遍历；
第四行为层次遍历。
每一行输出n个数，代表该方式遍历的结点的顺序，相邻两个数之间用一个空格相隔。

输入例子：

5
3 2
0 5
0 4
0 0
0 0

输出例子：

1 3 4 2 5
3 4 1 2 5
4 3 5 2 1
1 3 2 4 5

输入给的例子需要进行一定的处理。
处理完成之后得到的是一棵树。

对这棵树进行遍历。

以下是记录了这一天和二叉树遍历的爱恨情仇。

前序遍历

前序遍历就是先根遍历，先根节点，后左子树，然后右子树。
非递归的话，利用栈的结构。
1.（先根节点）从根开始先入栈；
2.（后左子树）一直向左节点遍历并入栈左节点；
3.（再右子树）如果当前节点没有左节点，则出栈，并将当前指针指向栈顶节点，然后指向右节点，开始遍历右子树。
PS：只要当前指针指向的节点存在，则表示遍历到此处，即将该节点放入res中，表示遍历顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var pretraver=function(pRoot){
	var res=[];
	var pCur=pRoot;
	var stack=[];
	stack.push(pRoot);
	while(stack.length!=0){
		if(pCur){
			res.push(pCur.val);
			stack.push(pCur);
			pCur=pCur.left;
		}else{
			pCur=stack.pop();
			pCur=pCur.right;
		}	
	}
	return res;
}

中序遍历

中序遍历就是中根遍历，即先左子树，后根，最后右子树。
非递归，依然使用栈。
1.一直向左遍历，入栈所有经过节点。
2.当前指针为空，则出栈，指针指向出栈节点，并将该节点放入res中，并将该节点右孩子入栈。指针指向右孩子。
3.如果当前指针为空，且栈为空，则表示遍历完了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var intraver=function(pRoot){
	var pCur=pRoot;
	var res=[];
	var stack=[];
	stack.push(pCur);
	var done=true;
	while(!done){
		if(pCur){
			stack.push(pCur);
			pCur=pCur.left;
		}else{
			if(stack.length!=0){
				pCur=stack.pop();
				res.push(pCur.val);
				pCur=pCur.right;
			}else{
				done=false;
			}
		}
	}
	return res;
}

后序遍历

后序遍历就是后根遍历，先左子树，后右子树，再根节点。
非递归实现，需要用到栈。
但是后序有一种简单的思路，就是利用与前序遍历的关系。
后序遍历就是先右后左的先（前）序遍历。
1.先根节点入栈。
2.然后左节点入栈。
3.最后右节点入栈。
PS：每次指向栈顶元素。并出栈。栈顶即为每一轮的右节点。所以即为先右后左。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var lasttraver=function(pRoot){
	var pCur=pRoot;
	var stack=[];
	var res=[];
	stack.push(pCur);
	while(stack.length!=0){
		pCur=stack.pop();
		res.push(pCur.val);
		if(pCur){
			pCur=pCur.left;
			stack.push(pCur);
		}else{
			pCur=pCur.right;
			stack.push(pCur)
		}
	}
	return res;
}

按层遍历

按层遍历特殊一点，需要先进先出，因为是按照从上到下，从左到右的顺序进入存储结构，但是又要从左到右从上到下进行遍历左右节点，所以需要队列，先进先出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var leveltraver=function(pRoot){
	var pCur=pRoot;
	var queue=[];
	queue.push(pCur);
	var res=[];
	while(queue.length!=0){
		res.push(queue.shift().val);
		if(pCur.left){
			queue.push(pCur.left);
		}
		if(pCur.right){
			queue.push(pCur.right);
		}
		pCur=queue[queue.length-1];
	}
	return res;
}

ps：如果有人有需要数据处理部分的代码的，请留言噢。有需要的话我再贴。