二叉树非递归遍历算法
A. 怎样实现二叉树的前序遍历的非递归算法
在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构
总结先根遍历得到的非递归算法思想如下：
1）入栈，主要是先头结点入栈，然后visit此结点
2）while，循环遍历当前结点，直至左孩子没有结点
3）if结点的右孩子为真，转入1）继续遍历，否则退出当前结点转入父母结点遍历转入1）
先看符合此思想的算法：
[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空，就有问题
}
pBiNode = pBiNode->rchild;
}
return 0;
}
B. 求一个二叉树的后序遍历非递归算法
// 中序遍历伪代码：非递归版本，用栈实现，版本2
void InOrder2(TNode* root)
{
Stack S;
if( root != NULL )
{
S.push(root);
}
while ( !S.empty() )
{
TNode* node = S.pop();
if ( node->bPushed )
{ // 如果标识位为true,则表示其左右子树都已经入栈，那么现在就需要访问该节点了
Visit(node);
}
else
{ // 左右子树尚未入栈，则依次将 右节点，根节点，左节点 入栈
if ( node->right != NULL )
{
node->right->bPushed = false; // 左右子树均设置为false
S.push(node->right);
}
node->bPushed = true; // 根节点标志位为true
S.push(node);
if ( node->left != NULL )
{
node->left->bPushed = false;
S.push(node->left);
}
}
}
}
对比先序遍历，这个算法需要额外的增加O(n)的标志位空间。另外，栈空间也扩大，因为每次压栈的时候都压入根节点与左右节点，因此栈空间为O(n)。时间复杂度方面，每个节点压栈两次，作为子节点压栈一次，作为根节点压栈一次，弹栈也是两次。因此无论从哪个方面讲，这个方法效率都不及InOrder1。
后序
void postOrder(TreeNode<T> *root)
{
stack<TreeNode<T>*> st;
TreeNode<T> *p = root;
TreeNode<T> *pre = NULL;//pre表示最近一次访问的结点
while(p || st.size()!=0)
{
//沿着左孩子方向走到最左下 。
while(p)
{
st.push(p);
p = p->left;
}
//get the top element of the stack
p = st.top();
//如果p没有右孩子或者其右孩子刚刚被访问过
if(p->right == NULL || p->right == pre)
{
/ isit this element and then pop it
cout << "visit: " << p->data << endl;
st.pop();
pre = p;
p = NULL;
}
else
{
p = p->right;
}
}//end of while(p || st.size()!=0)
}
C. c语言二叉树非递归遍历
我们今天讲了一点
我写了下函数部分。。其实我也不太懂！
void PreOrderTraverse(struct tree *p) /*进行先序遍历*/
{ top=0;
bool;
do
{
while(p)
{
s[top]=p;
top++;
p=p->lch;
top--;
if(top==0)
bool=0;
else{
top--;
p=s[top];
printf(p->data);
p=p->rch;
}
}while(bool)
}
void InOrderTraverse(struct tree *p) /*进行中序遍历*/
{
top=0;
bool;
do
{
while(p)
{
s[top]=p;
top++;
p=p->lch;
if(top==0)
bool=0;
else{
top--;
p=s[top];
printf(p->data);
p=p->rch;
}
}while(bool)
}
后序遍历我也不怎么会写！不过我可以给你说一下原理：
先是一个p->data入栈，入栈的时候给它标记下，用i=1记一下，
然后是他的左子树，p=p->lch;p->data要出栈，这时候做一次判断。看P的标记i是多少，是1的话就不让他出来，返回去并且i+1，变成2；然后继续前面的动作!等到第二次出栈时做同样的判断，i=2，就出栈！并输出！！希望对你有所帮助！
D. 二叉树先序遍历递归算法和非递归算法本质区别
在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构
总结先根遍历得到的非递归算法思想如下：
1）入栈，主要是先头结点入栈，然后visit此结点
2）while，循环遍历当前结点，直至左孩子没有结点
3）if结点的右孩子为真，转入1）继续遍历，否则退出当前结点转入父母结点遍历转入1）
先看符合此思想的算法：
[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空，就有问题
}
pBiNode = pBiNode->rchild;
}
return 0;
}
E. 二叉树的非递归遍历
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
typedef struct BiTNode
{
int data;
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
void visit(int e)
{
printf("->%d",e);
}
void InitBiTree(BiTree &T)// 操作结果：构造空二叉树T
{
T=NULL;
}
void CreateBiTree(BiTree &T)
//按先序次序输入二叉树中结点的值,构造二叉链表表示的二叉树T。变量Nil表示空(子)树。
{
int number;
scanf("%d",&number); // 输入结点的值
if(number==0) // 结点的值为空
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)// 初始条件：二叉树T存在。操作结果：销毁二叉树T
{
if(T) // 非空树
{
DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
//二叉树T存在，Visit是对结点操作的应用函数,先序递归遍历T，对每个结点调用函数Visit一次且仅一次
{
if(T) //T不为空时遍历
{
Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
//二叉树T存在，Visit是对结点操作的应用函数，中序递归遍历T，对每个结点调用函数Visit一次且仅一次
{
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
// 二叉树T存在，Visit是对结点操作的应用函数，后序递归遍历T，对每个结点调用函数Visit一次且仅一次
{
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main()
{
char m;
BiTree T;
InitBiTree(T); // 初始化二叉树T
do{
printf("\n");
printf("##################二叉树的基本操作###########################\n");
printf("×××××××××1.二叉树的创建××××××××××××××\n");
printf("×××××××××2.先序递归遍历二叉树×××××××××××\n");
printf("×××××××××3.中序递归遍历二叉树×××××××××××\n");
printf("×××××××××4.后序递归遍历二叉树×××××××××××\n");
printf("×××××××××5.退出程序××××××××××××××××\n");
printf("#############################################################\n");
printf("请输入你的选择:");
scanf("%c",&m);
switch(m) {
case '1':
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，如：（1 2 3 0 0 4 5 0 6 0 0 7 0 0 0）\n");
printf("\n请按先序次序输入二叉树中结点的值：");
CreateBiTree(T); // 建立二叉树T
break;
case '2':
printf("先序递归遍历二叉树： ");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
break;
case '3':
printf("\n中序递归遍历二叉树： ");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
break;
case '4':
printf(" \n后序递归遍历二叉树：");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
break;
case '5':break;
default:
printf("输入的字符不对，请重新输入!");
break;
}
getchar();
}while(m!='5');
}
F. 二叉树后序遍历非递归算法程序跪求解释
一，大循环中的第一个循环，当前节点一直往左走一直走到头，并且把走过的节点压栈，这个循环遍历完成后，栈里面都是左边走过但是右边还没有走过的节点
二，从最左边那个没有更左的那个节点，它位于栈顶，因为这时栈顶不是一个右节点，第二个循环跳过，然后把栈顶结点的右节点标记为r并以此作为根节点重复之前的操作
回溯：
因为一直往下层走，总会遇到既没有左节点有没有右节点的节点，就是叶子节点，就开始往回退 取他的右节点，取之前会把该节点标记为r，但是他没有右节点，为null，就会跳过第一个循环，来到第二个，那么这个叶子就从栈中pop掉，新的栈顶结点是那个叶子的父节点，如果没有右节点，那他就成了叶子，更简单，如果有右节点，那么继续二
一步一步推就是这样子，需要考虑所有情况，会把问题想复杂，但是利用递归的思想就好想了
参考递归算法
void preOrder2(BinTree *root)
{
preOrder(root->lchild);
preOrder(root->rchild);
}
第一个函数就是第一个小循环，只走左边，然后把新得到的节点作为根节点，继续调用第一个函数，得到左节点，然后再作为根节点，直到左节点为空；
第二个函数就是最后一个if，非递归算法中是从栈顶取，就是左边走过了的节点，相当于递归中，第一个函数执行完已经返回，然后取他的右节点作为根节点，继续递归
G. 二叉树中序遍历的非递归算法
推荐这篇文章，把二叉树的前序、中序和后续的递归和非递归算法都讲了。
http://www.cppblog.com/ngaut/archive/2006/01/01/2351.html
H. 二叉树非递归遍历算法c语言
给你个离散数学中的算法:
先序:
1. 将根节点放入栈中
2.while 栈不空
do
3. 从栈中取出一个节点,并visit
4. 将这个节点右孩子,左孩子(如果存在)分别放入栈中
endwhile
中序:
1.将根节点放入栈中
2.while 栈不空
do
3. 从栈中取出一个节点
4. if 节点被标记
5. then visit 该节点 并将右孩子放入栈(如果存在)
else
6. 将该节点标记并入栈
7. 将该节点的左孩子入栈(如果存在)
endif
endwhile
后序:
1.将根节点放入栈中
2.while 栈不空
do
3. 从栈顶取一节点
4. if 节点被标记
5. then visit 该节点
else
6. 将该节点标记并入栈
7. 将该节点的右孩子,左孩子分别入栈(如果存在)
endif
endwhile
I. 二叉树中序非递归遍历算法
对的，实际上如果p=0，是往左探索到头的意思。先要往左探索到头，只有到头了之后才退栈，看右子树。
探索的过程一直是p=p->lchild，如果p左边没有节点了，p->lchild=nullptr了，就说明到头了，开始执行if的第二个分支：
pop(s,p)实际上是恢复了p上一个状态，也就是那个叶子节点；
visit(p)，中序访问就是每pop一个紧接着就访问一个就是了；
p=p->rchild，访问右边，当然，如果右边还没有，下次pop的就是p的上上个状态了，这相当于是从一个叶子节点离开。以此类推。
不明白的可以继续问。
中序
J. 先序遍历二叉树的非递归算法
InitStack(S);//初始化栈
p=T;//取栈顶
while(P||!StackEmpty(S)){ //P存在或者栈非空
if(p) { //p非空，即左子树或者右子树存在
Push(S,p); //将左子树入栈
p=p->lchild; //取下一个左子树
}
else{
Pop(S,p); //出栈，相当于先序遍历了，因为左子树都TMD入栈了，现在反向输出
p=p->rchild; //弹出一个左子树，就同时取其右子树右子树，然后又跳到这个if的最开头那里，p存在的那个分支。接下来再取右子树的左子树
}
}
//其实，用递归也许你更能理解一些。但是，递归本质上也是压栈，只不过是程序压栈，还不如这个效率高