本文记录了自己做的关于树的四道题目。
@[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);
}
}
这就是我要介绍的四道题,比较简单。如果说的有不恰当的地方,可以在下方评论,或者私聊我😉,我会及时改正的。
如果看了有收获,可以点赞加关注😉,看计算机小白的成长之路。