非递归实现二叉树遍历
二叉树的遍历有三种方式：前序遍历、中序遍历、后序遍历，都是用递归方式实现的，很简单也很清晰。
同学问了一个问题，如何用非递归方式实现二叉树的遍历。
本来以为很简单，因为递归转非递归之前也写过，但是实际试了一下，没有那么简单。
作为一道很经典的面试题，网上一搜一大堆，比如：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;
}
}写得不规范，最近在学习《深入理解计算机系统》，等学会了之后再改进。