前言：
这里我们来了解 “ 树 ” 这种常见的数据结构。在我们有数组，链表，哈希表等后，为什么会产生树这种数据结构呢 ？
- 数组的优点 ：数组的主要优点是根据下标值访问效率会高很多。
- 数组的缺点 ：在根据元素查找对应的位置时，需要先对数组进行排序，生成有序数组，才能提高查找效率（比较好的方式就是，先对数组进行排序，在进行二分查找。）。另外数组在插入和删除操作时，需要大量的位移操作，效率低。
- 链表优点 ：链表的插入和删除效率都很高。
- 链表缺点 ：查找的效率很低，需要从头开始已次访问链表中的每个数据项，直到找到。
- 哈希表的优点 ：哈希表在插入，查询，删除效率都是非常高。
- 哈希表的缺点 ：空间利用率不高，底层使用的是数组，并且某些单元是没有被利用的。哈希表中的元素是无序的，不能按照固定的顺序来遍历哈希表中的元素。不能开苏找出哈希表中的最大值或者最小值这些特殊的值。
- 树的优点 ：在 插入，查询，删除效率都是非常高。空间利用率高，树中的元素是有序的，能按照固定的顺序来遍历树中的元素。能开找出树中的最大值或者最小值这些特殊的值 。树是非线性结构，可以表示一对多的关系。
- 什么是树 ？
树：n(n>=0) 个节点构成的有限集合。当 n=0 时，称为空树。对于任意一颗非空树（n>0）都具备以下性质：树中有一个称为根的节点，用r表示。其余节点可分为m(m>0)个互不相交的有限集，每个集合又是一棵树，称为原树的子树。
- 树相关的术语 ？
- 节点的度：节点的子树个数。
- 树的度：树的所有节点中最大的度数。
- 叶节点：度为 0 的节点（也称为叶子节点）。
- 父节点：有子树的节点是其子树的根节点的父节点。
- 子节点：若 A 节点是 B 节点的父节点，则称 B 节点是 A 节点的子节点，子节点也称孩子节点。
- 兄弟节点：具有同一父节点的各节点彼此是兄弟节点。
- 路径和路径长度：从节点 n1 到 nk 的路径。路径所包含边的个数为路径的长度。
- 节点的层次：规定根节点在 1 层，其他任一节点的层数是其父节点的层数 +1。
- 根的深度：树中所有的最大层次是这棵树的深度。
- 树的遍历方式 ？
- 先序遍历：1，访问 根节点；2，先序遍历其 左子树；3，先序遍历其 右子树。
- 中序遍历：1，中序遍历其 左子树；2，访问 根节点；3，中序遍历其 右子树。
- 后序遍历：1，中序遍历其 左子树；2，中序遍历其 右子树。3，访问 根节点。
- 层序遍历：一层一层遍历，可以使用队列完成。
- 什么是二叉树 ？
二叉树 : 如果 树中每个节点最多只能有两个子节点，这样的树就成为二叉树。二叉树可以为空，也就是没有节点。若不为空，则它是由根节点和左子树 TL，右子树 TR 两个不相交的二叉树组成。(任何一个树，最终都可以转换为二叉树。)
- 二叉树重要特性 ？
- 一个二叉树 第 i 层的最大节点数 为：2^(i-1),i>=1 。
- 深度为 k 的二叉树有最大节点总数：2^k-1,k>=1 。
- 对任何非空二叉树 T ，若 n1 表示 叶子节点个数；n2 是 度为 2 的非叶子节点个数，则存在 n1=n2+1 的关系 。
- 特殊的二叉树 ？
- 完美二叉树（满二叉树）：除了最下一层的叶节点外，每层节点都有2个子节点。
- 完全二叉树：除二叉树的最后一层外，其他各层的节点数都达到最大个数。且 最后一层从左到右的叶节点连续存在，只缺右侧若干节点，完美二叉树（满二叉树）是特殊的完全二叉树。
- 二叉搜索树（BST）：也称二叉排序树或二叉查找树。二叉搜索树是一颗二叉树，可以为空。如果不为空，需要满足以下性质：非空左子树的所有键值小于其根节点的键值。非空右子树的所有键值大于其根节点的键值。左右子树本身也都是二叉搜索树，二叉搜索树最大特点，查找速度高。
【注意】：二叉树的常见存储方法为，数组和链表，常见的方式还是使用链表存储每一个节点都封装成一个 Node, Node 中包含存储的数据，左节点的引用，右节点的引用。
- 二叉搜索树类的封装 ？
function BinarySearchTree() {// 属性，根节点this.root = null;// 内部类：Node节点类function Node(key) {this.key = key;this.left = null;this.right = null;}// 方法// insert(key)：向树中插入一个新的key BinarySearchTree.prototype.insert = function(key) {// 创建新节点var newNode = new Node(key);// 判断根节点是否为空if (this.root == null) {this.root = newNode;} else {this.insertNode(this.root, newNode);}}// insertNode(node, newNode)：插入的递归方法BinarySearchTree.prototype.insertNode = function(node, newNode) {if (newNode.key < node.key) {// 向左查找if (node.left == null) {node.left = newNode;} else {this.insertNode(node.left, newNode);}} else {// 向右查找if (node.right == null) {node.right = newNode;} else {this.insertNode(node.right, newNode);}}}// search(key)：在树中查找一个 key，是否存在BinarySearchTree.prototype.search = function(key) {var node = this.root;while (node) {if (node.key == key) {return true;} else if (node.key < key) {node = node.right;} else {node = node.left;}}return false;}// preOrderTraverse：通过先序遍历遍历树BinarySearchTree.prototype.preOrderTraverse = function(callback) {this.preOrderTraverseNode(this.root, callback);}// preOrderTraverseNode：先序遍历的递归函数BinarySearchTree.prototype.preOrderTraverseNode = function(node, callback) {if (node) {callback(node.key);this.preOrderTraverseNode(node.left, callback);this.preOrderTraverseNode(node.right, callback);}}// inOrderTraverse：通过中序遍历遍历树BinarySearchTree.prototype.inOrderTraverse = function(callback) {this.inOrderTraverseNode(this.root, callback);}// inOrderTraverseNode：中序遍历的递归函数BinarySearchTree.prototype.inOrderTraverseNode = function(node, callback) {if (node) {this.inOrderTraverseNode(node.left, callback);callback(node.key);this.inOrderTraverseNode(node.right, callback);}}// postOrderTraverse：通过后序遍历遍历树BinarySearchTree.prototype.postOrderTraverse = function(callback) {this.postOrderTraverseNode(this.root, callback);}// postOrderTraverseNode：后序遍历的递归函数BinarySearchTree.prototype.postOrderTraverseNode = function(node, callback) {if (node) {this.postOrderTraverseNode(node.left, callback);this.postOrderTraverseNode(node.right, callback);callback(node.key);}}// getRoot()：返回树的根节点BinarySearchTree.prototype.getRoot = function() {return this.root;}// mix()：返回树中最小的keyBinarySearchTree.prototype.mix = function() {var node = this.root;if (this.root == null) {return null;}if (node) {while (node && node.left) {node = node.left;}}return node.key;}// max：返回树中最大的keyBinarySearchTree.prototype.max = function() {var node = this.root;if (this.root == null) {return null;}if (node) {while (node && node.right) {node = node.right;}}return node.key;}// remove(key)：从树中移除某个keyBinarySearchTree.prototype.remove = function(key) {// 先判断是否存在key，如果不存在，则直接return 0if (!this.search(key)) return false;this.removeNode(this.root, key);}BinarySearchTree.prototype.removeNode = function(node, key) {if (node == null)return null;if (node.key > key) {node.left = this.removeNode(node.left, key);} else if (node.key < key) {node.right = this.removeNode(node.right, key);} else { // 找到要删除的节点// 要删除的节点是叶子节点，直接让该节点为nullif (node.left == null && node.right == null) {node = null;}// 要删除的节点有一个子节点，则把要删除的节点替换为它的子节点else if (node.left == null) {node = node.right;} else if (node.right == null) {node = node.left;}// 要删除的节点有两个子节点，这时可以用左子树里的最大节点来替换要删除的节点，也可以用右子树里的最小节点来替换要删除的节点// 这里我采用左子树的最大节点来替换else {// 找到要删除的节点的左子树里最大的值var LeftMax = this.getLeftMax(node.left);// 让要删除的节点的key等于刚才找到的左子树里最大值的key，保证了要删除的节点只改变了key，左右子树不变node.key = LeftMax.key;// 让要删除的节点的左子树里删除它的最大值node.left = this.removeNode(node.left, LeftMax.key);}}return node;}BinarySearchTree.prototype.getLeftMax = function(node) {if (node) {while (node && node.right) {node = node.right;}return node;}return null;}
}- 二叉搜索树类的测试 ？
// 测试：
var bst = new BinarySearchTree();
// 插入数据
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(3);
bst.insert(9);
bst.insert(8);
bst.insert(10);
bst.insert(13);
bst.insert(12);
bst.insert(14);
bst.insert(20);
bst.insert(18);
bst.insert(25);
bst.insert(6);
// 先序遍历
var result = "";
bst.preOrderTraverse(function(key) {result += key + " ";
});
console.log("先序遍历：" + result);// 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
// 中序遍历
result = "";
bst.inOrderTraverse(function(key) {result += key + " ";
});
console.log("中序遍历：" + result);// 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
// 后序遍历：
result = "";
bst.postOrderTraverse(function(key) {result += key + " ";
});
console.log("后序遍历：" + result);// 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11
// 最小值
console.log('min：' + bst.mix(bst.getRoot())); // 2
// 最大值
console.log('max：' + bst.max(bst.getRoot())); // 57
// 查找元素是否存在
var key1 = 18;
var key2 = 99;
console.log(bst.search(key1) ? key1 + ': 该元素存在！' : key1 + ': 该元素不存在！'); // true
console.log(bst.search(key2) ? key2 + ': 该元素存在！' : key2 + ': 该元素不存在！'); // false
// 删除元素
var key3 = 10;
console.log(!bst.remove(key3) ? key3 +': 该元素已删除！' : key3 + ': 该元素不存在！');
// 先序遍历
var result = "";
bst.preOrderTraverse(function(key) {result += key + " ";
});
console.log("先序遍历：" + result);// 9 8 4 2 6 18 10 57