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

编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历的各种递归和非递归算法，以及层次遍历的算法~

文件 main.cpp 代码如下：

#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 数学函数头文件，包括floor()，ceil()，abs()等


#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样

typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}

void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
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是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历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()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0
");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：
");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("
中序递归遍历二叉树：
");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("
后序递归遍历二叉树：
");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
这样可以么？

if(p!=NULL)
{
Push(S,p->data);
p=p->lchild;
}
else//此时的p==NULL
{
Pop(S,e);//这句与p毫无关系
printf("%c",p->data);//那么这里怎么能访问p->data？
p=p->rchild;;//以及这里的p->rchild？
}

下面是我以前写的程序对你是否有帮助
#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;
}
}

}

前序遍历?Pascal?

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

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

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

Over 递归的

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

---

昌平区18581929305： 假设二叉树采用链接方式存储,编写一个对二叉树进行中序遍历的递归和非递归程序 - ？
愈贾阿法： 这是我做的. 中序遍历: var root,i,t,tl,tr,n:byte;depth,l,r:array[1..100]of byte; procedure b(p:byte); beginif p=0 then exit;b(l[p]);writeln(p,' ');b(r[p]); end; beginreadln(n);for i:=1 to n do beginreadln(t,l[t],r[t]);if l[t]>0 then inc(depth[l[t]]);if r[t]>0 ...

昌平区18581929305： 编程:假设二叉树采用链接方式存储,编写一个非递归程序对二叉树进行前序遍历 - ？
愈贾阿法： //---------------------------------------------------------------------------#include #include #include #include typedef struct node{ int data; struct node *left; struct node *right; } node,*tree; typedef struct stknode{ tree nd; struct stknode *next; }stknode; typedef struct { ...

昌平区18581929305： 假设二叉树采用连接方式存储,编写一个对二叉树进行前序遍历的递归和非递归程序？
愈贾阿法： 前序遍历?Pascal? 建立个过程叫print接受传送来的指针参数 这个你要自己定义的 然后在过程里加上这些就O WriteLn(Tree.data); Print(Tree.L); Print(Tree.R); Over 递归的

昌平区18581929305： 假设二叉树采用链接方式存储....拜托啊!!! - ？
愈贾阿法： 二叉树采用链接方式存储,在二叉树中删除所有以结点

昌平区18581929305： 假设二叉树采用链接存储结构存储,设计一个算法由二叉树B复制产生二叉树1 - ？
愈贾阿法： level起始赋值为1boolgetIndexLevel(TreeNode*root,TreeNode*found,int&level){if(root==NULL||found==NULL)returnfalse;if(root==found)returntrue;intnextlevel=level+1;if(getIndexLevel(root->left,found,

昌平区18581929305： 二叉树采用链接存储结构,设计一个算法计算一棵给定二叉树的＂左孩子＂的结点数.(重点是左孩子结点数) - ？
愈贾阿法： int count = 0; void countsinglechild(btree *t) { if(t) { if((t->left == null && t->right != null)||(t->left != null && t->right == null)) count++; countsinglechild(t->left); countsinglechild(t->right); } }

昌平区18581929305： 数据结构与算法 - ？
愈贾阿法： 二叉树求高度, 运行后, 输入:ABC__DE_G__F___ (_为空格) #include#include#define OK 1 #define NULL 0 typedef int Status; typedef char TElemType; typedef struct BiTNode //二叉树的二叉链表存储表示 { TElemType data; struct ...

昌平区18581929305： 假设二叉树采用链式方法存储,编写一个计算一棵二叉树t的高度的函数？
愈贾阿法： #include ＂stdio.h＂ #include ＂stdlib.h＂ int BiTreeDepth(BiTree T) { int h1,h2,h; if (T==NULL) return 0; else { h1=BiTreeDepth(T-&gt;lchild); h2=BiTreeDepth(T-&gt;rchild); if (h1&gt;h2) h=h1+1; else h=h2+1; } return h; }

昌平区18581929305： 假设二叉树采用链式存储结构,编写一个算法释放该二叉树所占用的全部存储空间. - ？
愈贾阿法： 后序遍历二叉树的变种.一般的后序遍历是将节点信息输出,只需要将输出语句改为存储空间释放语句就行了

昌平区18581929305： 假设二叉树用二叉链表存储结构.编写一个算法统计二叉树的结点个数. - ？
愈贾阿法： int BiTreeCount(BiTree T) { int rNum,lNum; if(!T) return 0; else { lNum = BiTreeCount(T->lchild); rNum = BiTreeCount(T->rchild); return rNum + lNum + 1; }}