欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 科技 > 名人名企 > 浙大数据结构:03-树2 List Leaves

浙大数据结构:03-树2 List Leaves

2024/11/29 18:01:51 来源:https://blog.csdn.net/qq_74924951/article/details/141996562  浏览:    关键词:浙大数据结构:03-树2 List Leaves
这道题我借用了一点上一题的代码思路,这题考察的主要是层序遍历,即用队列来实现,当然此处我依然采用数组模拟队列来实现。
机翻

1、条件准备

map的键存下标,后面值分别存左右子树的下标,没有子树就存-1.
head数组只是为了找到树的跟结点在哪,实现原理后面再说
q数组是模拟队列,front是队头下标,rear是队尾下标
#include <iostream>
#include <map>
using namespace std;map<int, pair<int, int>> m;
int head[15];
int q[50], front = 0, rear = -1;
 主函数先是加快输入输出,h存根节点的下标,traval是进行层序遍历并输出

int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int h;h = init(m);traval(h);return 0;
}

2、init函数

先输入结点数n,然后循环输入数据,每组数据的子结点存到map里面,如果没有子节点存-1.
然后标记子节点出现过的数字,用head数组存,最后遍历head数组,没有标记的就是根节点。
因为根节点不会出现在任一组数据中,所以可以这样找到。
int init(map<int, pair<int, int>> &m)
{int n;cin >> n;for (int i = 0; i < n; i++){char f, s;cin >> f >> s;m[i].first = f == '-' ? -1 : f - '0';m[i].second = s == '-' ? -1 : s - '0';if (m[i].first != -1)head[m[i].first] = 1;if (m[i].second != -1)head[m[i].second] = 1;}for (int i = 0; i < n; i++){if (head[i] == 0)return i;}return -1;
}

3、traval函数

用队列先把根节点放入,flag是为了调整输出格式的。
遍历队列,取出队头,如果为叶子结点则输出,只有第一次输出不加空格。
然后若该结点有子节点,放入队列,然后弹出队头。
void  traval(int h)
{q[++rear] = h;int flag = 1;while (front <= rear){int t = q[front];if (m[t].first == -1 && m[t].second == -1){if (flag){ cout <<t;flag=0;}elsecout << ' ' << t;}if (m[t].first != -1)q[++rear] = m[t].first;if (m[t].second != -1)q[++rear] = m[t].second;front++;}
}

4、总结

这道题相对而言没有那么难了,还是较为友好的。
完整代码如下:
#include <iostream>
#include <map>
using namespace std;map<int, pair<int, int>> m;
int head[15];
int q[50], front = 0, rear = -1;int init(map<int, pair<int, int>> &m)
{int n;cin >> n;for (int i = 0; i < n; i++){char f, s;cin >> f >> s;m[i].first = f == '-' ? -1 : f - '0';m[i].second = s == '-' ? -1 : s - '0';if (m[i].first != -1)head[m[i].first] = 1;if (m[i].second != -1)head[m[i].second] = 1;}for (int i = 0; i < n; i++){if (head[i] == 0)return i;}return -1;
}void  traval(int h)
{q[++rear] = h;int flag = 1;while (front <= rear){int t = q[front];if (m[t].first == -1 && m[t].second == -1){if (flag){ cout <<t;flag=0;}elsecout << ' ' << t;}if (m[t].first != -1)q[++rear] = m[t].first;if (m[t].second != -1)q[++rear] = m[t].second;front++;}
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int h;h = init(m);traval(h);return 0;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com