List Leaves-----输出叶子节点

小咪咪 2023-06-01 06:17 130阅读 0赞

7-1 List Leaves （30 point(s))

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 (≤) 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. ###

`8 1 - - - 0 - 2 7 - - - - 5 - 4 6 4 1 5（最后没空格）`

`有必要先解释下题目的意思，输入n个结点，然后按顺序（0-n）输入每个结点的左右孩子，第二行是0的左右孩子，第三行是1的左右孩子，依次类推，-则为空。`

首先先考虑大概的框架，确定主函数

方法：创建一棵树，接收输入的数据并转化为树结构，按层（这就得先找到第一层吧即根节点）遍历树输出叶子结点

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

int main()
    {
        int root;
        root=createtree();  //创建即读入数据并转换为树结构接收根的下标 
        display(root);  //按层遍历并输出叶子结点 
        return 0;
    }

main

定义一棵树的每个结点，创建一棵树

方法：每个结点包含了他们的左右孩子和父结点，这里会涉及到用什么类型，的把（为了下面找整棵树的根结点提供便利），用一个每个元素为结点类型的数组来当作一棵树，这里定义为全局变量也有它的好处

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

struct node
    {  //定义树结点 
        int f,lchild,rchild;  //定义左右孩子及父 
        //char ---
    }t[15]; //定义树结构体

tree node

细化接收数据+找根节点的函数createtree（）

方法：输出n个结点，为了能够找到父结点我们先把所有的结点的父结点赋值为-1，用for循环输入n个结点的信息，输入两个字符，逐一判断ch1如果不是-就成为t【i】的左孩子，并把ch1的父结点修改为i，否则的话就把i的左孩子赋值为-1（我们定义输入的是字符型的话如果结点内的元素用整型的话的话要注意把字符型的输入转换为整型数字），第二个字符ch2的判断也一样。接着用for循环通过判断每个结点的父结点是否为-1来判断根结点，如果为-1就跳出整个循环，只有根结点是没爸的，然后返回根结点的下标（数值），先输出检验一下。这里我因为粗心出了很多问题例如输入两个字符放在了循环外，如果某结点的父为-1就return i，没有用括号，这样为什么不行呢……

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

int createtree()
    {  //输入数据转换为树结构并返回跟结点的下标 
        int n,root;
        cin>>n;  //输入结点个数 
        char ch1,ch2;
        //cin>>ch1>>ch2;
        for(int i=0;i<n;i++)
            t[i].f=-1;  //初始所有的根结点为-1 
        for(int i=0;i<n;i++)
        {  //按下标顺序（根结点的数据）输入数据并形成树 
            cin>>ch1>>ch2;
            if(ch1!='-')
            {  //如果当前的左孩子字符不为- 
                t[i].lchild=ch1-'0'; //输入为字符型应转化为整形 
                t[ch1-'0'].f=i;  //改变父（下标）的值 
            }
            else
            t[i].lchild=-1;  //如果左孩子为-就给值为-1 
            if(ch2!='-')
            {
                t[i].rchild=ch2-'0';
                t[ch2-'0'].f=i;
            }
            else
            t[i].rchild=-1;
        }    
        for(int i=0;i<n;i++)
            {  //找到整棵树的根结点，只有根结点是没有父的 
                if(t[i].f==-1)  
                {
                    root=i;
                    break;
                } 
                //if---
                //return i;
            }
            //cout<<root;
            return root;    
     }

createtree

细化转化数据+输出叶子结点的函数display（）

方法：先前我们是按照结点的数据（0-n）输入存入数组，现在按（树结构）层次遍历输出（有先后），我们就需要把输入的数据重新变成一棵二叉树（从根到最后），再按从上到下从左到右的遍历顺序输出叶子结点，那我们要用什么方式去转换呢，队列的特点就是先进先出，如果我们要把按顺序的数组转换为从根开始的二叉树（可以通过每个结点的左右孩子把原来的数组重新存入一个队列）先进队的叶子就先出队。按照（定义一个数组作为队）队列设置头尾指针，利用找到的根结点（入队作为第一个元素，队尾指针后移为最后元素的下一位）开始找他的左右孩子，如果左右孩子相等就输出（叶子=队头元素），若不相等但又存在（不等于-1）就左，右孩子就依次（队尾）入队，再找左孩子的左右孩子判断相等……以此类推，那我们就可以用一个循环来实现，条件（head小于rear）就是我们在循环体内改变的变量头尾指针（入队出队都会修改）。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

void display(int k)
    {  //输出叶子结点，按层次遍历实际为队列先进先出 
        int flag=1;  //为了格式正确 
        int head=0,rear=0;
        int a[15];  //用作队列 
        a[rear++]=k;  //第一个元素为根结点 
        while(head<rear)
        {  // 
            int num=a[head++];  //用一个num来代替每一个根结点 
            if(t[num].lchild==-1 && t[num].rchild==-1)
            {  //如果当前根结点的左右孩子为空就输出这个叶子结点 
                if(flag)
                cout<<num;
                else
                cout<<" "<<num;
                flag=0;  //为了实现输出格式 
            }
            if(t[num].lchild!=-1)
            {  //如果当前根结点的左孩子不为空就从队尾入队 
                a[rear++]=t[num].lchild;
            }
            if(t[num].rchild!=-1)
            {  //如果当前根结点的右孩子不为空就从队尾入队 
                a[rear++]=t[num].rchild;
            }
        }
    }

