6、树

前端中的树：dom tree + css rule = render tree，渲染和重绘
计算机中的树：在windows中，一切的东西都是存储在硬盘上的，windows是通过某个硬盘-某个硬盘的分区-分区上特定的系统文件
linux系统中的一切都是存在唯一的一个虚拟文件系统，这个虚拟的文件系统是树状的一个结构，一切都以根目录开始

树图示（DOM树）

树：
1、树（Tree）是n（n>=0）个结点的有限集，n=0，称为空树
2、从逻辑上看，树具有如下特点：
（1）任何非空树有且仅有一个结点没有前驱节点，这个结点就是根结点
（2）除根节点之外，其余的结点有且仅有一个直接的前驱结点
（3）包括根节点在内，每个结点可以有多个直接后继结点
（4）树形结构是一种具有递归特性的数据结构（任何一棵子树又满足树的概念）
（5）树形结构中的数据元素之间存在的关系是一对多，或者是多对一的关系
3、树的术语：
（1）结点的度：节点所拥有的子树的个数
（2）树的度：树中结点度的最大值
（3）叶子：终端结点，度为0的结点
（4）分支节点（非终端结点）：度不为0的结点，除根节点之外的分支结点统称为内部节点，根结点我们称为开始节点
（5）子节点：结点的直接后继（结点的子树的根）
（6）父节点：结点的直接前驱
（7）兄弟结点：同一个父节点
（8）子孙节点：
（9）祖先结点：
（10）路径：这个结点“自上而下”的通过每条路径上的每条边
（11）结点的层：根节点的层：1，其余节点的层数等于父节点的层数加1
（12）树的深度（高度）：树中所有结点层数的最大值

树的存储结构：
1、计算机只能是顺序存储或者链式存储，所以树这样的结构是不能够直接存储的，要将其转换为顺序或者是链式存储
双亲表示法：双亲表示法采用数组存储普通的树，其核心思想：顺序存储每个结点的同时，给各个结点附加一个记录其父节点位置的变量，存储的父节点的下标，实际操作的时候，就是从上往下，顺序去遍历一棵树，并为相应的域赋值，优点：可以快速的获取任意节点的父节点位置，缺点：如果要获取某个结点的子节点，需要遍历
2、孩子表示法：孩子表示法，是建立多个指针域，指向它的子节点的地址，也就是说，任何一个节点，都掌握他所有的子节点的信息，数组 + 链表的形式来实现，顺序表=>数组，从树的根节点开始，使用数组依次存储树的各个结点，需要注意的是：孩子表示法会给各个结点配备一个链表，用于存储各节点的孩子结点位于数组中的位置，如果说，结点没有子节点（叶子结点），则该节点的链表为空链表
3、孩子兄弟表示法：把普通的树，转换成二叉树，从树的根节点开始，依次用链表存储各个结点的孩子结点和兄弟结点
二叉树：其实所有的树的本质都是可以使用二叉树进行模拟出来的，所以二叉树非常重要

孩子兄弟表示法这个图有错误，F结点位置应该存在B的孩子指针域里

二叉树：
如果树中每个结点最多只能有两个子节点，这样的树我们称为：二叉树，只有两个分叉的树
二叉树是n个结点（n>=0）个结点的有限集合，如果这个集合是空集，空二叉树。
二叉树的特点：
1、每个结点最多有两棵子树，推导出二叉树中不存在度大于2的结点
2、左子树和右子树是有序的，次序是不能任意颠倒的
3、即使树中某个结点只有一棵子树，也要区分他是左子树还是右子树
满二叉树：在一棵二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有的叶子都在同一层上，这样的二叉树就是满二叉树
满二叉树叶子只能出现在最下一层，出现在其他层，不可能达成平衡，非叶子结点的度一定是2
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
完全二叉树：除最后一层外，其余层结点全满，最后一层只缺少右边的若干结点
如果树中每个结点最多只能有两个子节点，这样的树我们称为二叉树
二叉树可以为空，也就是没有结点
若不为空，则他是由根节点和称为其左子树TL和右子树TR的两个不相交的二叉树组成
性质：
1、在二叉树中，第i层上最多有2^i - 1次结点，（i>=1）第一层：2^1-1;
2、在二叉树中，如果深度为k，那么最多有2^k - 1 个结点
二叉树的存储：数组和链表，最合适的存储方式是：链表