当前位置:网站首页>二叉树 | 代码随想录学习笔记
二叉树 | 代码随想录学习笔记
2022-08-10 22:23:00 【Begonia_cat】
跟随carl代码随想录刷题
语言:python
本文为笔者学习二叉树的笔记,主要内容来自于代码随想录。
二叉树
二叉树的定义
二叉树的定义与链表差不多,只不过二叉树的节点里多了两个指针
:指向左右孩子。
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
二叉树的形式、平衡二叉树、二叉搜索树
- 二叉树主要有两种
形式
【不包含数值】:- 满二叉树
- 一棵二叉树只有
度为0
的节点和度为2
的节点,并且度为0
的节点在同一层上。 - 深度为
k
时,有2^k - 1
个节点。
- 一棵二叉树只有
- 完全二叉树
- 除了最底层节点可能没填满外,其余每层节点数都达到了最大值。并且最下面一层的节点都集中在该层
最左边的若干位置
。若最底层为n层
,则该层包含1~2^(h-1)
个节点。 堆
就是一个完全二叉树
- 除了最底层节点可能没填满外,其余每层节点数都达到了最大值。并且最下面一层的节点都集中在该层
- 满二叉树
- 二叉搜索树
二叉搜索树
是有序树
- 如果左子树不为空,则左子树上所有节点的值均
小于
它的根节点的值。 - 如果右子树不为空,则右子树上所有节点的值均
大于
它的根节点的值。
- 平衡二叉树(又称AVL树)
- 是
空树
或左右两个子树的高度差的绝对值不超过1
,并且左右两个子树
都是一棵平衡二叉树
红黑树是一种平衡二叉树 - 一定要知道自己所用语言的
常用的容器底层
是如何实现的
- 是
二叉树的存储方式
- 两种方式:
链式存储
- 用指针
- 元素散落在内存中的各个地址
顺序存储
- 用数组
- 元素在内存中是连续分布的
如果父节点的数组下标是
i
,那么它的左孩子就是i*2+1
,右孩子就是i*2+2
链式表示方式便于理解,一般都用链式存储二叉树(所以喔,
数组依然可以表示二叉树
)。
二叉树的遍历方式
- 主要有两种遍历方式:
深度优先遍历
- 先往深走,遇到叶子节点再往回走
- ️借助
栈
实现【栈是递归的一种实现结构】 - 按照
中间节点的遍历顺序
,可细分为三种遍历方式:- 前序遍历(递归法,迭代法)
中左右
- 中序遍历(递归法,迭代法)
左中右
- 后序遍历(递归法,迭代法)
左右中
前序、中序、后序递归遍历
代码
前序、中序、后序迭代遍历
代码
- 前序遍历(递归法,迭代法)
广度优先遍历
一层一层地去遍历
️借助
队列
实现层次遍历(迭代法)
边栏推荐
猜你喜欢
【开源教程5】疯壳·开源编队无人机-飞控固件烧写
How does the Weiluntong touch screen display the current value of abnormal data while alarming?
CFdiv2-Common Number-(奇偶数二分+规律)
EL表达式
QT笔记——vs + qt 创建一个带界面的 dll 和 调用带界面的dll
3598. 二叉树遍历(华中科技大学考研机试题)
配电网络扩展规划:考虑使用概率性能源生产和消费概况的决策(Matlab代码实现)
PyQt5 窗口自适应大小
Translating scientific and technological papers, how to translate from Russian to Chinese
德科立科创板上市:年营收7.3亿 市值59亿
随机推荐
String类的常用方法
RecyclerView滑动监听
QT笔记——vs + qt 创建一个带界面的 dll 和 调用带界面的dll
金山云CEO王育林离职:正值冲刺港股之际 雷军曾送金砖
JS学习 2022080
y93.第六章 微服务、服务网格及Envoy实战 -- Envoy配置(四)
BM7 链表中环的入口结点
BM13判断一个链表是否为回文结构
GMT,UTC,CST,DST,RTC,NTP,SNTP,NITZ: 嵌入式的时间
ThreadLocal comprehensive analysis (1)
QT笔记——QT工具uic,rcc,moc,qmake的使用和介绍
This visual tool artifact is more intuitive and easy to use!love so much
EL表达式
留言有奖|OpenBMB x 清华大学NLP:大模型公开课更新完结!
Redis
带着昇腾去旅行:一日看尽金陵城里的AI胜景
3598. Binary tree traversal (Huazhong University of Science and Technology exam questions)
make & cmake
LeetCode Daily 2 Questions 01: Reverse Strings (both 1200) Method: Double Pointer
美味的佳肴