display

最后还有一个格式问题（最后没有空格），这个就用老师讲的方法，用一个flag标记第一个输出只输出数据并修改flag的值，之后就输出数据+空格。

刚学习树，这道题刚开始我做的时候真的是一脸懵逼，首先要怎么把树的知识用上（接收数据并转换为树结构），怎么找到并输出叶子，参考了网上的代码一步步理解，看见说是用队列的思想我也是不太理解，就自己一步步在草稿纸上推发现代码上的好像还真是队列的特点，我的感受就是不理解的千万不要一昧地跟着别人的代码copy，要慢慢来今天不会明天就可能能懂了。

老师讲了题之后我们可以用stl来直接使用队列

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <queue>
    using namespace std;
    
    typedef struct
    {
        int lchild,rchild;
    }node;
    
    int input(node t[])
    {
        char ch1,ch2;
        int n;
        cin>>n;
        bool test[n]={
            false};
        for(int i=0;i<n;i++)
        {
            cin>>ch1>>ch2;
            if(ch1!='-')
            {
                t[i].lchild=ch1-'0';
                test[ t[i].lchild ]=true;
            }
            else t[i].lchild=-1;
            if(ch2!='-')
            {
                t[i].rchild=ch2-'0';
                test[ t[i].rchild ]=true;
            }
            else t[i].rchild=-1;
        }
        for(int j=0;j<n;j++)
        {
            if(!test[j])
            return j;
        }
    }
    
    void display(node t[],int r)
    {
        queue<int> q;
        int temp,flag=1;
        q.push(r);
        while(!q.empty())
        {
            temp=q.front();
            q.pop();
            if(temp!=-1)
            {
                if(t[temp].lchild==-1 && t[temp].rchild==-1)
                {
                    if(flag)
                    cout<<temp;
                    else
                    cout<<" "<<temp;
                    flag=0;
                }
                if(t[temp].lchild!=-1)
                q.push(t[temp].lchild);
                if(t[temp].rchild!=-1)
                q.push(t[temp].rchild);
            }
        }
    }
    int main()
    {
        node t[15];
        int root;
        root=input(t);
        display(t,root);
        return 0;
     }

stl

转载于:https://www.cnblogs.com/jingjing1234/p/10743192.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/b8822f656ea84a41b7b233421355ee89.png

发表评论取消回复

表情：

评论列表（有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

相关 List Leaves-----输出叶子节点

7-1 List Leaves （30 point(s)) Given a tree, you are supposed to list all the leaves in

小咪咪/ 2023年06月01日 06:17/ 0 赞/ 131 阅读

相关（Java）leetcode-1325 Delete Leaves With a Given Value（删除给定值的叶子节点）

题目描述给你一棵以 root 为根的二叉树和一个整数 target ，请你删除所有值为 target 的叶子节点。注意，一旦删除值为 target 的叶子节点，

落日映苍穹つ/ 2023年02月20日 07:38/ 0 赞/ 125 阅读

相关 mysql获取叶子节点数据

select b.\ from channel a right join channel b on a.parent\_id=b.channel\_id group by

古城微笑少年丶/ 2023年02月16日 05:48/ 0 赞/ 29 阅读

相关 Delete Leaves With a Given Value（C++删除给定值的叶子节点）

解题思路：（1）从上到下，遍历删除，因此采用后序遍历 / Definition for a binary tree node. struc

布满荆棘的人生/ 2023年01月02日 06:27/ 0 赞/ 151 阅读

相关 Deepest Leaves Sum（C++层数最深叶子节点的和）

解题思路：（1）先遍历求出最深的深度值（2）再遍历一次，将最深的节点值相加 / Definition for a binary tree node

亦凉/ 2022年12月29日 14:18/ 0 赞/ 176 阅读

相关 mysql 叶子节点_mysql求某一个根节点所有叶子节点

需求：通过一个user\_id找到它所在的部门，再找到它所在部门的最底层部门，再到这些最底层部门的人user\_id 表信息：部门信息表 CREATE TABLE

骑猪看日落/ 2022年11月05日 03:06/ 0 赞/ 184 阅读

相关 03-树2 List Leaves

include <stdio.h> include <ctype.h> struct Node { int root; //记录节点是否是根

矫情吗；*/ 2022年07月26日 04:06/ 0 赞/ 12 阅读

相关 404. Sum of Left Leaves(统计左叶子节点的和)

Find the sum of all left leaves in a given binary tree. Example: 3 / \

妖狐艹你老母/ 2022年01月05日 19:13/ 0 赞/ 195 阅读

相关 List Leave

本次作业是建立二叉树并输出叶结点（1）首先是定义结点，包括左孩子，右孩子 typedef struct { int lch;//左孩子

心已赠人/ 2021年12月19日 18:59/ 0 赞/ 144 阅读

相关 1004 Counting Leaves (30 分) 输出树每层的叶子节点数

A family hierarchy is usually presented by a pedigree tree. Your job is to count those f

ゝ一纸荒年。/ 2021年10月30日 00:42/ 0 赞/ 278 阅读