在实际场景中，常常存在着一对多，甚至多对多的情况，有许多逻辑并不是简单的线性关系，而 树 和 图 就是典型的非线性数据结构，
树
什么是树，在生活中有很多体现树的逻辑的例子:
在数据结构中，树的定义如下：
树 (tree) 是 n (n>=0) 个节点的有限集，当 n=0 时，称为空树，在任意一个非空树中，有如下特点：
1. 有且仅有一个特定的称为根的节点
2. 当 n > 1 时，其余节点可以分为 m(m>0) 个互不相交的有限集合，每个集合本身又是一个树，并称为根的子树
下边这张图就是标准的树结构
在上图中，节点1 是根节点，节点 5，6，7，8，9是树的末端，没有"孩子"，称为叶子节点(leaf)，图中虚线部分，是根节点1的其中一个 子树
同时，树的结构从根节点到叶子节点，分为不同的层级，它的上下级和同级节点关系如下：
节点4的上一级节点，是节点4的父节点(parent), 从节点4衍生出来的节点, 是节点4的子节点(child)，和节点4同级的，由同一个父节点衍生出来的节点，称为节点4的**兄弟节点(sibling)，**树的最大层级数，称为树的高度或深度，上图的这个树的高度是4
二叉树
二叉树(binary tree)是树的一种特殊形式，二叉，顾名思义，这种树的每个节点最多有两个孩子节点，需要注意的是，这里是最多有两个孩子节点，可以为一个，也可以没有
二叉树的结构如图所示：
二叉树节点的两个孩子节点，一个被称为左孩子(left child), 一个被称为右孩子(right child)，这两个孩子的顺序是固定的
此外，二叉树有两种特殊的形式: 满二叉树、完全二叉树
满二叉树
一个二叉树上的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，这个树就是满二叉树
完全二叉树
对于一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号从1到n，如果这个树所有节点和同样深度的满二叉树的编号从1到n的节点位置相同，则这个二叉树称为完全二叉树
完全二叉树的高度为logn+1 向下取整(从1 开始)
如下图：
这个二叉树的编号从1到12，和前边的满二叉树编号从1到12的节点位置完全对应，因此这个树是完全二叉树
数据结构可以分为物理结构和逻辑结构，二叉树属于逻辑结构，它可以用多种物理结构来表达(数组，链式储存结构)
链式储存结构
二叉树的每个节点包含三个部分：
1. 储存数据的data
2. 指向左孩子的left指针
3. 指向右孩子的right指针
数组
使用数组储存时，会按照层级顺序，把二叉树的节点放到数组中对应的位置上去，如果某一个节点的左孩子或者右孩子空缺，则数组的相应位置也空出来
这样做的目的是更方便的在数组中定位二叉树的孩子节点和父节点
例如一个父节点的下标为parent，那么它的左孩子节点下标为 2*parent + 1，右孩子节点下标为 2*parent+2，反过来，假设一个左孩子节点的下标为 leftChild，那么它的父节点下标为 (leftChild - 1) / 2
显然对于一个稀松的二叉树来说，用数组的表示方法是非常浪费空间的
二叉树的应用
二叉树包含很多特殊的形式，每一种形式都有自己的作用，但是其中最主要的应用还是在于查找操作和维持相对顺序这两个方面
查找
特殊的二叉树：二叉查找树
二叉查找树在二叉树的基础上增加了以下几个条件：
1. 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
2. 如果右子树不为空，则右子树上所有节点的值均大于根节点的值
3. 左右子树也都是二叉查找树
下图就是一个标准的二叉查找树：
例如查找值为4的节点，步骤如下：
1. 访问根节点6，发现4 < 6
2. 访问6的左孩子节点3，发现 4 > 3
3. 访问3的右孩子节点4，发现4=4，正是要查找的节点
对于一个节点分布相对均衡的二叉查找树来说，如果节点的总数是n，那么搜索节点的时间复杂度就是 O(logn)
维持相对顺序
二叉查找树要求左子树小于根节点，右子树大于根节点，正是这样保证了二叉树的有序性，因此二叉查找树还有另外一个名字：二叉排序树
如上例子，新插入一个节点5，由于 5 < 6, 5 > 3, 5 > 4,则节点5将插入到节点4的右孩子的位置
新插入一个节点10, 由于10 > 6, 10 > 8, 10 > 9, 则节点10将会插入到节点9的右孩子的位置
存在的问题：
在二叉查找树中依次插入9、8、7、6、5、4
不仅外形变得怪异了，查询的时间复杂度也变成了 O(n)，解决这个问题就涉及到了二叉树的自平衡
二叉树的遍历
当介绍数组、链表的时候为什么没有着重研究它们的遍历过程
二叉树的遍历又有什么特殊之处
在计算机程序，遍历本身是一个线性操作，所以遍历同样是线性数据结构的数组和链表是一件轻而易举的事情
但是二叉树是一个典型的非线性数据结构，遍历时，需要把非线性关联的节点转换成一个线性的序列，以不同的方式来遍历，则遍历出来的序列顺序也是不同的
二叉树的遍历方式
从节点位置关系来看，二叉树的遍历分为4种
1. 前序遍历
2. 中序遍历
3. 后序遍历
4. 层序遍历
从更宏观的角度来看，二叉树的遍历分为两大类
1. 深度优先遍历(前序遍历、中序遍历、后序遍历)
2. 广度优先遍历(层序遍历)
深度优先遍历
深度优先和广度优先这个两个概念不止局限于二叉树，它们更是一种抽象的算法思想，决定了访问某些复杂数据结构的顺序。
所谓深度优先，顾名思义，就是偏向于纵深，"一头扎到底"的访问方式
1. 前序遍历
二叉树的前序遍历，输出顺序是：根节点、左子树、右子树
上边是一个二叉树的前序遍历，每个节点左侧序号代表该节点输出顺序，详细步骤如下：
1. 首先输出根节点 1
2. 由于根节点 1 存在左孩子，输出左孩子节点 2
3. 由于节点 2 也存在左孩子，输出左孩子节点 4
4. 节点 4 既没有左孩子也没有右孩子，那么回到节点 2 ，输出节点 2 的右孩子 节点 5
5. 节点 5 既没有左孩子也没有右孩子，那么回到节点 1，输出节点 1 的右孩子 节点 3
6. 节点 3 没有左孩子，但是有右孩子，因此输出节点 3 的右孩子 节点 6
2. 中序遍历
二叉树的中序遍历，输出顺序是：左子树、根节点、右子树
上边是一个二叉树的中序遍历，详细步骤如下
1. 首先访问根节点的左孩子，如果这个左孩子还有左孩子，则继续深入访问下去，一直找到不再有左孩子的节点，并输出该节点，显然第一个没有左孩子的节点是节点 4 ，
2. 依照中序遍历的次序，接下来输出节点 4 的父节点，节点 2
3. 再输出节点 2 的右孩子 节点 5
4. 以节点 2 为根节点的左子树已经遍历完毕，这时再输出整个二叉树的根节点 节点 1
5. 由于节点 3 没有左孩子，所以直接输出 根节点的右孩子 节点 3
6. 最后输出节点 3 的右孩子 节点 6
3. 后序遍历
二叉树的后序遍历，输出顺序是左子树，右子树、根节点
上边是一个二叉树的后序遍历，详细步骤如下：
1. 和中序遍历相同，首先访问根节点的左孩子，如果这个左孩子还有左孩子，则继续深入访问下去，一直找到不再有左孩子的节点，并输出该节点，则输出节点 4
2. 依据中序遍历的次序，接下来输出节点 4 的根节点 节点 2 的右孩子，节点 5
3. 再节点4 的根节点 节点 2
4. 以节点 2 为根节点的左子树已经遍历完毕了，接下来访问 根节点 1 的右孩子，节点 3，
5. 由于节点 3 没有左孩子，则访问节点 6，
6. 由于节点 6 没有左孩子，也没有右孩子，则输出节点 6，
7. 接下来输出 节点 6的根节点 节点 3
8. 最后输出节点 3 的根节点 节点 1
深度优先遍历代码实现
递归实现：
1 interface TreeNodeType{ 2 data: any; 3 leftChildren: TreeNodeType | null; 4 rightChildren: TreeNodeType | null; 5 } 6 7 8 class TreeNode implements TreeNodeType{ 9 data: any; 10 leftChildren: TreeNodeType | null; 11 rightChildren: TreeNodeType | null; 12 constructor(params:any){ 13 this.data = params; 14 this.leftChildren = null; 15 this.rightChildren = null; 16 } 17 } 18 /** 19 * @param {Array<any>} list 20 * @param {number} [index] 要读取的节点下标 21 * @returns {(TreeNodeType|null)} 22 * @description 创建二叉树 23 */ 24 function createBinaryTree(list:Array<any>, index?:number):TreeNodeType|null { 25 if(!Array.isArray(list) || !list.length){ 26 return null 27 } 28 let node = null; 29 let i = index || 0 30 let data = list[i]; 31 if(data !== undefined) { 32 node = new TreeNode(data); 33 node.leftChildren = createBinaryTree(list, i * 2 + 1); 34 node.rightChildren = createBinaryTree(list, i * 2 + 2) 35 } 36 return node 37 } 38 39 40 /** 41 * @param {(TreeNodeType | null)} node 42 * @description 二叉树的前序遍历 43 */ 44 function preOrderTraversal(node: TreeNodeType | null){ 45 if(node === null){ 46 return 47 } 48 console.log(node.data); 49 preOrderTraversal(node.leftChildren); 50 preOrderTraversal(node.rightChildren) 51 } 52 53 54 /** 55 * @param {(TreeNodeType|null)} node 56 * @description 二叉树的中序遍历 57 */ 58 function inOrderTraversal(node: TreeNodeType | null){ 59 if(node === null){ 60 return 61 } 62 63 64 inOrderTraversal(node.leftChildren); 65 console.log(node.data); 66 inOrderTraversal(node.rightChildren); 67 68 69 } 70 71 72 /** 73 * @param {(TreeNodeType | null)} node 74 * @description 二叉树后序遍历 75 */ 76 function postOrderTraversal(node: TreeNodeType | null){ 77 if(node === null){ 78 return 79 } 80 81 82 postOrderTraversal(node.leftChildren); 83 postOrderTraversal(node.rightChildren); 84 console.log(node.data); 85 } 86 87 88 89 90 function main(){ 91 const a = createBinaryTree([1,2,3,4,5,6]); 92 console.log('前序遍历'); 93 preOrderTraversal(a); 94 console.log('中序遍历'); 95 inOrderTraversal(a) 96 console.log('后序遍历'); 97 postOrderTraversal(a); 98 console.log('栈实现前序遍历'); 99 preOrderTraversalByStack(a); 100 console.log('广度-层序遍历') 101 levelOrderTraversal(a) 102 } 103 104 105 main() 106
这里改了一下原书中的构建二叉树实现
栈实现
绝大多数可以使用递归解决的问题，其实都可以使用另一种数据结构来解决，这种数据结构就是栈，因为递归和栈都具有回溯的特性,
下边以二叉树的前序遍历为例子，看一下具体实现过程：
1. 首先遍历二叉树的根节点 1 ， 放入栈中
2. 遍历根节点 1，的左孩子节点 2，放入栈中
3. 遍历节点 2 的左孩子，节点 4 放入栈中
4. 节点 4 既没有左孩子，也没有右孩子，此时需要回溯到节点 2， 即让旧的栈顶元素 4 出栈，就可以重新访问节点 2，得到节点 2 的右孩子，节点 5，此时节点 节点 2，已经没有价值了(已经访问过 左孩子 和 右孩子了)，节点 2 出栈，节点 5 入栈
5. 节点 5 既没有左孩子，也没有右孩子，我们需要再次回溯，一直回溯到节点 1 ，所以，让节点 5 出栈，根节点 1 的右孩子是节点 3，则节点 1 出栈，节点 3 入栈
6. 节点 3 没有左孩子，只有右孩子 节点 6 ， 则节点 3 出栈，节点 6 入栈
7. 节点 6 既没有左孩子，也没有右孩子，则节点 6出栈，此时栈为空，遍历结束
代码实现如下
1 /** 2 * @param {TreeNode} node 3 * @description 栈实现前序遍历 4 */ 5 function preOrderTraversalByStack(node:TreeNodeType|null) { 6 if(node === null){ 7 return 8 } 9 const stackList:Array<TreeNode> = []; 10 11 12 let treeNode:TreeNodeType|null = node; 13 while(treeNode !== null || stackList.length) { 14 while(treeNode !== null) { 15 console.log(treeNode.data) 16 stackList.push(treeNode); 17 treeNode = treeNode.leftChildren 18 } 19 20 21 if(stackList.length) { 22 treeNode = <TreeNodeType>stackList.pop(); 23 treeNode = treeNode.rightChildren 24 } 25 } 26 } 27
广度优先遍历
如果说深度优先遍历是在一个方向上"一头扎到低"，那么广度优先遍历则恰好相反：在各个方向上走出第一步，再在各个方向上走出第二步，.... 一直到各个方向都走完，
下边通过二叉树的层序遍历演示广度优先遍历
层序遍历，顾名思义，就是二叉树按照根节点到叶子节点的层级关系，一层一层横向遍历各个节点
上图是一个二叉树的层序遍历节点输出顺序，实现这样的遍历方式，需要借助一个数据结构：队列，详细步骤如下
1. 根节点 1 进入队列
2. 节点 1 出队，输出节点 1 ，并得到节点 1 的左孩子 节点 2 和右孩子节点 3，让节点 2 和节点 3 入队
3. 节点 2 出队，并得到节点 2 的左孩子 节点 4，和右孩子 节点 5，让节点 4 和节点 5 入队
4. 节点 3 出队，并得到 节点 3 的右孩子 节点 6，让节点 6 入队
5. 节点 4、 5、6 依次出队，由于都没有孩子节点，所以没有入队操作
广度优先遍历代码实现
1 /** 2 * @param {TreeNode} node 3 * @description 层序遍历-广度优先遍历 4 */ 5 function levelOrderTraversal(node:TreeNodeType|null) { 6 if(node === null){ 7 return 8 } 9 let queue:Array<TreeNode> = []; 10 queue.push(node) 11 while(queue.length) { 12 let outNode = <TreeNodeType>queue.shift(); 13 console.log(outNode.data) 14 if(outNode.leftChildren) { 15 queue.push(outNode.leftChildren) 16 } 17 if(outNode.rightChildren) { 18 queue.push(outNode.rightChildren) 19 } 20 } 21 } 22
摘要总结自: 漫画算法 小灰的算法之旅