10.1二叉树10.1.1为什么类似树的数据结构数组存储方式的分析
优点:采用下标方式访问元素,速度快。 对于规则数组,还可以使用二分搜索来提高搜索速度。
缺点:尝试搜索特定值或插入值时,整个“按一定顺序”会移动,导致效率低下[图像]
绘制操作示意图:
链存储方法分析优点:对数组存储方法进行了一定程度的优化。 例如,插入一个数字节点,将插入节点链接到链表即可,删除效率也很高。缺点:进行搜索时,(要搜索某个值,必须从第一个节点开始遍历)【图像】
操作示意图:
树存储方式分析
可以提高数据的保存、读取效率。 例如,Binary Sort Tree (二进制排序树)可以确保数据的搜索速度,同时还可以确保插入、删除和修改数据的速度。
情况:[7、3、10、1、5、9、12]
10.1.2树的示意图树的常用术语(结合示意图理解):
节点根节点的父节点的子节点的叶节点(没有子节点的节点)节点的权重(节点值)路径)从根节点找到该节点的根)层的子树的高度)最大层数)从森林:个以上的子树构成森10.1.3二叉树的概念树有很多种类,各节点二叉树的子节点分为左节点和右节点的图像
当该二叉树所有叶的节点都在最后一层,节点总数=2^n -1,n为阶数时,我们称之为满二叉树。
如果该二叉树的所有叶节点都在最后一层或倒数第二层,并且最后一层叶节点在左边连续,倒数第二层叶节点在右边连续,我们就称为完全二叉树。