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