数据结构二叉树的遍历

Question

求！数据结构二叉树遍历

代码如下：

```c++
#include <stdio.h>
#include <stdlib.h>
typedef char  Elemtype;
typedef struct BiTNode  //树结点
{
    Elemtype data;
    struct BiTNode *lchild,*rchild; //指向左右子树的指针
} *BiTree;
BiTree CreateLink() //二叉树的递归创建
{
    char data;
    BiTree T;
    scanf("%c",&data);//读入当前结点


    if(data=='0')
    {
        return NULL;
    }
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));
        T->data=data;
        printf("请输入%c的左子树: ",data);
        T->lchild=CreateLink();
        printf("请输入%c的右子树: ",data);
        T->rchild=CreateLink();
        return T;
    }
}
void visit(BiTree T)
{
    printf("%c  ",T->data);
}

//先序遍历%d
void PreOrder(BiTree T)
{

if(T==NULL)      // 递归中遇到NULL，返回上一层节点
 {
  return;
 }
 printf("%c ",T->data);
 PreOrder(T->lchild);   // 递归遍历左子树
 PreOrder(T->rchild);   // 递归遍历右子树
}

//中序遍历
void InOrder(BiTree T)
{

if(T==NULL)      // 递归中遇到NULL，返回上一层节点
 {
  return;
 }

 InOrder(T->lchild);   // 递归遍历左子树
 printf("%c ",T->data);
 InOrder(T->rchild);   // 递归遍历右子树
}

void PostOrder(BiTree T)
{


if(T==NULL)      // 递归中遇到NULL，返回上一层节点
 {
  return;
 }

 PostOrder(T->lchild);   // 递归遍历左子树
 PostOrder(T->rchild);   // 递归遍历右子树
 printf("%c ",T->data);
}


int main()
{
    BiTree T;
    printf("请输入根节点数据: ");
    T=CreateLink();
    printf("先序遍历： ");
    PreOrder(T);
    printf("\n");
    printf("中序遍历： ");
    InOrder(T);
    printf("\n");
    printf("后序遍历： ");
    PostOrder(T);
    printf("\n");
    return 0;
}

用此代码运算出来，如图所示，重复出现：“请输入 的左子树”

将此代码转化为int类型时，全部使用数字而非字母，就可以正常运行，不会出现错误

#include <stdio.h>
#include <stdlib.h>
typedef int  Elemtype;
typedef struct BiTNode  //树结点
{
    Elemtype data;
    struct BiTNode *lchild,*rchild; //指向左右子树的指针
} *BiTree;
BiTree CreateLink() //二叉树的递归创建
{
    int data;
    BiTree T;
    scanf("%d",&data);//读入当前结点
    if(data==-1)
    {
        return NULL;
    }
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));
        T->data=data;
        printf("请输入%d的左子树: ",data);
        T->lchild=CreateLink();
        printf("请输入%d的右子树: ",data);
        T->rchild=CreateLink();
        return T;
    }
}
void visit(BiTree T)
{
    printf("%d  ",T->data);
}
//先序遍历
void PreOrder(BiTree T)
{
if(T==NULL)      // 递归中遇到NULL，返回上一层节点
 {
  return;
 }
 printf("%d ",T->data);
 PreOrder(T->lchild);   // 递归遍历左子树
 PreOrder(T->rchild);   // 递归遍历右子树
}
//中序遍历
void InOrder(BiTree T)
{
if(T==NULL)      // 递归中遇到NULL，返回上一层节点
 {
  return;
 }
 InOrder(T->lchild);   // 递归遍历左子树
 printf("%d ",T->data);
 InOrder(T->rchild);   // 递归遍历右子树
}
void PostOrder(BiTree T)
{
if(T==NULL)      // 递归中遇到NULL，返回上一层节点
 {
  return;
 }

 PostOrder(T->lchild);   // 递归遍历左子树
 PostOrder(T->rchild);   // 递归遍历右子树
 printf("%d ",T->data);
}
int main()
{
    BiTree T;
    printf("请输入根节点数据: ");
    T=CreateLink();
    printf("先序遍历： ");
    PreOrder(T);
    printf("\n");
    printf("中序遍历： ");
    InOrder(T);
    printf("\n");
    printf("后序遍历： ");
    PostOrder(T);
    printf("\n");
    return 0;
}

想要将字符类型的代码改善改善，将其运行出来向int类型时，没有错误，不会重复出现“请输入 的左子树”

Answer 1

从控制台输入0的时候，你按了一个回车，递归调用 CreateLink() 的时候，

scanf("%c",&data);

自动把回车作为数据读入，所以你不停的输入0， 回车，一直这样下来，不会结束。

如果是整数类型，就不会把回车作为字符读入。

谢谢！

创建二叉树可以用前序，中序来创建一棵二叉树，欢迎你参考我最近的文章，

用递归重写已有的程序（四）： 前序遍历和中序遍历建立一棵二叉树_elliptical的博客-CSDN博客 用递归程序创建一棵二叉树：利用给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一确定一棵二叉树的结构。 https://blog.csdn.net/elliptical/article/details/127325357?spm=1001.2014.3001.5502