Question

c语言二叉树遍历后输出格式问题！（求帮忙修改代码）

题目描述

求二叉树的先序、中序及后序遍历序列。结点数<=100。

输入

按先序遍历的顺序建立一个二叉树，为了保证树的唯一性，并在程序中的递归出口是左右子树为空，故输入时，当某结点的左子树或右子树为空值时也要作为先序遍历的有效输入。例如一个树只有3个结点，根结点值为1，其左孩子结点值为2，其右孩子结点值为3，则输入的先序遍历序列依次为1　2　0　0
3　0 0（为空时输入0值）*/

结点的值为整数。

输出

在三行上，依次输出二叉树的先序、中序及后序遍历序列。序列中各数用空格隔开。
样例输入
1 2 0 0 3 0 0
样例输出

1 2 3
2 1 3
样例输出里每一行的最后一个数字不要输出空格，可是我的代码是每个数字后都会输出一个空格，求帮改代码
#include<iostream>
using namespace std;
#include <stdio.h>

typedef struct node
{
struct node *lchild;
struct node *rchild;
int data;
}BiTreeNode, *BiTree;

void createBiTree(BiTree &T)//先序遍历创建二叉树
{
int c;
scanf("%d",&c);
if(0== c)
T = NULL;
else
{
T = new BiTreeNode;
T->data = c;
createBiTree(T->lchild);
createBiTree(T->rchild);
}
}
void first(BiTree T)//先序遍历
{
if(T)
{
printf("%d",T->data);
first(T->lchild);
first(T->rchild);

}
}
void middle(BiTree T)//中序遍历
{
if(T)
{
middle(T->lchild);
printf("%d",T->data);
middle(T->rchild);

}
}
void last(BiTree T)//后序遍历
{
if(T)
{
last(T->lchild);
last(T->rchild);
printf("%d",T->data);
}
}

int main()
{
BiTree T;
createBiTree(T);
first(T);
printf("\n");
middle(T);
printf("\n");
last(T);

return 0;
}

Answer 1

在输出前先判断一下左右子树是否为空，以first为例：

void first(BiTree T)//先序遍历
{    
    if(T)    
    {        
    printf("%d",T->data);
    if(T->lchild || T->rchild)   
    printf(" ");       //后面还有，多输出一个空格

追问

这个我有试过，输出不对，请看截图

追答

那把左右子树的判断分开就可以了，如下：

void first(BiTree T)//先序遍历
{
    if(T)
    {
        printf("%d",T->data);
        if(T->lchild) 
{
printf(" ");
first(T->lchild);
}
        if(T->rchild) 
{
printf(" ");
first(T->rchild);
}
    }
}

追问

你好，那请问你这种方法用中序遍历，后序遍历要怎么写呢？ 我照您的方法写不对呢T_T，另外我在函数里加了一个计数器解决了这个问题，可是我觉得您的方法更快捷，您可以把中序和后序遍历都写写吗？

追答

void middle(BiTree T)//中序遍历
{
if(T)
{
middle(T->lchild);
if(T->lchild)
{
printf(" ");
}
printf("%d",T->data);
if(T->rchild)
{
printf(" ");
}
middle(T->rchild);

}
}
void last(BiTree T)//后序遍历
{
if(T)
{
last(T->lchild);
if(T->lchild)
{
printf(" ");
}
last(T->rchild);
if(T->rchild)
{
printf(" ");
}
printf("%d",T->data);
}
}