二叉树遍历算法的改良
二叉树的深度优先遍历算法都是用递归函数实现的，这是很低效的，起因在于零碎帮你调用了一个栈并做了诸如爱护现场和复原现场等简单的操作，才使得遍历能够用十分简洁的代码实现。二叉树深度优先遍历算法的非递归实现用用户定义的栈来代替零碎栈，也就是用非递归的形式来实现遍历算法，能够失去不小的效率晋升。
二叉树深度优先遍历算法的非递归实现
（1）先序遍历非递归算法
要写出其遍历的非递归算法，其次要工作是用本人定义的栈来代替零碎栈的性能。
以图1所示的二叉树为例，过程为图二所示
初态栈空
- 结点1入栈。
- 出栈，输入栈顶结点1，并将1的左、右孩子结点（2和4）入栈；右孩子先入栈，左孩子后入栈，因为对左孩子的拜访要先于右孩子，后入栈的会先出栈拜访。
- 出栈，输入栈顶结点2，并将2的左、右孩子结点（3和5）入栈。
- 出栈，输入栈顶结点3，3为叶子结点，无孩子，本步无结点入栈。
- 出栈，输入栈顶结点5。
出栈，输入栈顶结点4，此时栈空，进入终态。
遍历序列为1，2，3，5，4。
代码如下
void preorderNonrecursion(BTNode *bt){ if(bt != NULL) { BTNode *Stack[maxSize]; //定义一个栈 int top = -1; //初始化栈 BTNode *p; Stack[++top] = bt; //根结点入栈 while(top != -1) //栈空循环完结 { p = Stack[top--]; //出栈并输入栈顶结点 Visit(p); //Visit()为拜访p的函数 if(p->rchild != NULL) //栈顶结点的右孩子存在，则右孩子入栈 Stack[++top] = p->rchild; if(p->lchild != NULL) //栈顶结点的左孩子存在，则左孩子入栈 Stack[++top] = p->lchild; } }}（2）中序遍历非递归算法
相似于先序遍历，对图1中的二叉树进行中序遍历，各个结点进栈、出栈过程如图3所示。
初态栈空。
- 结点1入栈，1左孩子存在。
- 结点2入栈，2左孩子存在。
- 结点3入栈，3左孩子不存在。
- 出栈，输入栈顶结点3，3右孩子不存在。
- 出栈，输入栈顶结点2，2右孩子存在，右孩子5入栈，5左孩子不存在。
- 出栈，输入栈顶结点5，5右孩子不存在。
- 出栈，输入栈顶结点1，1右孩子存在，右孩子4入栈，4左孩子不存在。
出栈，输入栈顶结点4，此时栈空，进入终态。
遍历序列为3，2，5，1，4。
由以上步骤能够看出，中序非递归遍历过程如下：
- 开始根结点入栈
- 循环执行如下操作：如果栈顶结点左孩子存在，则左孩子进栈；如果栈顶结点左孩子不存在，则出栈并输入栈顶结点，而后查看其右孩子是否存在，如果存在，则右孩子入栈。
- 当栈空时算法完结。
代码如下
void inorderNonrecursion(BTNode *bt){ if(bt != NULL) { BTNode *Stack[maxSize]; int top = -1; BTNode *p; p = bt; /*下边循环实现中序遍历。留神：图3进栈、出栈过程在7中会呈现栈空状态，然而这时遍历还没有完结，因根结点的右子树还没有遍历，此时p非空，依据这一点来维持循环的进行*/ while(top != -1 || p != NULL) { while(p != NULL) //左孩子存在，则左孩子入栈 { Stack[++top] = p; p = p->lchild; } if(top != -1) //在栈不空的状况下出栈并输入出栈结点 { p = Stack[top--]; Visit(p); p = p->rchild; } } }}（3）后序遍历非递归算法
首先写出图1中二叉树进行先序遍历和后序遍历的序列。
先序遍历序列：1、2、3、5、4
后序遍历序列：3、5、2、4、1
把后序遍历序列逆序得：
逆后序遍历序列：1、4、2、5、3
发现，逆后序遍历序列和先序遍历序列有一点的分割，逆后序遍历序列只不过是先序遍历过程中对左右子树遍历程序交换所失去的后果，如图4所示。
因而，只须要将后面的非递归先序遍历算法中对左右子树的遍历程序替换就能够失去逆后序遍历序列，而后将逆后序遍历序列逆序就失去了后序遍历序列。因而须要两个栈，一个栈stack1用来辅助做逆后序遍历（将先序遍历的左、右子树遍历程序替换的遍历形式称为逆后序遍历）并将遍历后果序列压入另一个栈stack2，而后将stack2中的元素全副出栈，所失去的序列即为后序遍历序列。具体过程如图5所示。
初态栈空。
- 结点1如stack1。
- stack1元素出栈，并将出栈结点1入stack2，结点1的左、右孩子存在，左孩子结点2入stack1，右孩子结点4入stack1，这里留神和先序遍历进出栈过程比照，恰好是将其左、右孩子入栈程序调换，以实现拜访程序的调换。
- stack1元素出栈，并将出栈结点4入stack2，结点4的左、右孩子不存在。
- stack1元素出栈，并将出栈结点2入stack2，结点2的左、右孩子存在，左孩子结点3入stack1，右孩子结点5入stack1。
- stack1元素出栈，并将出栈结点5入stack2。
- stack1元素出栈，并将出栈结点3入stack2。
此时stack1空，stack2中元素自顶向下顺次为：3、5、2、4、1，正好为后序遍历序列。
代码如下：
void postorderNonrecursion(BTNode *bt){ if(bt != NULL) { /*定义两个栈*/ BTNode *Stack1[maxSize];int top1 = -1; BTNode *Stack2[maxSize];int top2 = -1; BTNode *p = NULL; Stack1[++top1] = bt; while(top1 != -1) { p = Stack1[top1--]； Stack2[++top2] = p;//留神这里和先序遍历的区别，输入改为入Stack2 /*留神下边这两个if语句和先序遍历的区别，左、右孩子的入栈程序相同*/ if(p->lchild != NULL) Stack1[++top1] = p->lchild; if(p->rchild != NULL) Stack1[++top1] = p->rchild; } while(top2 != -1) { /*出栈序列即为后序遍历序列*/ p = Stack2[top2--]; Visit(p); } }}