数据结构（树）基础，虚拟dom，树的类型，二叉树的类型

树的简介

一棵树有且只有一个根节点
每个节点有零到多个子节点
每个子节点还有零到多个子节点
每个节点会保存节点的值
相邻的节点称为：邻居节点
没有子节点的节点称为：叶子节点
树的层数称为：树的高度
除了根节点以外，子节点以及它后续节点所形成的树称为：子树
树是应用最广泛的一种数据结构
比如：html dom，vertual dom的结构

一般用于：

verual dom（虚拟dom）

所谓的 virtual dom，也就是虚拟节点。它通过 JS 的 Object 对象模拟 DOM 中的节点，然后再通过特定的 render 方法将其渲染成真实的 DOM 节点。

https://blog.csdn.net/xiasohuai/article/details/100037640

树的分类

根据子节点数量的不同，分为：二叉树，三叉树 或者 多叉树

二叉树：

二叉树最为常见
每个节点最多有两个子节点

多叉树：

最常见的为 字典树

字典树又叫前缀树，一般用来存储一些单词或数字，在查找的时候比较方便，由于相同前缀只存储一次，所以也是比较省空间的

字典树是一棵树，一般用数组存储比较方便，从根节点出发，根节点不存储字母，每遇到一个字母，先判断树上是不是已经有了，如果有了，就顺着这条路；如果没有，新建立一条路径，直到最后一个字母，这时候将末尾字母所在位置染色，表示这是末尾字母。所以，字典树是一棵多叉树。

二叉树的类型

完全二叉树

每一层的节点都拥有两个子节点，最后一层除外，并且最后一层空缺的节点必须在右边，左边必须填满

满二叉树

二叉树每个节点要么有两个子节点，要么没有子节点，不能只有一个子节点

完美二叉树

所有的节点都有两个子节点，最后一层都是叶子节点

标题平衡二叉树

平衡二叉树的定义并不是很严格，不同的场景下有不同的定义

一个二叉树，如果大体上左右两棵子树看起来比较平衡，那么它就是平衡二叉树

有的定义是左右子树的每个节点的高度差都不大于一

二叉搜索树

二叉树左子节点的值小于等于节点值， 小于 右子节点的值，并且 左节点 和 它后续节点的值 都 小于等于 该节点的值，右节点 和它后续的值 都大于该节点的值

这样形成的树 方便进行搜索和排序，所以叫做二叉搜索树


对于 和节点相同的子节点 应该放在左边还是右边，不同的实现有不同的规定

自平衡二叉搜索树

这种树在 平衡二叉树和搜索二叉树 的基础上，会根据节点的插入和删除 自动保持平衡

常见的有：红黑树和AVL树

js的实现：

子节点（value，left，right）的类型都是TreeNode

value存树的值，left保存左子节点的引用，right保存右子节点的引用

注意：TreeNode是一个递归的类型
注意：树也是递归的结构

什么是递归类型

在计算机编程语言中，递归类型（又名：递归定义、隐含类型或隐含定义）是一种特殊的数据类型，它表示自身内部可能包含其它的同样类型的值。
https://baike.baidu.com/item/递归类型/2432721

因为树也是递归的结构，所以通过根节点可以找到所有的子节点类的剩余部分，可以定义和二叉树有关的操作

用的最多的应该是平衡二叉树，有种特殊的平衡二叉树红黑树，查找、插入、删除的时间复杂度最坏为O(log n)

Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
https://blog.csdn.net/fadbgfnbxb/article/details/88701343