[C语言][树][层次遍历]List Leaves

60 阅读 0 评论 40 点赞

我是靠谱客的博主传统小伙，最近开发中收集的这篇文章主要介绍[C语言][树][层次遍历]List Leaves，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.题目

Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree – and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a “-” will be put at the position. Any pair of children are separated by a space.

Output Specification:
For each test case, print in one line all the leaves’ indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.
Sample Input:
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6
Sample Output:
4 1 5

2.代码

#include<stdio.h>
#include<stdlib.h>
#define Maxsize 10
#define Null -1
typedef struct Tree *List;
typedef struct Queue *Q;
struct Tree
{
     int data;
     int left;
     int right;
}t[Maxsize];

struct Queue
{
    int Data[Maxsize+1];
    int rear;
    int top;
};
Q CreatQ()
{
    Q q;
    q=(Q)malloc(sizeof(struct Queue));
    q->rear=0;
    q->top=0;
    return q;
}
int CreatTree(struct Tree t[])
{
    int n,i;
    int check[Maxsize];
    int root=Null;
    scanf("%d",&n);
   getchar();
    for(i=0;i<n;i++)
        check[i]=0;
    char cl,cr;
    for(i=0;i<n;i++)
    {
        scanf("%c %c",&cl,&cr);
        getchar();
        t[i].data=i;
        if(cl!='-'){
            t[i].left=cl-'0';
            check[t[i].left]=1;
        }
        else
            t[i].left=Null;
        if(cr!='-'){
            t[i].right=cr-'0';
            check[t[i].right]=1;
        }
        else
            t[i].right=Null;
    }
    for(i=0;i<n;i++)
    {
        if(check[i]!=1)
            break;
    }
    root=i;
    return root;
}

void Addq(Q q,int x)
{
        q->Data[++(q->rear)]=x;
        //printf("x:%dn",q->Data[q->rear]);
}

int deleteq(Q q)
{
        //printf("x:%dn",q->Data[++(q->top)]);
        return q->Data[++(q->top)];
}

int IsEmptyq(Q q)
{
    if(q->top==q->rear)
        return 1;
    else
        return 0;
}
void printleave(int root)
{

    Q q;
    q=CreatQ();
    Addq(q,root);
    int flag=0;//输出标记
    while(!IsEmptyq(q))
    {
        int p;
        p=deleteq(q);//弹出一个元素

        if(t[p].left==Null&&t[p].right==Null&&flag==0)
        {
                printf("%d",t[p].data);
                flag=1;
        }
        else if(t[p].left==Null&&t[p].right==Null&&flag==1)
        {
            printf(" %d",t[p].data);
        }
        if(t[p].left!=Null) Addq(q,t[p].left);
        if(t[p].right!=Null) Addq(q,t[p].right);
    }
}

int main()
{
    int r;
    r=CreatTree(t);
    printleave(r);
    printf("n");
    return 0;
}

3.分析

1.首先是审题。in the order of top down, and left to right.审题能力太差，直接认为是先序、中序、后序依次遍历。而不是理解我从上到下，从左到右的层次遍历。
2.段错误：creatq()的时候没有return，导致段错误。
3.队列边界判断：当取到最大N的时候，由于队列下标为0的位置没有存储值，导致真实长度只有N-1,所以会发生错误，因此将队列大小设为Maxsize+1。
4.链表的理解：无论是静态链表还是动态链表，都需要申请内存空间，不要将静态链表当作数组。
5.使用队列进行层次遍历。