Question

c语言 关于二叉树的创建和遍历(中序遍历)

以下是我写的创建二叉树的程序，有错，但不知怎么改正，请高手帮忙！
typedef struct BiTNode
{
char date;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//创建二叉树
BiTree creatBiTree(BiTree T)
{
char ch;
scanf("%c",&ch);
if(ch==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->date=ch;
creatBiTree(T->lchild);
creatBiTree(T->rchild);
}
return T;
}

Answer 1

#include <stdio.h>
#include <stdlib.h> //需要包含这个头文件，后面exit()用到
#include <malloc.h>
#define OVERFLOW 1
#define NULL 0
#define OK 1

typedef struct BiTNode
{ char data;
struct BiTNode * lchild, * rchild;
} BiTNode, * BiTree;

int flag=0;//增加这个变量，用于标记当前是否是根结点
BiTNode *head;//增加这个变量，用于记录根结点

CreateBiTree ( BiTree T )
{ char ch;
fflush(stdin);//建议加上这个键盘缓冲区清空处理，防止读入了上次输入的回车
scanf ("%c",&ch);
if (ch=='*') T=NULL;
else {
T=( BiTNode * ) malloc( sizeof( BiTNode ) ) ;
if(T==NULL) exit(OVERFLOW); //不是判断if (T) ，而是判断if(T==NULL)
if(flag==0)//如果当前是第一个结点(根结点)
{
head=T;//将head指向根结点
flag=1;//flag置为1
}
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);}
return OK;
}

PreOrderTraverse(BiTree T)
{if(T)
{printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);}
}

main()
{
BiTree t;
CreateBiTree(t);
PreOrderTraverse(head);//由于在CreateBiTree执行后，t指向的位置已经变为了叶结点了，所以这里传入的应该是根结点head的地址
}

Answer 2

以下是我修改的，请参考：
#include "stdio.h"
#include "malloc.h"
typedef struct BiTNode
{
char date;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//创建二叉树
void creatBiTree(BiTree T)
{
char ch;
scanf("%c",&ch);
if(ch == ' ')
T = NULL;
else
{
T = (BiTNode *)malloc(sizeof(BiTNode));
T->date=ch;
creatBiTree(T->lchild);
creatBiTree(T->rchild);
}
}

void InOrder(BiTree T)
{
if (T)
{
InOrder(T->lchild);
printf("%c",T->date);
InOrder(T->rchild);
}
}

void main()
{
BiTree T;
creatBiTree(T);
InOrder(T);

}

Answer 3

你写的改一下
BiTree creatBiTree(/*BiTree T*/)
{
BiTree T = NULL;
char ch;
scanf(" %c",&ch); //%c前面加空格缓冲掉回车
if(ch==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->date=ch;
T->lchild=creatBiTree(/*T->lchild*/);
T->rchild=creatBiTree(/*T->rchild*/);
}
return T;
}
如果T做函数参数就要用二级指针