【算法通关指南：数据结构与算法篇 】二叉树相关算法题：1.新二叉树 2.二叉树的遍历

🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人方向学习者
❄️个人专栏：《算法通关指南》
✨ 永远相信美好的事情即将发生

文章目录

• 前言
• 二、新二叉树
  • 2.1题目
    • 2.2 算法原理
    • 2.3代码
• 三、 二叉树的遍历
  • 3.1题目
  • 3.2 算法原理
  • 3.3代码
• 总结与每日励志

前言

本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》 等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长

二、新二叉树

2.1题目

链接：新二叉树

2.2 算法原理

（1）建树：和常规的链式存储方式式⼀致。
因为结点是字符，所以可以直接用ASCII 码值当做下标来使用。比如’a’ 直接映射成97 ，l[97] 里面就存着’a’ 的左儿子，r[97]就存着’a’ 的右儿子，以此类推，建立二叉树。
2. 先序遍历：根左右。

2.3代码

#include<iostream> using namespace std;constint N =300;char l[N], r[N];voiddfs(char root){ cout << root;if(l[root]!='*')dfs(l[root]);if(r[root]!='*')dfs(r[root]);}intmain(){int n; cin >> n;char root; cin >> root; cin >> l[root]>> r[root];for(int i =2; i <= n; i++){char u; cin >> u; cin >> l[u]>> r[u];}dfs(root);return0;}

三、 二叉树的遍历

3.1题目

链接：二叉树的遍历

3.2 算法原理

仿照之前讲解二叉树的方式：建图+dfs

3.3代码

#include<iostream> using namespace std;constint N =1e6+10;int l[N], r[N];voiddfs1(int root){ cout << root <<" ";if(l[root])dfs1(l[root]);if(r[root])dfs1(r[root]);}voiddfs2(int root){if(l[root])dfs2(l[root]); cout << root <<" ";if(r[root])dfs2(r[root]);}voiddfs3(int root){if(l[root])dfs3(l[root]);if(r[root])dfs3(r[root]); cout << root <<" ";}intmain(){int n; cin >> n;for(int i =1; i <= n; i++){ cin >> l[i]>> r[i];}dfs1(1); cout << endl;dfs2(1); cout << endl;dfs3(1); cout << endl;return0;}

总结与每日励志

✨本文介绍了两个二叉树相关算法题：《新二叉树》和《二叉树的遍历》。在《新二叉树》中，通过ASCII码值映射节点建立二叉树，并实现先序遍历；《二叉树的遍历》则通过链式存储和深度优先搜索（DFS）完成前序、中序和后序遍历。代码简洁高效，适合算法初学者练习。文章强调以实战提升算法能力，鼓励读者坚持学习，相信努力终会收获成长。