二叉树的递归遍历

来源:百度知道 编辑:UC知道 时间:2024/09/20 19:38:23
#include <stdio.h>
#include <iostream.h>
#include <malloc.h>
#include <stdlib.h>

#define NULL 0

typedef char DataType;

typedef struct node //定义二叉树
{
DataType data;
struct node *lchild,*rchild;
}TBinTree;

TBinTree* CreatBinTree(TBinTree *T) //构造二叉树
{
DataType ch;

ch=getchar();

if(ch=='#')
T=NULL;
else
{
T=(TBinTree *)malloc(sizeof(TBinTree));

T->data=ch;
T->lchild=CreatBinTree(T->lchild);
T->rchild=CreatBinTree(T->rchild);
}
return T;
}

void PreOrderTraverse(TBinTree *T) // 先序遍历
{
if(T)
{
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}

}

void InOrderTraverse(TBinTree *T

问题在你没有清除getchar()时输入的回车符上。
ch=getchar()时,假定你输入了'A'. 实际你键入了一个'A',一个回车. 而getchar()却只取出了'A',没有取出回车, 下次再执行到getchar()时,如果你输入了'#', 实际上键盘缓冲区里有三个字符,一个是上次没有取出的回车符,还有'#'和新的回车符. 由于回车符的积累和递归的原因, 这个程序就永远无法从创建二叉树的函数中退出来了.

解决方法也很简单: 在ch=getchar();之后再加一行getchar()把回车符取出来:
ch=getchar();
getchar();

或者在ch=getchar();之后再加一行fflush(stdin)清除键盘缓冲区:
ch=getchar();
fflush(stdin);

另外, 中序和后序遍历的函数第二个lchild应该是rchild. 可能是复制的, 忘修改了吧.