树是n（n>=0）个节点的有限集，当n为0时为空树。在任意一颗非空的树中：有且仅有一个根节点；
子节点互不相交，且子节点之间又构成了一颗颗子树。树是一对多的数据结构
基本概念
节点拥有的子树数称之为节点的度；最大的节点度称之为树的度；度为0的节点称之为叶子节点或终端节点，度不为0则称之为内部节点或分支节点
节点的子树的根为该节点的子节点；该节点则为子树的父节点；子节点的子树的根称之为该节点的孙子节点；子节点的同级节点互为兄弟节点
节点的最大层次称为树深
有序树：节点的子树从左到右有序且不能互换
森林：m颗树的集合
树的常用操作
树的结构定义
双亲表示法
每个节点结构如下
JavaScript实现
假设后台返回的数据结构如下
由于双亲表示法是向上查找，故利用js的对象引用关系保留最后一位节点即可保留下整颗
树
节点查找结果如下
（这段代码只适用于子节点为0或1的情况，由于没有对子节点进行保留，故只能保留下最后一级的最后一个子节点）
孩子表示法
每个节点的度表示其拥有的子树数，如果能在每个节点下记录度根则可以正确表示出每个节点
。有两种可选方案：指针域的个数等于树度、指针域个数等于节点的度数。这两种方案的节点结
构一致
方案一
JavaScript代码如下
生成的树结构如下
可以看到，对于终端节点的child中存在很多是以undefined构造的无意义数组。这是一种对空间的浪费。因此衍生出第二种：按照节点的度存储。具体来说，就是把每个节点排列起来，以单链表作存储结构，则n个节点有n个孩子链表，如果是叶子节点则此单链表为空。然后n个头指针（节点的左侧第一个子节点）又组成一个线性表，采用顺序存储结构，存放进一个一维数组中
方案二
JavaScript代码如下
创建的树结构如下
孩子兄弟表示法（二叉树）
对于一个节点而言，它的左右节点是唯一的。图示如下
二叉树
二叉树是n个节点的有限集合，该集合或者为空或者由一个根节点和两颗互不相交分、分别为根节点的左子树和右子树的二叉树组成（对于在某个阶段总是两种结果的情况，如开关、0和1、真假、上下、对错、正反等，都适用二叉树建模）
二叉树的特点
每个节点至多有两颗子树
左右子树次序不能互换
基本形态
空二叉树
只有一个根节点
根节点只有左子树
根节点只有右子树
根节点既有左子树又有右子树
特殊二叉树
斜数
只有左子树或右子树因此每一层只有一个节点，节点的个数即二叉树的深度
满二叉树
在一颗二叉树中，如果所有分支节点都存在左右子树，且所有叶子在同一层，即为满二叉树
完全二叉树
对一颗具有n个节点的二叉树按层序编号，若编号为i(i大于等于1小于等于n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置完全相同，则为完全二叉。满二叉一定是完全二叉
特点：叶子节点只能出现在最下两层；
最下层的叶子一定集中在左部连续位置；
倒数二层，若有叶子节点，一定在右部连续；
如果节点度为1，则该节点只有左孩子，不存在只有右子树的情况；
同样节点数的二叉树，完全二叉树的深度最小
二叉树性质
在二叉树的第i层上至多有
-1个节点（i大于等于1）
深度为k的二叉树至多有
个节点（k大于等于1）
对任何一颗二叉树T，若其终端节点数为a,度为2的节点数为b,则a=b+1
具有n个节点的完全二叉树的深度为
+1
如果对一颗有n个节点的完全二叉树的节点按层序编号，则对任一节点有：
如果i=1，则节点i是二叉树的根，无双亲；如果i>1,则其双亲是节点
如果2i>n，则节点i无左孩子（节点i为叶子节点）；否则其左孩子是节点2i
如果2i+1>n，则节点i无右孩子；否则其右孩子是节点2i+1
二叉树的存储结构
顺序（数组）
顺序存储只适用于完全二叉树，如果想使普通二叉树应用顺序存储，需先进行转换。之后按照层次将树中的节点存到数据即可
如图
在数组中的存储为
链式（二叉链表）
节点结构如下
二叉树的遍历
二叉树的遍历按照从左到右分为四种：前序、中序、后序、层序
假设有树结构图示如下
数据如下
则JavaScript代码创建的二叉链表如下
I-将数据转换成链式结构
生成的树结构如下
前序遍历（当前节点的根
当前节点左子树
当前节点右子树）
遍历结果为
中序遍历（当前节点左子树
当前节点的根
当前节点右子树）
结果为
执行顺序：
从节点A开始，遍历左子树，即B为根节点的子树
从节点B开始，遍历左子树，即D为根节点的子树
从节点D开始，遍历左子树，即G为根节点的子树
从节点G开始，遍历左子树，无
访问根节点G
从节点G开始，遍历右子树，无。子树G遍历结束，即子树D的左子树结束
开始遍历节点D的右子树，找到以H为根的子树
从节点H开始，访问左子树，无
访问根节点H
访问右子树，无。子树D遍历结束，即子树B的左子树结束
访问根节点B
......
后续遍历（当前节点左子树
当前节点右子树
当前节点的根）
结果为
二叉树的创建
二叉树的创建过程实际上和遍历过程是一样的。只不过是将遍历时的打印换成了节点创建。对于树
我们要通过一定的"补位措施"将其转换为满二叉树，对于"补"出来的节点进行特殊标记
对于该扩展树的前序遍历结果为
则生成的树的代码为
结果为
根据前序遍历的输出为
