二叉树递归非递归遍历+文件读写
#include <stdio.h>
#include<stdlib.h>
//const int N = 100;
typedef struct BiTNode
{
char data;
struct BiTNode *lchild;
struct BiTNode *rchild;
} BiTNode, *BiTree;
void CreateBiTree(BiTree T,FILE *fp) // 建立二叉链表存储的二叉树
{
char ch;
ch=fgetc(fp);
if (ch == '#') T = NULL; // #表示当前结点为空
else
{
T = (BiTree)malloc(sizeof(BiTNode)); // 动态申请结点内存
T->data = ch; // 生成根结点
CreateBiTree (T->lchild,fp); // 构造左子树
CreateBiTree (T->rchild,fp); // 构造右子树
}
}
void PreOrderTraverse(BiTree T,FILE *fp1) // 前序遍历二叉树(递归)
{
if (T == NULL)
{
return;
}
fprintf(fp1,"%c ",T->data);
printf("%c ", T->data);
PreOrderTraverse(T->lchild,fp1);
PreOrderTraverse(T->rchild,fp1);
}
void PreOrder(BiTree T,FILE *fp1) // 前序遍历二叉树(非递归)
{
BiTree s[100];
int top = 0;
BiTree p;
p = T;
while (p != NULL || top != 0) // 若当前结点非空,或者栈不为空
{
while (p != NULL) // 依次访问左子树,并入栈
{
fprintf(fp1,"%c ",p->data);
printf("%c ", p->data);
s[++top] = p;
p = p->lchild;
}
if (top != 0) // 返回栈顶元素,及当前结点的根节点,并进入根节点的右子树
{
p = s[top--];
p = p->rchild;
}
}
}
void InOrderTraverse(BiTree T,FILE *fp1) // 中序遍历二叉树(递归)
{
if (T == NULL) return;
InOrderTraverse(T->lchild,fp1); // 先中序遍历左子树
fprintf(fp1,"%c ",T->data);
printf("%c", T->data); // 再显示结点数据
InOrderTraverse(T->rchild,fp1); // 最后中序遍历右子树
}
void InOrder(BiTree T,FILE *fp1) // 中序遍历二叉树(非递归)
{
BiTNode *s[100]; // 用结构体指针数组模拟栈
int top = 0; // 设置栈顶指针
BiTNode *p;
p = T;
while (top != 0 || p != NULL) // 若当前结点为空结点 且栈为空,则结束
{
while (p != NULL) // 若当前结点不为空,则访问根结点,根指针入栈,进入左子树
{
s[++top] = p;
p = p->lchild;
}
if (top != 0) // 若栈不为空,根指针退栈,进入其右子树
{
p = s[top--];
fprintf(fp1,"%c ",p->data);
printf("%c ", p->data); // 先访问完左结点之后,回到根结点,再访问根节点
p = p->rchild;
}
}
}
void PostOrderTraverse(BiTree T,FILE *fp1) // 后序遍历二叉树(递归)
{
if (T == NULL) return;
PostOrderTraverse(T->lchild,fp1);
PostOrderTraverse(T->rchild,fp1);
fprintf(fp1,"%c ",T->data);
printf("%c ", T->data);
}
void PostOrder(BiTree T,FILE *fp1) // 后序遍历二叉树(非递归)
{
BiTNode *s[100];
int top = 0;
BiTNode *p, *q; // q存储二次访问的结点,p存储当前根结点
p = T;
q = NULL;
while (p != NULL || top != 0)
{
while (p != NULL)
{
s[++top] = p;
p = p->lchild;
}
if (top != 0)
{
p = s[top]; // 获取栈顶元素
if (p->rchild == NULL || p->rchild == q) // 若右子树为空 或者 右子树刚刚被访问过
{
top--; // 栈顶元素出栈
fprintf(fp1,"%c ",p->data);
printf("%c", p->data);
q = p;
p = NULL;
}
else
{
p = p->rchild;
}
}
}
}
void LevelOrder(BiTree T,FILE *fp1) // 二叉树的层序遍历
{
BiTNode *Q[100]; // 数组模拟队列
int front = 0;
int rear = 0;
BiTNode *p;
Q[++rear] = T; // 根结点入队
while (front != rear) // 若队列不为空
{
// 队头结点出队,并访问出队结点
p = Q[++front];
fprintf(fp1,"%c ",p->data);
printf("%c ", p->data);
// 出队结点的非空左右孩子依次入队
if (p->lchild != NULL)
{
Q[++rear] = p->lchild;
}
if (p->rchild != NULL)
{
Q[++rear] = p->rchild;
}
}
}
int Depth(BiTree T) //深度
{
int hl,hr,h;
if(T==NULL)
return 0;
else
{
hl=Depth(T->lchild);
hr=Depth(T->rchild);
if(hl>hr)
h=hl+1;
else
h=hr+1;
return h;
}
}
int main()
{
FILE *fp;
fp=fopen("data.txt","r");
BiTree T;
CreateBiTree(T,fp);
FILE *fp1;
fp1=fopen("results.txt","w");
///前序递归
fprintf(fp1,"前序递归遍历:");
printf("前序递归遍历:");
PreOrderTraverse(T,fp1);
fprintf(fp1,"\n");
printf("\n");
///前序非递归
fprintf(fp1,"前序非递归遍历:");
printf("前序非递归遍历:");
PreOrder(T,fp1);
fprintf(fp1,"\n");
printf("\n");
///中序递归
fprintf(fp1,"中序递归遍历:");
printf("中序递归遍历:");
InOrderTraverse(T,fp1);
fprintf(fp1,"\n");
printf("\n");
///中序非递归
fprintf(fp1,"中序非递归遍历:");
printf("中序非递归遍历:");
InOrder(T,fp1);
fprintf(fp1,"\n");
printf("\n");
///后序递归
fprintf(fp1,"后序递归遍历:");
printf("后序递归遍历:");
PostOrderTraverse(T,fp1);
fprintf(fp1,"\n");
printf("\n");
///后序非递归
fprintf(fp1,"后序非递归遍历:");
printf("后序非递归遍历:");
PostOrder(T,fp1);
fprintf(fp1,"\n");
printf("\n");
///层次遍历
fprintf(fp1,"层次遍历:");
printf("层次遍历:");
LevelOrder(T,fp1);
fprintf(fp1,"\n");
printf("\n");
///深度
int h=0;
fprintf(fp1,"二叉树的高度是:");
printf("二叉树的高度是:");
h=Depth(T);
fprintf(fp1,"%d",h);
printf("%d",h);
fprintf(fp1,"\n");
printf("\n");
return 0;
}
data.txt的内容:
运行结果及报错内容 :
运行结果错误,每一种遍历(每一个函数)都无法显示正确结果。
可以帮忙看一下哪里出错了吗?