中序遍历二叉树

中序遍历二叉树

时间: 1ms        内存:128M

描述:

给定一颗二叉树,要求输出二叉树的深度以及中序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。

输入:

输入数据分为多组,第一行是测试数据的组数n,下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数,数据为0代表当前结点为空,数据为-1代表二叉树数据输入结束,-1不作处理。二叉树的构造按照层次顺序(即第1层1个整数,第2层2个,第3层4个,第4层有8个......,如果某个结点不存在以0代替)

输出:

输出每棵二叉树的深度以及中序遍历二叉树得到的序列。

示例输入:

2
1 -1
1 2 0 3 4 -1

示例输出:

1 1
3 3 2 4 1

提示:

参考答案(内存最优[752]):

#include<stdio.h>
#include<stdlib.h>

#define maxsize 20

typedef struct node
{
	int ltag,rtag;
	int data;
	struct node *lch,*rch;
}btnode;

btnode *Q[maxsize];

int flag;

btnode *creat()
{
    int c;
	int front,rear;
	btnode *T,*S;
	T=NULL;
	front=1;rear=0;
	scanf("%d",&c);
	while(c!=-1)
	{
		S=NULL;
		if(c!=0)
		{
			S=(btnode *)malloc(sizeof(btnode));
			S->data=c;
			S->lch=NULL;
			S->rch=NULL;
			S->rtag=0;
			S->ltag=0;
		}
		rear++;
		Q[rear]=S;
		if(rear==1) T=S;
		else
		{
			if(S!=NULL && Q[front]!=NULL)
				if(rear%2==0) Q[front]->lch=S;
				else Q[front]->rch=S;
				if(rear%2==1) front++;
		}
		scanf("%d",&c);
	}
	return T;
}

void pre(btnode *T)
{
	if(T)
	{
		if(T->ltag!=1) pre(T->lch);
        if(flag)
		{
             printf(" ");
		}
		flag=1; printf("%d",T->data);
		if(T->rtag!=1) pre(T->rch);
	}
}
int depth(btnode *bt)
{
    int m,n;
    if(bt==NULL)
        return 0;
    m=depth(bt->lch);
    n=depth(bt->rch);
    if(m>n)
        return m+1;
    else
        return n+1;
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        flag=0;
        btnode *bt;
        bt=creat();
        printf("%d ",depth(bt));
        pre(bt);
        printf("\n");
    }
    return 0;
}

参考答案(时间最优[0]):

#include<stdio.h>
#include<stdlib.h>

#define maxsize 20

typedef struct node
{
	int ltag,rtag;
	int data;
	struct node *lch,*rch;
}btnode;

btnode *Q[maxsize];

int flag;

btnode *creat()
{
    int c;
	int front,rear;
	btnode *T,*S;
	T=NULL;
	front=1;rear=0;
	scanf("%d",&c);
	while(c!=-1)
	{
		S=NULL;
		if(c!=0)
		{
			S=(btnode *)malloc(sizeof(btnode));
			S->data=c;
			S->lch=NULL;
			S->rch=NULL;
			S->rtag=0;
			S->ltag=0;
		}
		rear++;
		Q[rear]=S;
		if(rear==1) T=S;
		else
		{
			if(S!=NULL && Q[front]!=NULL)
				if(rear%2==0) Q[front]->lch=S;
				else Q[front]->rch=S;
				if(rear%2==1) front++;
		}
		scanf("%d",&c);
	}
	return T;
}

void pre(btnode *T)
{
	if(T)
	{
		if(T->ltag!=1) pre(T->lch);
        if(flag)
		{
             printf(" ");
		}
		flag=1; printf("%d",T->data);
		if(T->rtag!=1) pre(T->rch);
	}
}
int depth(btnode *bt)
{
    int m,n;
    if(bt==NULL)
        return 0;
    m=depth(bt->lch);
    n=depth(bt->rch);
    if(m>n)
        return m+1;
    else
        return n+1;
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        flag=0;
        btnode *bt;
        bt=creat();
        printf("%d ",depth(bt));
        pre(bt);
        printf("\n");
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注