学习笔记-数据结构-树与二叉树（2024-4-22）
递归遍历二叉树 先序遍历： typedef struct BiTNode{ Elemtype data; struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;void PreOrder(BiTree T){ if(T!=NULL) { vist(T);//访问根节点 PreOrder(T->lchild);//递归遍历左子树 PreOrder(T-...
二叉检索树的查找删除（替换删除）的实现
支的结点（且一定是右子树上有元素），或者是叶子结点。 要删除当前结点，只需把右结点的元素赋值为当前结点元素即可，若是叶子结点赋None，也能达到目的 （1）代码 （2）图解 4、删除元素 （1）思路 二叉树中的结点可以根据分支分为三类 叶子结点、只有一个分支的结点、有两个分支的结点 对于叶子结点 只需要赋值为None，不会影响二叉树的结构 对于只有一个分支的结点 在删除最小元素的启发下，只需要将这个结...
【LeetCode: 95. 不同的二叉搜索树 II + DFS】
🍔 目录 🚩 题目链接⛲ 题目描述🌟 求解思路&实现代码&运行结果⚡ DFS🥦 求解思路🥦 实现代码🥦 运行结果 💬 共勉 🚩 题目链接 95. 不同的二叉搜索树 II ⛲ 题目描述 给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。 输入：n = 3 输出：[[1,null,2,null,3],[1,null,...
C++数据结构与算法——二叉树公共祖先问题
文章目录 一、236. 二叉树的最近公共祖先二、235. 二叉搜索树的最近公共祖先 一、236. 二叉树的最近公共祖先 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left...
【C++庖丁解牛】自平衡二叉搜索树--AVL树
AVL树的验证6 AVL树的删除(了解)7 AVL树的性能 前言 前面对map/multimap/set/multiset进行了简单的介绍，在其文档介绍中发现，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡...
P8681 [蓝桥杯 2019 省 AB] 完全二叉树的权值
题目描述 给定一棵包含 �N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 �1,�2,⋯��A1,A2,⋯AN，如下图所示： 现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。 注：根的深度是 11。 输入格式 第一行包含一个整数 �N。 第二行包含 �N 个整数 �1,�2,...
数据结构——二叉树——堆
左子树，2所在分叉成为右子树 还有一些规则如下： 对于学过离散数学的同学来说这部分知识并不难，没有学过的自己再去搜一下了解一下吧，这里只讲了一些大概内容 二、什么是堆 树里面有几个特殊的概念，例如完全二叉树和满二叉树，而堆就是完全二叉树的一种，完全二叉树就是除了最后一层外，其他层节点数达到最大 堆与普通的完全二叉树的不同在于它的大小堆的性质 例如： 三、堆的节点结构 typedef int HPDat...
代码随想录-二叉树（路径）
目录 257. 二叉树的所有路径 题目描述： 输入输出描述： 思路和想法： 404. 左叶子之和 题目描述： 输入输出描述： 思路和想法： 513.找树左下角的值 题目描述： 输入输出描述： 思路和想法： 112. 路径总和 题目描述： 输入输出描述： 思路和想法： 113.路径总和ii 题目描述： 输入输出描述： 思路和想法： 257. 二叉树的所有路径 题目描述： 给你一个二叉树的根节点 roo...
DAY16|104.二叉树的最大深度，111.二叉树的最小深度，222完全二叉树的个数
文章目录 104.二叉树的最大深度111.二叉树的最小深度222.完全二叉树的个数 104.二叉树的最大深度 思路： 1、此题有两种求解方式，一种是求根节点的高度，另一种是求二叉树的深度；如果求根节点的高度，则需要从叶子节点开始往上回溯，那么这一题和昨天的"对称二叉树"一题的思想如出一辙，通过后序遍历的思想，借助递归完成； 2、通过求二叉树深度的方式，则需要类似于昨天"二叉树的层级遍历"方式类似，使...
深入理解数据结构第二弹——二叉树（2）——堆排序及其时间复杂度
看这篇前请先把我上一篇了解一下：深入理解数据结构第一弹——二叉树（1）——堆-CSDN博客 前言： 目录 一、堆排序 1、堆排序的大体思路 2、堆排序的实例讲解 二、堆排序的时间复杂度 向下排序的时间复杂度 向上排序的时间复杂度 堆排序整体的时间复杂度 总结 一、堆排序 1、堆排序的大体思路 在上一篇我们已经讲过了堆是什么东西，我们已经知道堆有大堆和小堆两种形式，堆排序的想法正是借助它的这个特点诞生的...