JavaScript数据结构与算法-二叉树
前言：
之前做百度前端练习题时，遇到二叉树遍历的问题，由于不了解二叉树这种数据机构，自己只好学习一番并且总结如下。
树的简介
栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。直观地，树型结构是以分支关系定义的层次结构。
基础概念
树的定义
树（Tree）是n（n>=0）个结点的有限集。
在一颗非空树里：
- 有且只有一个根节点（root）
- 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,T3,...Tm，其中每一个集合本身又是一棵树，并且称为根的子树（Subtree）。
(a) 图只有一个根节点A ，（b）A是根节点，13个子节点，13个子节点分成3个互不相交的子集：T1={B,E,F,K,L},t2={D,H,I,J,M};T1,T2和T3都是根A的子树，且本身也是一棵树。
树的节点
树中的每个元素，都叫做节点。
树的结点包含一个数据元素及若干指向其子树的分支。该节点的子树被称为该节点的孩子并且该节点同时也是孩子的双亲
度：节点拥有的子树数目被称为
度
例如（b）B节点的度为2，D节点的度为3，度为0的节点称为叶子或者终端结点,反之称为非终端结点或分支结点。该树的度为拥有节点的度的最大值
节点的层次
节点的层次（Level）从根开始定义起，根为第一层，然后为第二层，依次顺序下去为n层。
深度： 树中节点的最大层数被称为树的深度或高度
例如 （b）树的深度为4
有序和无序树
如果将树中节点的各子树看成从左至右是有次序的（即不能交换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
森林
森林（Forest）是m（m>=0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。
二叉树
二叉树（Binary Tree）是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分（其次序不能任意颠倒。）
二叉树的性质
- 二叉树的第i层上最多有2的(i-1)方个节点。（i>=1）
- 深度为k的树最多有2的k次方-1个节点。（k>=1）
- 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1;
- 一棵深度为k且有2的k次方-1个结点的二叉树称为
满二叉树。 - 深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为
完全二叉树。
(我的理解是有限的节点个数里从左到右的编号要一一对应，否则不能称为完全二叉树)
注意：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。
二叉树的5个基本形态
- 空二叉树
- 只有一个根结点
- 根结点只有左子树
- 根结点只有右子树
- 根结点既有左子树又有右子树
二叉树的存储结构
-
顺序存储结构
用一维数组依照顺序存储树的节点，编号为i节点依次存储在数组下标i-1的元素里。i为0意味不存在此节点，这样的顺序存储适合完全二叉树。但是最坏的情况下，深刻为k并且只有k个节点的二叉树（每个节点的度小于2），那么意味着需要长度为2的k次方-1的一维数组来存储，非常浪费存储空间。
-
链式存储结构
二叉树的结点由一个数据元素和分别指向其左右子树的两个分支构成，则表示二叉树的链表中的结点至少包含三个域：数据域和左右指针域。有时，为了便于找到结点的双亲，则还可在结点结构中增加一个指向其双亲结点的指针域。利用这两种结构所得的二叉树的存储结构分别称之为二叉链表和三叉链表。
在含有n个结点的二叉链表中有n+1个空链域，我们可以利用这些空链域存储其他有用信息，从而得到另一种链式存储结构---线索链表。
二叉树的遍历
二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
二叉树的遍历有三种方式，如下：
-
（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。
-
（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。
-
（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。
前序遍历（DLR）
算法思路
若二叉树为空，则遍历结束；否则
⑴ 访问根结点；
⑵ 先序遍历左子树(递归调用本算法)；
⑶ 先序遍历右子树(递归调用本算法)。
遍历的顺序为：A B D H I E J C F K G
算法实现
//先序遍历
function preOrder(node){
if(!node == null){
putstr(node.show()+ " ");
preOrder(node.left);
preOrder(node.right);
}
}
中序遍历（LDR）
算法思路
若二叉树为空，则遍历结束；否则
⑴ 中序遍历左子树(递归调用本算法)；
⑵ 访问根结点；
⑶ 中序遍历右子树(递归调用本算法)。
遍历的顺序为：A B D H I E J C F K G
算法实现
//使用递归方式实现中序遍历
function inOrder(node){
if(!(node == null)){
inOrder(node.left);//先访问左子树
putstr(node.show()+ " ");//再访问根节点
inOrder(node.right);//最后访问右子树
}
}
后序遍历（LRD）
算法思路
若二叉树为空，则遍历结束；否则
⑴ 后序遍历左子树(递归调用本算法)；
⑵ 后序遍历右子树(递归调用本算法) ；
⑶ 访问根结点 。
遍历的顺序为：H I D J E B K F G C A
算法实现
//后序遍历
function postOrder(node){
if(!node == null){
postOrder(node.left);
postOrder(node.right);
putStr(node.show()+ " ");
}
}
个人水平有限，如有错误，还望指正，感激不尽！！！
参考链接
