二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现

Question

要求：遍历的内容应是千姿百态的。
树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。
要求：遍历的内容应是千姿百态的。

Answer 1

#include <iostream>
using namespace std;//二叉树链式存储的头文件
typedef char datatype;//结点属性值类型
typedef struct node // 二叉树结点类型
{
datatype data;
struct node* lchild,*rchild;
}bintnode;
typedef bintnode *bintree;
bintree root;//指向二叉树结点指针
//下面是些栈的操作 为非递归实现做准备
typedef struct stack//栈结构定义
{
bintree data[100];//data元素类型为指针
int tag[100];//为栈中元素做的标记，，用于后续遍历
int top;//栈顶指针
}seqstack;
void push(seqstack *s,bintree t)//进栈
{
s->data[++s->top]=t;
}

bintree pop(seqstack *s) //出栈
{
if(s->top!=-1)
{s->top--;
return(s->data[s->top+1]);
}
else
return NULL;
}

//按照前序遍历顺序建立一棵给定的二叉树
void createbintree(bintree *t)
{
char ch;
if((ch=getchar())== '-')
*t=NULL;
else
{
*t=(bintnode*)malloc(sizeof(bintnode));//产生二叉树根结点
(*t)->data=ch;
createbintree(&(*t)->lchild);//递归实现左孩子的建立
createbintree(&(*t)->rchild);//递归实现右孩子的建立
}
}
//二叉树前序遍历递归实现
void preorder(bintree t)//t是指针变量，而不是结点结构体变量
{if(t)
{
cout<<t->data<<" ";
preorder(t->lchild);
preorder(t->rchild);
}
}
//二叉树前序遍历非递归实现
void preorder1(bintree t)
{
seqstack s;
s.top=-1;//top 的初始值为-1；
while((t)||(s.top!=-1))//当前处理的子树不为空或者栈不为空，则循环
{
while(t)
{
cout<<t->data<<" ";//访问当前子树根结点
s.top++;
s.data[s.top]=t;
t=t->lchild;
}
if(s.top>-1)
{
t=pop(&s);//当前子树根结点出栈
t=t->rchild;//访问其右孩子
}
}
}
//二叉树中序遍历递归算法
void inorder(bintree t)
{
if(t)
{
inorder(t->lchild);
cout<<t->data<<" ";
inorder(t->rchild);
}
}
// 二叉树中序遍历非递归算法
void inorder1(bintree t)
{
seqstack s;
s.top=-1;
while((t!=NULL)||(s.top!=-1))
{
while(t)
{
push(&s,t);
t=t->lchild;//子树跟结点全部进栈
}
if(s.top!=-1)
{
t=pop(&s);
cout<<t->data<<" ";//输出跟结点，其实也就是左孩子或者有孩子（没有孩子的结点是他父亲的左孩子或者有孩子）
t=t->rchild;//进入右孩子访问
}
}
}
//后续递归遍历二叉树
void postorder(bintree t)
{
if(t)
{
postorder(t->lchild);
postorder(t->rchild);
cout<<t->data<<" ";
}
};
//后序遍历 非递归实现
void postorder1(bintree t)
{
seqstack s;
s.top=-1;
while((t)||(s.top!=-1))
{
while(t)
{
s.top++;
s.data[s.top]=t;//子树根结点进栈
s.tag[s.top]=0;//设此根结点标志初始化为0，表示左右孩子都么有访问，当访问完左子树，tag变为1；
t=t->lchild;//进入左子树访问。（左子树根结点全部进栈）
}
while((s.top>-1)&&(s.tag[s.top]==1))
{
t=s.data[s.top];
cout<<t->data<<" ";//没有孩子的根结点，也就是它父亲的左孩子或者右孩子
s.top--;
}
if(s.top>-1)
{
t=s.data[s.top];
s.tag[s.top]=1;//进入右孩子前，标志tag变为1；
t=t->rchild;//进入右孩子
}
else
t=NULL;
}
}
int main()
{
bintree tree;
cout<<"输入根结点：" ;
createbintree(&tree);
cout<<"\n 前序递归遍历二叉树；";
preorder(tree);
cout<<"\n 前序非递归遍历二叉树：";
preorder1(tree);
cout<<"\n-------------------------------\n";
cout<<"\n 中序遍历递归二叉树；";
inorder(tree);
cout<<"\n 中序非递归遍历二叉树：";
inorder1(tree);
cout<<"\n----------------------------\n";
cout<<"\n 后序递归遍历二叉树：";
postorder(tree);
cout<<"\n 后序非递归遍历二叉树：";
postorder1(tree);
cout<<endl;
}