二叉树非递归算法
‘壹’ 二叉树非递归遍历的算法
以下为先序，中序，后序三种递归算法
#include
#define MAX 30
typedef struct TreeNode
{
char a;
TreeNode *left;
TreeNode *right;
}TreeNode,*BinTree;
typedef struct
{
TreeNode* data[MAX];
int top;
}SeqStack;
void InitStack(SeqStack &S)
{
S.top=0;
}
int StackEmpty(SeqStack S)
{
if(S.top==0)
return 1;
else return 0;
}
int StackFull(SeqStack S)
{
if(S.top==MAX) return 1;
else return 0;
}
void Push(SeqStack &S,TreeNode *node)
{
if(!StackFull(S))
{
S.data[S.top]=node;
S.top++;
}
else cout<<"Stack is full!\n";
}
void Pop(SeqStack &S,TreeNode* &e)
{
if(!StackEmpty(S))
{
S.top--;
e=S.data[S.top];
}
else cout<<"Stack is empty!";
}
TreeNode* GetTop(SeqStack S)
{
if(!StackEmpty(S))
{
TreeNode *node;
node=S.data[S.top-1];
return node;
}
else cout<<"Stack is empty!";
}
void CreateBinTree(BinTree &T)
{
char b;
cin>>b;
if(b=='0')T=NULL;
else
{
T=new TreeNode;
T->a=b;
CreateBinTree(T->left);
CreateBinTree(T->right);
}
}
void Inorder(BinTree T)
{
TreeNode * p;
SeqStack S;
p=T;
InitStack(S);
while(!StackEmpty(S)||p)
{
while(p)
{
Push(S,p);
p=p->left;
}
if(!StackEmpty(S))
{
Pop(S,p);
cout cout<<"\nA----------二叉树的建立\n";
cout<<"\nB----------非递归先序遍历\n";
cout<<"\nC----------非递归中序遍历\n";
cout<<"\nD----------非递归后序遍历\n";
cout<<"\nX----------退出\n";
}
void main()
{
BinTree T;
char ch='\0';
bool flag=true;
while(flag)
{
info();
cin>>ch;
switch(ch)
{
case'a':
case'A':
cout<<"请按先序次序输入结点，空结点用'0'表示:\n";
CreateBinTree(T);
cout<<"二叉树建立成功!\n";
break;
case'b':
case'B':
cout<<"先序遍历的结果为:\n";
Preorder(T);
break;
case'c':
case'C':
cout<<"中序遍历的结果为:\n";
Inorder(T);
break;
case'd':
case'D':
cout<<"后序遍历的结果为:\n";
Postorder(T);
break;
case'x':
case'X':
flag=false;
break;
default:
cout<<"输入无效,请重新输入!\n";
}
}
}
‘贰’ 《数据结构》遍历二叉树的非递归算法的疑问。
首先敬仰一下楼主的勤奋！
我主要针对第二个算法说，我觉得上面这段话也是在讲第二个算法。其实两个算法差不太多。
1. 栈顶记录中的指针其实就是指栈顶，每次push()进去或者pop()出来的那个p。他代表的是正在访问的节点得下一个节点。比如，访问一个树t的左子树t->lchild时，栈顶就是t；访问t->lchild->lchild时，栈顶就是t->lchild。访问t->rchild时，栈顶为NULL；访问t->lchild->rchild时，栈顶为t；访问t->rchild->lchild时，栈顶也是t；访问t->rchild->rcchild时，栈顶仍为NULL。他的意义就是，在访问完了当前的子树之后，就会去访问栈顶记录的指针对应的节点的数据。
2. 关于“工作记录”那个词，我觉得还是别深究了。那段话意思是要仿照编译器把递归编译成迭代的思路来自己写迭代算法，可是实际上后面给出的算法里根本没有严格执行上述思路，写出来的算法并不是严格意义上的可以一般性替换递归的迭代算法。所以追究那个词也没意义，明白迭代遍历的算法怎么用就够了。等以后对递归有了更深刻的认识，自然就明白了。其实就是函数递归调用自身之前像中断那样保存自己的工作环境和进度。
3. （2）句并不矛盾。他说“指针为空时”和“指针指向的xxx”中间不是有句“退回上一层”么，那就表示pop()，于是原来那个在栈顶的空指针弹出去了，原来在第二位的指针现在到了栈顶。于是后面那句指的是对这个指针进行操作。
‘叁’ 二叉树中序非递归遍历算法
对的，实际上如果p=0，是往左探索到头的意思。先要往左探索到头，只有到头了之后才退栈，看右子树。
探索的过程一直是p=p->lchild，如果p左边没有节点了，p->lchild=nullptr了，就说明到头了，开始执行if的第二个分支：
pop(s,p)实际上是恢复了p上一个状态，也就是那个叶子节点；
visit(p)，中序访问就是每pop一个紧接着就访问一个就是了；
p=p->rchild，访问右边，当然，如果右边还没有，下次pop的就是p的上上个状态了，这相当于是从一个叶子节点离开。以此类推。
不明白的可以继续问。
中序