树的遍历

简介: 树的遍历

如果要实现树的结构,按照前面的链表实现指针域需要开一个数组,可能比较麻烦,这里采用静态实现,又考虑到一个结点的孩子树不确定,用vector定义变长数组,最后结构如下:

struct node{
   datatype data;
   vector<int>child;
}Node[maxn];

如果遇到某些问题只需要树的结点不需要数据域,上述结构还可以直接用vector<int>Node[maxn]代替

树有两种遍历,是先根遍历和层序遍历,根据上述结构其实现如下:

void preorder(int root) {  //先根遍历 
  printf("%d",Node[root].data);
  for(int i=0;i<Node[root].child.size();i++)
  preorder(Node[root].child[i]);
}
void layerorder(int root) { //层序遍历 
  queue<int>q;
  q.push(root);
  int temp;
  while(!q.empty()){
  temp=q.front();q.pop();
  printf("%d",Node[temp].data);
  for(int i=0;i<Node[root].child.size();i++){
    q.push(Node[root].child[i]);
  }
  } 
}

实际上,观察上述程序你会发现它和dfs、bfs十分相像,而遇到bfs,dfs问题可以将其途中的状态转化为树的结点,那问题也就直观的转化成对树的遍历问题。

对于求层次,求每层结点数、求路径这些问题应该熟练掌握。

相关文章
|
Java
switch的使用
这段 Java 代码首先提示用户输入一个代表月份的数字。通过 `Scanner` 类从键盘接收输入后,使用 `switch` 语句根据输入的数字来判断所属季节并输出相应的信息。例如,1、2 或 12 月为冬季。若输入不在 1 至 12 的范围内,则输出错误信息。此外,还展示了仅针对单个特定月份(如 1 月)进行匹配的简化示例。 ```markdown - 提示用户输入月份。 - 使用 `Scanner` 获取输入。 - 通过 `switch` 语句根据输入判断季节。 - 输出对应季节或错误信息。 - 展示了处理单个和多个月份的 `case` 示例。 ```
170 4
|
SQL 自然语言处理 监控
Elasticsearch 基础检索(全文检索/多语言检索/地理位置查询)
Elasticsearch是一个基于Lucene的实时的分布式搜索和分析引擎,设计用于云计算中能够达到实时搜索,稳定,可靠,快速,并支持RESTFUL风格的url访问。全文检索、多语言检索以及基于地理位置信息检索在Elasticsearch上应用广泛,本场实验将分别介绍如何使用Elasticsearch8.5版本进行全文检索、多语言检索和地理位置查询三个Elasticsearch基础检索子场景的实现。
19355 7
Elasticsearch 基础检索(全文检索/多语言检索/地理位置查询)
|
JavaScript Linux Windows
imagemagick安装调用报错command failed
记录下通过nodejs调用imagemagick 的时候发现的一个错误,command failed -- crop .
imagemagick安装调用报错command failed
|
XML Android开发 数据格式
Android自定义View示例(零)—很简单的自定义View
MainActivity如下:package cn.com; import android.app.Activity; import android.
1071 0
|
3天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
14天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1303 5
|
13天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1329 87
|
2天前
|
弹性计算 安全 数据安全/隐私保护
2025年阿里云域名备案流程(新手图文详细流程)
本文图文详解阿里云账号注册、服务器租赁、域名购买及备案全流程,涵盖企业实名认证、信息模板创建、域名备案提交与管局审核等关键步骤,助您快速完成网站上线前的准备工作。
183 82
2025年阿里云域名备案流程(新手图文详细流程)