二叉树
二叉树是特殊的树，也是我们平时程序中用的比较多的一种数据结构，它具有以下特点：
- 每个结点最多有两颗子树，结点的度最大为2。
- 左子树和右子树是有顺序的，次序不能颠倒。
- 即使某个结点只有一个子树，也要区分左右子树。
下面是二叉树的数据特性
- 在二叉树的第i（根结点为1层）层上最多有2^(i-1)个结点（i>=1）。
- 高度为k的二叉树，最多有2^k-1个结点（k>=0）。
- 对任何一棵二叉树，如果其叶结点有n个，度为2的非叶子结点有m个，则 n=m+1。
特殊的二叉树及特点
1、斜树
所有的结点都只有左子树（左斜树），或者只有右子树（右斜树）。斜树应用场景较少。
2、满二叉树
所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上。
- 叶子结点只能出现在最下一层。
- 非叶子结点的度一定是2.
- 在同样深度的二叉树中，满二叉树的结点个数最多，叶子结点最多。
3、完全二叉树
对一棵具有n个结点的二叉树按层序排号，如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同，就是完全二叉树。满二叉树必须是完全二叉树，反过来不一定成立。
- 叶子结点只能出现在最底部两层。
- 最底层叶子结点一定集中在左部连续位置。
- 倒数第二层如果有叶子结点，一定出现在右部连续位置。
- 同样数量结点的树，完全（满）二叉树的深度最小。
- 对于有n个结点的完全二叉树，按层次对结点进行编号（从上到下，从左到右），对于任意编号为i的结点：
- 如果i=1，则结点i是二叉树的根
- 如果i>1，则其双亲结点为i/2下取整。
- 如果2i<=n，则结点i的做孩子2i。
- 如果2i>n，则结点i无左孩子。
- 如果2i+1<=n，则结点i的右孩子为2i+1。
- 如果2i+1>n，则结点i无右孩子。
4、二叉排序树
二叉排序树，又称，也叫。
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： (1) 若左子树不为空，则左子树上所有结点的值均小于或等于它的根结点的值。 (2) 若右子树不为空，则右子树上所有结点的值均大于或等于它的根结点的值。 (3) 左、右子树也分别是二叉排序树。(4) 二叉排序树中序遍历结果为递增有序数列。// 树的结点类class Node { constructor(key, leftChild, rightChild) { this.key = key; this.left = leftChild; this.right = rightChild; }}// 二叉排序树类class BinarySortTree { constructor() {} // 创建二叉排序树的数据结构 create(data) { if(!(data instanceof Array) || data.length < 1) { return } var len = data.length; var tree = new Node(data[0], null, null); if(len == 1) { return tree; } for(let i=1; i currentNode.key) { currentNode.right = this.deleteNode(currentNode.right, key); return currentNode; }else { if(!currentNode.left && !currentNode.right) { // 如果是叶子结点 currentNode = null; return currentNode; } if(!currentNode.right) { // 如果只有左子树 currentNode = currentNode.left; return currentNode; }else if(!currentNode.left) { // 如果只有右子树 currentNode = currentNode.right; return currentNode; }else { // 既有左子树又有右子树 var minRightKey = this.findMinNode(currentNode.right); currentNode.key = minRightKey; currentNode.right = this.deleteNode(currentNode.right, minRightKey); return currentNode; } } } // 查找最小结点 findMinNode(rightTree) { if(rightTree) { while(rightTree && rightTree.left) { rightTree = rightTree.left; } return rightTree.key; } return null; }}const arr = [62, 88, 58, 47, 35, 73, 51, 99, 37, 93];var binSrotTree = new BinarySortTree();var bstree = binSrotTree.create(arr);console.log(bstree);var searchResult = binSrotTree.searchNode(bstree, 100);console.log(searchResult); // falsevar newbstree = binSrotTree.deleteNode(bstree, 62);console.log(newbstree);复制代码 5、平衡二叉树
平衡二叉树（Balanced BinaryTree）又被称为AVL树（有别于AVL算法），它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
注意：满二叉树和完全二叉树一定是平衡二叉树
二叉树的存储
1、链表存储（对象）
适用于所有二叉树，详细介绍见 树的存储--孩子兄弟表示法。
2、顺序表存储（数组）
利用平衡二叉树平衡的特性，使用数组来存储完全二叉树，a[n]的左右子节点分别为a[2n+1]，a[2n+2]。
注：数组的下标是从0开始的，二叉树是从1开始的。
二叉树的遍历
1、先序遍历
基本思想：先访问根结点，再先序遍历左子树，最后再先序遍历右子树即根—左—右。
先序遍历JavaScript实现见下面程序。
var sortedArr = [];function preOrder(tree) { if(tree) { sortedArr.push(tree.key); middleOrder(tree.left); middleOrder(tree.right); }}复制代码 2、中序遍历
基本思想：先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树即左—根—右。
中序遍历JavaScript实现见下面程序。
var sortedArr = [];function middleOrder(tree) { if(tree) { middleOrder(tree.left); sortedArr.push(tree.key); middleOrder(tree.right); }}middleOrder(bstree); // bstree为上文中创建的二叉排序树console.log(sortedArr); //[ 35, 37, 47, 51, 58, 62, 73, 88, 93, 99 ]复制代码 3、后序遍历
基本思想：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左—右—根。
后序遍历JavaScript实现见下面程序。
var sortedArr = [];function postOrder(tree) { if(tree) { middleOrder(tree.left); middleOrder(tree.right); sortedArr.push(tree.key); }}复制代码 堆及特点
堆是什么？一般情况下可以把堆认作是一种特殊的完全二叉树。非一般情况下堆是什么？阅读
堆可以分为大根堆和小根堆。 大根堆：所有父结点都比子结点大的完全二叉树。 小根堆：所有父结点都比子结点小的完全二叉树。总结
关于数据结构中二叉树相关的知识点有很多很多，本文提到的二叉树属于二叉树应用中比较常见的几种。还有更多的知识点可以阅读文章中引用的文章。此外，堆排序也是一种比较常见（经典）的排序方式，后序会有专门文章介绍。