首页 > 其他分享 >二叉树|二叉树理论基础、二叉树的递归遍历

二叉树|二叉树理论基础、二叉树的递归遍历

时间:2024-03-18 20:31:15浏览次数:22  
标签:遍历 TreeNode cur 递归 traversal vec 二叉树

代码随想录 (programmercarl.com)

树和二叉树

1.树的基本概念

1.1树的定义

1.2树的逻辑表示方法

1.3树的基本术语

1.4树的性质

1.5树的基本运算

1.6树的存储结构

2.二叉树的概念和性质

2.1二叉树的定义

2.2二叉树的性质

2.3二叉树与树、森林之间的转换

3.二叉树的存储结构

3.1二叉树的顺序存储结构

3.2二叉树的链式存储结构

4.二叉树的基本运算及其实现

5.二叉树的遍历

5.1二叉树遍历的概念

5.2先序、中序、后序遍历递归算法

先序遍历:

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

中序遍历:

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中
    traversal(cur->right, vec); // 右
}

后序遍历:

 

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
}

5.3先序、中序、后序遍历非递归算法

5.4层次遍历算法

6.二叉树的构造

二叉树的定义:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

以上,列了一个目录,如果你都明白了,就说明你已经对树和二叉树有一个认识和了解了。

前序:

 

 

只要搞懂了一个遍历的代码实现,其他的就模仿一下子写出。 

标签:遍历,TreeNode,cur,递归,traversal,vec,二叉树
From: https://blog.csdn.net/Talking999/article/details/136819170

相关文章

  • 2733: 【搜索】【广度优先】 马遍历棋盘
    题目描述有一个n*m的棋盘(1<n,m<=400),在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步输入一行四个数据,棋盘的大小和马的坐标输出一个n*m的矩阵,代表马到达某个点最少要走几步(左对齐,宽5格,不能到达则输出-1)样例输入4411样例输出0325......
  • Python 递归函数实现二分法,带思路解释
            二分法可以大大提升对有序数列的查找,传统的迭代查找会挨个比较数列中的值,如果数列较为庞大会影响查询效率。二分法每次取数列的中间数与待查找数字比较大小,以升序排列为例子 首先要考虑数列长度的奇偶性。        奇数取中间位置的数字,如果比待查找......
  • 力扣---验证二叉搜索树---前根/中根/后根遍历
     题目解析参考:验证二叉搜索树_哔哩哔哩_bilibili一开始做呢,就跟这位老兄一样:因为没有考虑到5和3的比较接下来走入整体:先根遍历解法:首先 每个点其实都有范围,比如根节点的范围在(-INF,INF),就拿上面图片举例子,4这个节点的范围应该是(-INF,5),所以先序遍历,我们要先比较根......
  • 洛谷题单指南-二叉树-P3884 [JLOI2009] 二叉树问题
    原题链接:https://www.luogu.com.cn/problem/P3884题意解读:要计算二叉树的深度、宽度、节点间的距离,深度、宽度的概念很好理解,节点间的距离描述是:节点u,v之间的距离表示从u到v的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。说人话就是:u到v的距离=uv最近公共祖先到u......
  • 关于scss手动遍历生成类名
    1、自动生成宽度类名$width-name:300,100;@each$namein$width-name{.w#{$name}{width:$name+px;}};//以上代码将会生成.w300{width:300px;};.w100{width:100px;}2、自动生成间距类名$margin-name:(mt:(16,24,10),mb:(16),ml:......
  • 你还在用for循环遍历list吗?
    简介Java8API添加了一个新的抽象称为流Stream,可以让你以一种声明的方式处理数据。Stream使用一种类似用SQL语句从数据库查询数据的直观方式来提供一种对Java 集合运算​和表达的高阶抽象。这种风格将要处理的元素集合看作一种流,流在管道中传输,并且可以在管道的节......
  • 递归组件实现子向父传值
    业务逻辑:通过自己调用自己的方式生成树,再点击子菜单时,需要将点击子菜单的菜单名传值给父组件(使用总线bus) 新建bus.js文件import{ref}from'vue'classBus{constructor(){//收集订阅信息,调度中心this.eventList={},//事件列表,这项是必须的//......
  • 一.函数的递归
    简单而通俗易懂的说,函数的递归就是:函数自己调用自己。就是把大事化小事,递的意思就是推进的意思。归就是回归的意思。递归的限制:两个条件:1.递归存在限制条件,当满⾜这个限制条件的时候,递归便不再继续。                        ......
  • 二叉树的广度优先遍历(力扣102)
    文章目录题目前知BFS是什么?队列的基本操作有什么?题解一、思路二、解题方法三、Code总结题目Problem:102.二叉树的层序遍历给你二叉树的根节点root,返回其节点值的层序遍历。(即逐层地,从左到右访问所有节点)。前知BFS是什么?树的广度优先遍历(BFS)是一种遍......
  • 树与二叉树(数据结构)
    本篇博客讲解树与二叉树,后续会继续讲解堆——————————————————————1.树概念及结构1.1树的概念 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的......