hanyeah

二叉树的遍历有三种方式：前序遍历、中序遍历、后序遍历，都是用递归方式实现的，很简单也很清晰。

同学问了一个问题，如何用非递归方式实现二叉树的遍历。

本来以为很简单，因为递归转非递归之前也写过，但是实际试了一下，没有那么简单。

作为一道很经典的面试题，网上一搜一大堆，比如：https://www.cnblogs.com/SHERO-Vae/p/5800363.html。

https://www.jianshu.com/p/12848eef3452

大多数都是很复杂的逻辑，而且没有通用的方法，理解起来比较困难。也没有通用性。

这道题的目的是什么呢？是为了考我们逻辑？

应该先把问题抽象，建立数学模型，然后设计算法，一个好的算法应该能解决一类问题，而不是一个问题。

我认为这道题要考察的是计算机函数调用的知识。要求我们了解计算机函数调用的实现原理，模拟计算机函数调用的过程。

计算机函数调用的过程比较复杂，可以粗略看一下：https://www.jianshu.com/p/ea9fc7d2393d

三种遍历方式都用js实现了一下，代码如下：

var t = {};
for(var i = 0; i < 10; i++){
	var k = Math.floor(Math.random()*20);
	treeInsert(t, {key:k});
	console.log("插入：", k);
}
treeInsert(t, {key:10});
console.log(t);

console.log = function(...arg){
	for(var i = 0; i < arg.length; i++){
		document.write(arg[i],'<br/>');
	}
}

console.log("前序遍历：");
preOrderTreeWalk(t.root);
console.log("非递归前序遍历：");
nonRecursivePreOrderTreeWalk(t.root);

console.log("中序遍历：");
inOrderTreeWalk(t.root);
console.log("非递归中序遍历：");
nonRecursiveInOrderTreeWalk(t.root);

console.log("后序遍历：");
postOrderTreeWalk(t.root);
console.log("非递归后序遍历：");
nonRecursivePostOrderTreeWalk(t.root);


/**
 * 中序遍历
 * @param
 * @return
 */
function inOrderTreeWalk(x){
	if(x){
		inOrderTreeWalk(x.left);
		console.log(x.key);
		inOrderTreeWalk(x.right);
	}
}
/**
 * 非递归中序遍历
 * @param
 * @return
 */
function nonRecursiveInOrderTreeWalk(x){
	var stack = [x];
	var next = 'left';
	var n = 1;
	while(n > 0){
		x = stack[n - 1];
		if(x){
			if(next=='left'){
				stack.push('log');
				stack.push(x.left);
				// next = 'left';
				n += 2;
				continue;
			}
			if(next=='log'){
				console.log(x.key);
				next = 'right';
			}
			if(next == 'right'){
				stack.push('end');
				stack.push(x.right);
				next = 'left';
				n += 2;
				continue;
			}
		}
		stack.pop();
		next = stack.pop();
		n -= 2;
	}
}

/**
 * 前序遍历
 * @param 
 * @return
 */
function preOrderTreeWalk(x){
	if(x){
		console.log(x.key);
		preOrderTreeWalk(x.left);
		preOrderTreeWalk(x.right);
	}
}

/**
 * 非递归前序遍历
 * @param
 * @return
 */
function nonRecursivePreOrderTreeWalk(x){
	var stack = [x];
	var next = 'log';
	var n = 1;
	while(n > 0){
		x = stack[n - 1];
		if(x){
			if(next == 'log'){
				console.log(x.key);
				next = 'left';
			}
			if(next=='left'){
				stack.push('right');
				stack.push(x.left);
				next = 'log';
				n += 2;
				continue;
			}
			if(next=='right'){
				stack.push('end');
				stack.push(x.right);
				next = 'log';
				n += 2;
				continue;
			}
		}
		stack.pop();
		next = stack.pop();
		n -= 2;
	}
}

/**
 * 后序遍历
 * @param
 * @return
 */
function postOrderTreeWalk(x){
	if(x){
		postOrderTreeWalk(x.left);
		postOrderTreeWalk(x.right);
		console.log(x.key);
	}
}
/**
 * 非递归后序遍历
 * @param
 * @return
 */
function nonRecursivePostOrderTreeWalk(x){
	var stack = [x];
	var next = 'left';
	var n = 1;
	while(n > 0){
		x = stack[n - 1];
		if(x){
			if(next=='left'){
				stack.push('right');
				stack.push(x.left);
				// next = 'left';
				n += 2;
				continue;
			}
			if(next=='right'){
				stack.push('log');
				stack.push(x.right);
				next = 'left';
				n += 2;
				continue;
			}
			if(next == 'log'){
				console.log(x.key);
			}
		}
		stack.pop();
		next = stack.pop();
		n -= 2;
	}
}

/**
 * 插入
 * @param
 * @param
 * @return
 */
function treeInsert(t, z){
	var y = null;
	var x = t.root;
	while(x){
		y = x;
		if(z.key < x.key){
			x = x.left;
		}
		else {
			x= x.right;
		}
	}
	z.parent = y;
	if(!y){
		t.root = z;
	}
	else if(z.key < y.key){
		y.left = z;
	} else {
		y.right = z;
	}
}

写得不规范，最近在学习《深入理解计算机系统》，等学会了之后再改进。

https://github.com/hanyeah/lianxi/tree/master/非递归实现二叉树遍历