假设二叉树采用连接方式存储，编写一个对二叉树进行前序遍历的递归和非递归程序

Question

如题所述

Answer 1

下面是我以前写的程序对你是否有帮助
#include "iostream.h"
#include "string.h"
#include "malloc.h"
#include "stdio.h"

typedef struct btree
{
int data;//树结点的值域
int ltag,rtag;//树结点的左右线索
struct btree *left,*right;//树结点的左右指针，ltag，rtag=1时指向前驱和后继，否则指向左右孩子

}node;

node *SearchNode(node *q,node *r)
{//在根结点地址为q的中序线索二叉树中查找结点r将要插入的结点
node *p;
p=q;
while(1)
{
while(r->data<p->data&&p->ltag!=1){p=p->left;}//一直向左寻找
while(r->data>p->data&&p->rtag!=1){p=p->right;}//一直向右寻找
if(r->data<p->data&&p->ltag==1||r->data>p->data&&p->rtag==1||r->data==p->data)break;
//当r->data<p->data并且p没有左孩子或r->data>p->data并且p没有由孩子
//或r->data==p->data时，结点p找到，跳出循环
}
return(p);//返回p结点

}
node *InsertNode(node *rot,node *s)
{//在根结点地址为rot的中序线索二叉树中插入结点s

node *p;

if(rot==NULL)
{//如果根结点为空，s结点作为根结点插入。
rot=s;
rot->data=s->data;
rot->ltag=1;
rot->left=NULL;
rot->rtag=1;
rot->right=NULL;
return(rot);
}

p=SearchNode(rot,s);//调用SearchNode函数查找s将要插入的结点p的位置
if(s->data==p->data)
{//如果结点在树中已经存在，释放该结点并返回
free(s);
return(rot);
}

if(s->data<p->data)
{//如果s->data<p->data，则做为p的左孩子插入，此时s的前驱是插入前p的前驱，s的后继是p
s->ltag=1;
s->left=p->left;
s->rtag=1;
s->right=p;
p->ltag=0;
p->left=s;
}
if(s->data>p->data)
{//如果s->data>p->data，则做为p的右孩子插入，此时s的后继是插入前p的后继，s的前驱是p
s->rtag=1;
s->right=p->right;
s->ltag=1;
s->left=p;
p->rtag=0;
p->right=s;
}
return(rot);
}
node *CreatTree(node *rt)
{//以根结点为空开始构造中序线索二叉排序树，并返回根结点的地址

int m;//用于输入根结点的值域
node *q;

while(1)
{
printf("Please input number:\nm=");
//scanf("%d",&m);
cin>>m;//输入结点的值
if(m==-1) return(rt);
node *s;//建一个有待插入的新结点
s=(node *)malloc(sizeof(node));//给s开辟一个结点空间
s->data=m;
q=InsertNode(rt,s);//调用InsertNode函数一个个结点插入已生成的中序线索二叉树中，形成新的树
rt=q;

}
return(rt);

}

node *Search(node *root,int x)
{//在根结点地址为root的中序线索二叉树中查找结点值为x的结点p并返回p，若结点不存在则返回NULL。
node *p;//返回值为x的结点的位置
p=root;
while(1)
{
while(x<p->data&&p->ltag!=1){p=p->left;}
while(x>p->data&&p->rtag!=1){p=p->right;}
if(x<p->data&&p->ltag==1||x>p->data&&p->rtag==1||x==p->data)break;

}
if(x!=p->data) p=NULL;
return(p);

}

node *P_Next(node *root,int x)
{//查找根结点地址为root的中序线索二叉树中结点值为x的结点p按后序遍历的后继结点q
node *p,*q;//p是结点值为x的结点，q用来返回p按后序遍历的后继结点
p=Search(root,x);//调用Search函数查找结点p的位置
if(p==NULL)//值为x结点不存在，出错
{
return NULL;
}
if(p->ltag==0) return(p->left);//如果此结点有左孩子，返回左孩子结点
else
{
if(p->rtag==0) return(p->right);//如果此结点无左孩子有右孩子，返回右孩子结点
else//如果此结点为叶子结点
{
q=p->right;//寻找此结点的后继结点
if(q==NULL)//后继为空，此结点是按前序遍历的最后一个结点，返回空
{
printf("this node is last node\n");
return NULL;
}
else
{
while(q->rtag==1&&q->right!=NULL) {q=q->right;}//如果结点的后继没有右孩子，一直向后继方向寻找结点
if(q->right==NULL)
{
return NULL;
}
else return(q->right);//返回结点的右孩子结点
}

}
}
}

void display(node *t)
{//非递归中序遍历中序线索二叉排序树
printf("中序序列为：");

while(t->ltag!=1){t=t->left;}//寻找最左结点，即中序遍历的第一个结点
while(t!=NULL)
{
printf("%d ",t->data);//打印结点值
while(t->rtag==1)//结点右指针指向后继结点
{
t=t->right;
if(t==NULL)return;//t空，遍历结束
else printf("%d ",t->data);//打印结点值
}
if(t->rtag==0)//如果结点有右孩子
{
t=t->right;//从右孩子结点开始
while(t->ltag!=1){t=t->left;}//继续向左寻找此子树的最左结点
}

}

}

void main()
{
int w;

printf("输入一串正整数建立一棵中序线索二叉排序树最后以-1作为结束标志\n");
node *root;
root=NULL;
node *p;
node *q;

p=CreatTree(root);
display(p);
while(1)
{
cout<<"\n查找按前序遍历x的后继结点\nx=";
cin>>w;

q=P_Next(p,w);
if(q==NULL) cout<<"此结点不在树中或是按前序遍历的最后一个结点\n";
else
{
cout<<"\n此结点的后继结点为：";
cout<<q->data;
}
}

}

Answer 2

前序遍历?Pascal?

建立个过程叫print接受传送来的指针参数 这个你要自己定义的

然后在过程里加上这些就O

WriteLn(Tree.data);
Print(Tree.L);
Print(Tree.R);

Over 递归的

Answer 3

<算法与数据结构>书上有，现成的例子啊