树的一些题目


本文记录了自己做的关于树的四道题目。

@[TOC]

1 统计二叉树的叶结点个数

统计二叉树的叶结点个数
【问题描述】以二叉链表作为二叉树的存储结构, 统计二叉树的叶结点个数。

【输入形式】一行字符序列(限定大写字母为结点元素,#代表空树)。
【输出形式】数字,代表叶结点个数。
【样例输入】ABC##DE#G##F###

【样例输出】3
样例以先序遍历的顺序建立二叉链表后统计叶子结点个数。

#include<iostream>
#include<stdio.h>

using namespace std;

typedef struct bitnode
{
    char data;
    struct bitnode *lchild,*rchild;
}BitNode,*BitTree;

void createTree(BitTree &t)
{
    char ch;
    cin>>ch;
    if (ch == '#')
    {
        t = NULL;
        return;
    }
    else
    {
        t = new BitNode;
        t->data = ch;
        createTree(t->lchild);
        createTree(t->rchild);
    }
}

int traverse(BitTree t)
{
    if (t == NULL)
    {
        return 0;
    }
    if (t->lchild == NULL && t->rchild == NULL)
    {
        return 1;
    }
    else
    {
        return traverse(t->rchild) + traverse(t->lchild);
    }
}

int main()
{
    //freopen("tt2.txt","r",stdin);
    BitTree t;
    createTree(t);
    cout<<traverse(t)<<endl;
    return 0;
}

tt1.txt:

ABC##DE#G##F###

树的结构就不说了,然后createTree函数是按先序的顺序来建立树。建立之后调用traverse函数查找叶子节点,traverse函数采用递归的方法,当遇到空节点时,返回0.当遇到左右子节点为空时,返回1,否则递归调用左右子节点,然后返回它们的和。

2 自底向上的层次遍历

【问题描述】

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

【输入形式】

一行,包含用空格分开的n个元素,每个元素为整数或者None(None表示空结点),依次表示按自顶向下层次遍历的二叉树结点。

注:空结点对应的“孩子”(实际上不存在)不再用None表示,直接跳过。例如二叉树:

输入表示为:

1 2 3 None None 4 5 6

而非:

1 2 3 None None 4 5 None None None None 6

【输出形式】

自底向上的层次遍历,每个数之间用空格分开,不需要输出None。

【样例输入】

3 9 20 None None 15 7

【样例输出】

15 7 9 20 3

【样例说明】

二叉树为:


本题的难点是有两个,一个是因为特殊的输入形式,所以导致建立树比较麻烦。另一个是底遍历,一开始我是打算用栈来处理,后来发现输出的为7 15并不是15 7.于是采取了另一种方法,利用一个二维数组来存储,然后在进行输出。
先来看第一个难点:
首先树的结构和上题的结构一样,就不说了,下面的两题也是一样的。这里主要讲一下建树的过程。
因为采用层次的顺序对节点进行输入,所以我们需要借助队列来进行建树。

void createTree(BitTree &v)
{
    queue<BitNode*> q;
    char ch[8];
    char *T="None";
    cin>>ch;
    BitNode* n = new BitNode;
    n->data=atoi(ch);
    v = n;
    q.push(n);
    while (q.size() != 0)
    {
        BitNode *t = q.front();
        q.pop();
        if (t != NULL)
        {
            if (cin>>ch)
            {
               BitNode *d1 = new BitNode;
               if (strcmp(ch, T) != 0)
               {
                   d1->data=atoi(ch);
                   t->lchild = d1;
                   q.push(d1);
               }
               else
               {
                   t->lchild = NULL;
               }
            }
            else
            {
                t->lchild = NULL;
            }
            if (cin>>ch)
            {
                BitNode *d2 = new BitNode;
                if (strcmp(ch, T) != 0)
                {
                    d2->data=atoi(ch);
                    t->rchild = d2;
                    q.push(d2);
                }
                else
                {
                    t->rchild = NULL;
                }
            }
            else
            {
                t->rchild = NULL;
            }
        }
    }
}

代码写的可能有些冗余🙁。思路也比较简单,就不说了。

接下来就是从底层遍历,这里采用了一种比较差劲的方法,采用数组来存储。这样会造成大量空间的浪费,但是我又想不到其它的数据结构,如果有更好的数据结构,可以在下方评论,我会及时更改的。

int dd[100][100];

int traverse(BitTree &t)
{
    if (t == NULL)
    {
        return 0;
    }
    if (t->lchild == NULL && t->rchild == NULL)
    {
        return 1;
    }
    else
    {
        return 1 + max(traverse(t->rchild), traverse(t->lchild));
    }
}

void init()
{
    for (int i = 0; i < 100; ++i)
    {
        for (int j = 0; j < 100; ++j)
        {
            dd[i][j] = 0;
        }
    }
}

void ddd(BitTree &t, int cnt)
{
    if (t == NULL)
    {
        return ;
    }
    else
    {
        int i = 0;
        while(dd[cnt][i] != 0)
        {
            i++;
        }
        dd[cnt][i] = t->data;
        ddd(t->lchild, cnt + 1);
        ddd(t->rchild, cnt + 1);
    }
}
//这是用来输出的,放在main方法体,或者单独一个函数里都可以。
init();
for (int i = traverse(v); i > 0; --i)
    {
        int j = 0;
        while(dd[i][j] != 0)
        {
            cout<<dd[i][j]<<" ";
            j++;
        }
    }

思路比较简单,利用cnt记录层数,不过代码写的似乎并不好😢。

3 树有多深

【问题描述】接着上周的题,求树的最大深度
【输入形式】一个数组
【输出形式】深度
【样例输入】

3 9 20 None None 15 7
【样例输出】

3
【样例说明】

【评分标准】送分题

hhh,送分题,比较简单,其实就是上一题的traverse函数,不过这一切都是建立在把树建立好的情况下,如果树没建好,就比较难了。

int traverse(BitTree &t)
{
    if (t == NULL)
    {
        return 0;
    }
    if (t->lchild == NULL && t->rchild == NULL)
    {
        return 1;
    }
    else
    {
        return 1 + max(traverse(t->rchild), traverse(t->lchild));
    }
}

4 二叉树的中序遍历

【问题描述】

给定一个二叉树,按中序遍历的顺序输出。

【输入形式】

一行,包含用空格分开的n个元素,每个元素为整数或者None(None表示空结点),依次表示按层次遍历的二叉树结点。

【输出形式】

中序遍历的所有结点,每个数之间用空格分开,不需要输出None。

【样例输入2】

1 2 3 None None 4 5

【样例输出2】

2 1 4 3 5

【样例说明2】

这俨然又是一道送分题啊,但是还是得建立在把树建好的情况下。

void middle(BitTree &t)
{
    if (t == NULL)
    {
        return ;
    }
    else
    {
        middle(t->lchild);
        cout<<t->data<<" ";
        middle(t->rchild);
    }
}

这就是我要介绍的四道题,比较简单。如果说的有不恰当的地方,可以在下方评论,或者私聊我😉,我会及时改正的。

如果看了有收获,可以点赞加关注😉,看计算机小白的成长之路。


文章作者: vrerain
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 vrerain !
评论
  目录