二叉树的一些问题

答案正确啊，如下图

/*经改正后能正常运行，无限输入主要是由于scanf引起的 

详细请看http://baike.baidu.com/view/1390039.html?tp=0_11 

注意构建树的输入顺序 

比如要构建 

``````1 

`````/`\ 

`````2``5 

```/\ 

``3``4 

这棵树，则输入应为1-2-3-!-!-4-!-!-5-!-! */ 

#include "stdio.h" 

#include "malloc.h" 

#define MAXSIZE 100 

typedef char ElemType; 

typedef struct BiTNode 

{ 

ElemType data; 

struct BiTNode *lchild, *rchild; 

} BiTNode; 

BiTNode *root; 

BiTNode* CreateBitTree() 

{ 

ElemType ch; 

BiTNode *T; 

printf("请输入节点字符,!为空树："); 

scanf("%c",&ch); 

fflush(stdin);//清除一个输入流 

if (ch=='!') 

{ 

T=NULL; 

} 

else 

{ 

T=(BiTNode *)malloc(sizeof(BiTNode)); 

T->data=ch; 

T->lchild=CreateBitTree(); 

T->rchild=CreateBitTree(); 

} 

return T; 

} 

void inorder(BiTNode *head) 

{ 

BiTNode *t=NULL; 

t=head; 

if(t) 

{ 

inorder(t->lchild); 

printf("%c\t",t->data); 

inorder(t->rchild); //这里写错了，原来是inorder(t->lchild); 

} 

} 

void main() 

{ 

BiTNode *b; 

b=CreateBitTree(); 

inorder(b); 

}

#include "stdio.h"

#include "malloc.h"

#define MAXSIZE 100

typedef char ElemType;

typedef struct BiTNode

{

 ElemType data;

 struct BiTNode *lchild, *rchild;

} BiTNode;

BiTNode *root;

BiTNode* CreateBitTree()

{

 ElemType ch;

 BiTNode *T;

 printf("请输入节点字符,!为空树：");

 scanf("%c",&ch);

 // 吃掉ENTER

 getchar();

 if (ch=='!')

 {

  T=NULL;

 }

 else

 {

  T=(BiTNode *)malloc(sizeof(BiTNode));

  T->data=ch;

  T->lchild=CreateBitTree();

  T->rchild=CreateBitTree();

 }

 return T;

}

void inorder(BiTNode *head)

{

 BiTNode *t=head;

 if(t)

 {

  inorder(t->lchild);

  printf("%c\t",t->data);

  //接下来遍历的是右子树

  inorder(t->rchild);

 }

}

// 需要释放动态分配的节点，否则会造成内存泄露

void clear(BiTNode *head)

{

 if (head)

 {

  clear(head->lchild);

  clear(head->rchild);

  free(head);

 }

}

main()

{

 BiTNode *b;

 b=CreateBitTree();

 inorder(b);

 putchar('\n');

 clear(b);

}

#include "stdio.h"
#include "malloc.h"
#define MAXSIZE 100
typedef char ElemType;

typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode;

BiTNode *root;

BiTNode* CreateBitTree()
{
ElemType ch;
BiTNode *T;

printf("请输入节点字符,!为空树：");
scanf("%c",&ch);

if (ch=='!')
{
T=NULL;
}
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=ch;
T->lchild=CreateBitTree();
T->rchild=CreateBitTree();
}
return T;
}

void inorder(BiTNode *head)
{
BiTNode *t=NULL;
t=head;
if(t)
{
inorder(t->lchild);
printf("%c\t",t->data);
inorder(t->rchild); //这里有问题！！
}
}

main()
{
BiTNode *b;
b=CreateBitTree();
inorder(b);
}

程序不停地让你输入是因为你的“空树”标记是'!'，而一直没有遇到'!'所致；
但为什么会一直没有遇到'!'，那是因为它把你输入时敲进的回车符'\n'也当作一个树的data保存起来了，所以要让程序正确，必须每次在scanf的时候也把你敲的回车符也读掉：

#include "stdio.h"
#include "malloc.h"
#define MAXSIZE 100
typedef char ElemType;

typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode;

BiTNode *root;

BiTNode* CreateBitTree()
{
ElemType ch;
char enter;// 这个变量来装回车符
BiTNode *T;

printf("请输入节点字符,!为空树：");
scanf("%c%c",&ch,&enter);// 把回车符装了

if (ch=='!')
{
T=NULL;
}
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=ch;
T->lchild=CreateBitTree();
T->rchild=CreateBitTree();
}
return T;
}

void inorder(BiTNode *head)
{
BiTNode *t=NULL;
t=head;
if(t)
{
inorder(t->lchild);
printf("%c\t",t->data);
inorder(t->lchild);
}
}

main()
{
BiTNode *b;
b=CreateBitTree();
inorder(b);
}

运行试试吧，因该OK了。

呵呵，
要记住输入的时候不能完全按先序序列来，单纯由先序序列是不能确定一棵二叉树的，比如对于一棵根为A，左子树为B，右子树为C的二叉树，你得输入AB!!C!!