佛山专业网站设计方案,招聘网站建设人员要求,虚拟主机免费空间,京东app下载官网免费下载参考#xff1a;https://www.hello-algo.com/chapter_tree/binary_tree/#711
1. 介绍
树存储不同于数组和链表的地方在于既可以保证数据检索的速度#xff0c;又可以保证数据插入删除修改的速度#xff0c;二者兼顾。
二叉树是一种很重要的数据结构#xff0c;是非线性的…参考https://www.hello-algo.com/chapter_tree/binary_tree/#711
1. 介绍
树存储不同于数组和链表的地方在于既可以保证数据检索的速度又可以保证数据插入删除修改的速度二者兼顾。
二叉树是一种很重要的数据结构是非线性的结构
非常多其他数据结构都是基于二叉树的基础演变而来的。
如一般二叉树、完全二叉树、满二叉树、线索二叉树、哈夫曼树、
二叉排序树、平衡二叉树、红黑树、B树。普通的二叉树很难构成现实的应用场景但因其简单常用于学习研究
平衡二叉树则是实际应用比较多的。
常见于快速匹配、搜索等方面。
常用的树有AVL树、红黑树、B树、Trie字典树。
1、AVL树: 最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。
2、红黑树: 平衡二叉树广泛用在C的STL中。如map和set都是用红黑树实现的。还有Linux文件管理。
3、B/B树: 用在磁盘文件组织 数据索引和数据库索引。
4、Trie树(字典树): 用在统计和排序大量字符串如自动机、M数据库索引。2 概念
2.1 二叉树的每个节点最多只能有两个子节点左、右节点 1. 「根节点 root node」位于二叉树顶层的节点没有父节点。
2. 「叶节点 leaf node」没有子节点的节点其两个指针均指向None
3. 「边 edge」连接两个节点的线段即节点引用指针。
4. 节点所在的「层 level」从顶至底递增根节点所在层为 1 。
5. 节点的「度 degree」节点的子节点的数量。在二叉树中度的取值范围是 0、1、2 。
6. 二叉树的「高度 height」从根节点到最远叶节点所经过的边的数量。
7. 节点的「深度 depth」从根节点到该节点所经过的边的数量。
8. 节点的「高度 height」从距离该节点最远的叶节点到该节点所经过的边的数量。2.2 完全二叉树
若设二叉树的高度为h除第 h 层外其它各层 (1h-1) 的结点数都达到最大个数第h层有叶子结点并且叶子结点都是从左到右依次排布这就是完全二叉树。
特征
叶子结点只可能在最下面的两层上出现对任意结点若其右分支下的子孙最大层次为L则其左分支下的子孙的最大层次必为L或L1
图示 特点
1若i为奇数且i1那么tree[i]的左兄弟为tree[i-1]2若i为偶数且in那么tree[i]的右兄弟为tree[i1]3若i1tree[i]的双亲为tree[i div 2]4若2*in那么tree[i]的左孩子为tree[2*i]若2*i1n那么tree[i]的右孩子为tree[2*i1]5若in/2那么tree[i]为叶子结点对应于36若i(n-1)/2那么tree必有两个孩子对应于47满二叉树一定是完全二叉树完全二叉树不一定是满二叉树8完全二叉树第i层至多有2^(i-1)个节点共i层的完全二叉树最多有2^i-1个节点。
2.3 满二叉树
