共计 2038 个字符，预计需要花费 6 分钟才能阅读完成。
树结构和数组 / 链表 / 哈希表的比照有什么长处？
数组：
长处：
数组的次要长处是依据下标值拜访效率会很高
然而如果咱们心愿依据元素来查找对应地位呢？
比拟好的形式是先对数组排序，再进行二分查找
毛病：
须要先对数组进行排序，生成有序数组，能力进步查找效率
另外数组在插入和删除时，须要大量位移操作，效率很低
链表：
长处：链表插入和删除操作效率都很高
毛病：查找效率很低，须要从头开始顺次拜访链表中的每个数据项，直到找到，而且即便插入和删除效率很高，然而如果插入和删除两头地位的数据，还是须要重头先找到对应数据再进行操作。
哈希表：
长处：
咱们学过哈希表后，曾经发现哈希表的插入 / 查问 / 删除效率都十分高
毛病：
空间利用率不高，底层应用的是数组，并且某些单元格没有被利用
哈希表中的元素是无序的，不能依照固定程序来遍历哈希表中的元素
不能疾速的找出哈希表中的最大值或者最小值这些非凡值。
树结构：
咱们不能说树结构比其余构造都要好，因为每种数据结构都有本人特定的利用场景，然而树结构的确也综合了下面的数据结构的长处（当然长处有余于盖过其余数据结构，比方效率个别状况下没有哈希表高），并且也补救了下面数据结构的毛病，而且为了模仿某些场景，咱们应用树结构会更加不便，因为树结构是非线性的，能够示意一对多的关系，比方文件的目录构造。
树
树的术语：
1. 节点的度（Degree）：节点的子树个数
2. 树的度：树的所有节点中最大的度数
3. 叶节点（leaf）: 度为 0 的节点（也称为叶子节点）
4. 父节点（parent）: 有子树的节点是其子树的根节点的父节点
5. 子节点（child）: 若 A 节点为 B 节点的父节点，则成 B 节点是 A 节点的子节点；子节点也称孩子节点
6. 兄弟节点(sibling): 具备同一父节点的各节点彼此都是兄弟节点
7. 节点的档次(level)：规定根节点在 1 层，其余任一节点的层数是其父节点的层数加 1
9. 树的深度(Depth): 树中所有节点中的最大档次是这棵树的深度
树最一般的示意形式
这种示意形式因为不晓得有几个子节点 所以没有方法来定义绝对的连贯 比方下面的 A 有三个子节点 咱们能够定义 left 指向左子节点 right 指向右子节点 middle 指向两头子节点 然而如果它有四个子节点甚至更多那么咱们封装起来并不会这么直白的创立连贯了
儿子兄弟表示法
这种办法能够轻松的解决下面的问题 只须要一个 left 指针和 right 指针就能够将树结构出现进去
儿子兄弟表示法旋转
儿子兄弟表示法旋转将儿子兄弟表示法变成二叉树
树的品种
完满二叉树
完满二叉树也称为满二叉树
在二叉树中，出了最下一层的叶节点外，每层节点都有两个子节点，就形成了满二叉树
齐全二叉树
若设二叉树的深度为 k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第 k 层所有的结点都间断集中在最右边，这就是齐全二叉树。
完满二叉树是非凡的齐全二叉树
下图并不是齐全二叉树，因为 D 节点没有右节点，然而 E 节点就有了左右节点，解决办法：
1）减少 D 的右子节点 2）将 9 和 10 删掉
二叉树
二叉树概念
如果树中每个节点最多只能有两个子节点，这样的树就成为二叉树，下面咱们曾经提到了二叉树的重要性，不仅仅是因为简略，也因为简直所有的树都能够示意成二叉树的模式
二叉树的定义
二叉树能够为空，也就是没有节点，若不为空，则它是由根节点和称为其左子树 tl 和右子树 tr 的两个不相交的二叉树组成
二叉树有五种状态
（a）: 空树
（b）: 只有根节点
（c）: 只有左子树
（d）: 只有右子树
（e）: 左右子树都存在
二叉树有几个比拟重要的个性
一个二叉树第 i 层的最大节点数为：2^(i-1),i>=1;
如下图比方第三层最大个数 = 2^(3-1) = 2^2 = 4; 那么第三层最大的节点数就为 4
深度为 k 的二叉树有最大节点的总数为：2^k-1,k>=1;
以第四层为例，最大个数 = 2^4-1 = 16 – 1 =15；那么咱们下图中的树所有节点不能超过 15
对任何非空二叉树 T，若 n0 示意叶节点的个数，n2 是度为 2 的非叶节点个数，那么两者满足关系 n0=n2+1
这里的度为 2 就是左右子树都存在的节点，无论怎么画这颗树叶子节点的个数都等于度为 2 的非叶子节点 +1
二叉树的存储
二叉树的存储常见的形式是数组和链表
应用数组
齐全二叉树：按从上至下，从左到右顺序存储
非齐全二叉树
非齐全二叉树要转成齐全二叉树才能够依照下面的计划存储，然而会造成很大的空间节约
应用链表
二叉树最常见的形式还是应用链表存储
每个节点封装成一个 node,node 中蕴含存储的数据，左节点的援用，右节点的援用
二叉搜寻树
概念
二叉搜寻树（BST,Binary Search Tree）, 也称为二叉排序树或二叉查找树
二叉搜寻树是一颗二叉树，能够为空；
如果不为空，满足一下性质：
非空左子树的所有键值小于其根节点的键值。
非空右子树的所有键值大于其根节点的键值。
左，右子树自身也都是二叉搜寻树。
二叉搜寻树的特点
二叉搜寻树的特点就是绝对较小的值总是保留在左节点上，绝对较大的值总是保留在右节点上，查找效率十分高，这也是二叉搜寻树中搜寻的起源
