前言
在数据结构教材中的中序遍历非递归形式过程中发现每次遍历到叶子结点的时候，都会把NULL空结点放入栈中。
从而让我思考这个空结点是否有必要放入栈中？
为了顺理成章引出该问题。文章的前半部分讲述中序遍历的基本过程。
不想看的同学直接看最后一部分。想要加深对二叉树遍历的印象的同学推荐还是浏览一遍。
中序遍历
递归形式
要求形式一：不加入空结点
① 先遍历左结点
② 遍历完中结点后，假如有右节点就遍历右节点；没有则返回上级。
按照要求可以写出这样的递归形式
InOrderTraverse(BiTree* tree)
{
if(tree->lchild)//满足要求①
InOrderTraverse(tree->lchlid);
Visit(tree->data);
if(tree->rchild)//满足要求②，其中一部分
InOrderTraverse(tree->rchild);
//在函数结束后就会返回至上级调用该函数的地方
}
也可以这样理解中序遍历
要求形式二：加入空结点
① 如果该节点存在，就按要求遍历左中右；不存在就返回。
InOrderTraverse(BiTree* tree)
{
if(tree)
{
InOrderTraverse(tree->lchild);
Visit(tree->data);
InOrderTraverse(tree->rchild);
}
}
非递归形式
依照递归形式的执行过程中递归工作栈的状态变化模拟出非递归形式。
为了引出不加空结点的方法，先按照 要求二：加入空结点 的理解。
1、这里需要一个堆栈s，用来模拟每次递归过程中的工作栈。
2、用一个最外层的while循环表示每一个新结点的调用与返回。
因此代码会是这样
bool InOrderTraverse(BiTree* tree, TreeVisiter visit)
{
std::stack<BiTree*> s;
s.push(tree);
//继续分析 要求二方式的递归 中栈里面存的是什么的过程中，
//会发现栈中存入的是每一个未被访问过的结点和空结点。
//所以栈未空时，表示树遍历结束
while(!s.empty())
{
//...
}
return true;
}
步骤1、获取栈顶结点，如果结点存在，就先遍历左结点。
tree = s.top();
if(tree)
{
s.push(tree->lchild);//注意这里可以会把空结点存入栈中。
continue;//开始下一个循环，因为将外层while循环定义为访问每个新结点
}
步骤2、如果结点不存在，则先退出空节点，再访问该结点。最后访问右孩子。
s.pop();
tree = s.top();//c++中top()是获取栈顶，不退栈
s.pop();
if(!visit(tree->data)) return false;
s.push(tree->rchild);//这里的右孩子可能是空结点
结合后代码就会变为如下
bool InOrderTraverse(BiTree* tree, TreeVisiter visit)
{
std::stack<BiTree*> s;
s.push(tree);
while(!s.empty())
{
//------------------------------
//可优化处
tree = s.top();
if(tree)
{
s.push(tree->lchild);//注意这里可以会把空结点存入栈中。
continue;//开始下一个循环
}
//------------------------------
s.pop();
if(!s.empty())
{
tree = s.top();
s.pop();
if(!visit(tree->data)) return false;
s.push(tree->rchild);
}
}
return true;
}
考虑整个while循环过程中，会发现在 可优化处 的地方可以用一个while稍微优化一下。
//访问空结点代码
bool InOrderTraverse(BiTree* tree, TreeVisiter visit)
{
std::stack<BiTree*> s;
s.push(tree);
while(!s.empty())//外层while循环
{
//------------------------------
while((tree = s.top()) && tree)
s.push(tree->lchild);
//------------------------------
s.pop();//弹出空结点
if(!s.empty())
{
tree = s.top();
s.pop();
if(!visit(tree->data)) return false;
s.push(tree->rchild);
}
}
return true;
}
假如优化成这样的话，那么对外层while循环的定义也就和前边的不一样了。
不再是 “用一个最外层的while循环表示每一个新结点的调用与返回。”（也许你可能忘了）
就变成两个定义了：
外层while循环新定义1：如果该结点存在，访问当前结点的最左结点，再右移一位。
外层while循环新定义2：如果该结点为空结点，则返回至兄弟结点。（如果一直都是NULL，那么就一直返回）
定义1 如下图的 红线 部分
定义2 如下图的 蓝线 部分
中序遍历过程图
空结点是否有必要放入栈中？
问题1：为什么要弹出空结点？
看到代码，给我的第一个反应是：很简单呀，因为外层的while循环多放了一个空结点。
这是第一个原因。
当我尝试在外层的while循环中加入空结点判断，不加入空结点时，发现代码就会陷入死循环。
因为该处弹出空结点并不仅仅是为了弹出外层的while循环中的空结点。
还为了右结点为空时返回至兄弟结点。
问题2：如果在每次入栈之前判断一次是否为空结点会怎么样？会不会减少入栈次数的同时减少判断次数？
不访问空结点
从图像上看，遍历的过程少了一些。主要是少了叶子个数的循环次数。看来 可能 是有效果的。
如果遵循上图的访问规则，外层while循环的定义很明显地就不一样了。
外层while循环在不访问NULL结点的新定义：
访问当前结点的最左结点，然后寻找下一个存在的合适结点（右孩子，否则是右兄弟，否则是右叔叔，否则是右爷爷，否则是右祖父，否则是......）
于是改写了一下代码。
//不访问空结点代码
bool InOrderTraverse_non_recursive_1(BiTree* tree, TreeVisiter visit)
{
std::stack<BiTree*> s;
s.push(tree);
while(!s.empty())
{
tree = s.top();
while(tree->lchild)
{
tree = tree->lchild;
s.push(tree);
}
s.pop();
if(!visit(tree->data)) return false;
tree = tree->rchild;
//寻找下一个存在的合适结点
while(!tree)
{
if(s.empty())//在寻找的过程中可能是最后一个结点了
return true;
tree = s.top();
s.pop();
if(!visit(tree->data)) return false;
tree = tree->rchild;
}
s.push(tree);
}
return true;
}
总结：
在加入栈之前判断下该结点是否为空，只加入不为空的结点，在效率上较加入空结点会有一点点的改进。只是代码长度可能会多那么几行。
网友评论