一、二叉树的基本概念
从逻辑结构角度来看，前面说的链表、栈、队列都是线性结构；而今天要了解的“二叉树”属于树形结构。
1.1 多叉树的基本概念，以上图中“多叉树”为例说明
节点：多叉树中的每一个点都叫节点；其中最上面的那个节点叫“根节点”；
父节点：节点1是节点2/3/4/5/6的父节点，然后节点2/3/4/5/6是节点1的子节点；节点2/3/4/5/6又是互为兄弟节点，因为它们有父节点为同一个节点；
空树：一个没有任何节点的树叫空树；一棵树可以只有一个节点，也就是只有根节点；
子树：子节点及子节点的后台节点形成的一个节点集合叫子树；对于只有两个子节点的节点，其左边的子节点叫左子树，右边的叫右子树；
叶子节点（leaf）：子树为0的节点；其他子树不为0的节点叫“非叶子节点”；
层数（level）：根节点在第1层，根节点的子节点在第2层，以此类推（有些说法也从第0层开始结算）；
节点的深度(depth)：从根节点到当前节点的唯一路径上的节点总数；
节点的高度(height)：从当前节点到最远叶子节点的路径上的节点总数；
树的深度：所有节点深度中的最大值；
树的高度：所以节点高度中的最大值；数的深度等于数的高度
有序树：树中任意节点的子节点之间有顺序关系；
无序树：树中任意节点的子节点之间没有顺序关系，也叫“*树”；
森林：由n(n >= 0) 颗不相交的树组成的集合；
1.2 二叉树的特点
- 每个节点的度最大为2(最多拥有2颗子树)；
- 左子树和右子树是有顺序的。即使某节点只有一颗子树，也要区分左右子树；
- 非空二叉树的第i层，最多有2^(i-1)个节点（i >= 1)
- 在高度为h的二叉树上最多有2^h - 1个节点（h >= 1);
- 对于任何一颗非空二叉树，如果叶子节点个数为n0, 度为2的节点个数为n2, 则有n0 = n2 + 1。（这个好理解，假如这个二叉树除了第一级节点有2个子节点，后面的节点都是只有一个子节点，则不管这颗二叉树如何往下延伸，永远度为2的节点个数是1个，叶子节点为2个；然后如果在这个二叉树的中间节点，每加一个节点，相当于度为2的节点加一个，叶子节点也加一个，则度为2的节点和叶子节点的增加是同步同数量的，所以对于二叉树，叶子节点个数 = 度为2的节点个数 + 1 公式是永远成立的）
- 假设度为1的节点个数为n1, 那么二叉树的节点总数 n = n0 + n1 + n2。则二叉树的边数T = n1 + 2 * n2 = n -1 = n0 + n1 + n2 -1 --> n2 + 1 = n0
1.3 真二叉树/满二叉树/完全二叉树
- 真二叉树：所有节点的度都要么为2，要么为0；
- 满二叉树：所有节点的度都要么为2，要么为0，且所有的叶子节点都在最后一层；
- 假设满二叉树的高度为h (h>=1)，那么第i层的节点数量：2^(i-1), 叶子节点数量：2(^h-1), 总节点数量n = 2^h -1 = 2^0 + 2^1 + 2^2 + ... + 2^(h-1)
- 等比数列公式：a1=1, 公比q=2, 则an = a1*q^(n-1)=2^(n-1), 前n项之和Sn = a1+a2+...+an = 2^0 + 2^1 + 2^2 + ... + 2^(n-1) = a1(1-q^n)/(1-q)=2^n-1
- 在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多；
- 满二叉树一定是真二叉树，真二叉树不一定是满二叉树；
- 完全二叉树：叶子节点只会出现在最后两层，且最后一层的叶子节点都靠左对齐；
- 完全二叉树从根节点到倒数第二层是一颗满二叉树；满二叉一定是完全二叉树，完全二叉树不一定是满二叉树；
- 度为1的节点只有左子树；度为1的节点要么是1个，要么是0个；
- 假设完全二叉树的高度为h(h>=1), 那么至少有2^(h-1) 个节点(2^0 + 2^1 + 2^2 + ... + 2^(h-2) + 1), 最多有2^h - 1个节点(2^0 + 2^1 + 2^2 + ...+ 2^(h-1), 满二叉树)；总节点数量为n, 则有2^(h-1) <= n < 2^h --> h-1 <= log(2)(n) < h --> h = floor(log(2)(n)) + 1 (floor是向下取整，ceiling是向上取整)
- 一颗有n个节点的完全二叉树(n > 0），从上到下，从左到右对节点从1开始进行编号，对任意第i个节点
- 如果i = 1, 它是根节点
- 如果i > 1, 它的父节点编号为floor(i/2)
- 如果2i <= n, 它的左子节点编号为2i
- 如果2i > n, 它无左子节点
- 如果2i + 1 <= n, 它的右子节点编号为2i + 1
- 如果2i + 1 > n , 它无右子节点
面试题：如果一颗完全二叉树有768个节点，求叶子节点的个数？
分析：假设叶子节点个数为n0，度为1的节点个数为n1，度为2的节点个数为n2。
则总节点个数n = n0 + n1 + n2，而且n0 = n2 + 1 ;
则n = 2n0 + n1 -1
根据完全二叉树的定义我们知道，n1要么为0，要么为1：
当n1为1时， n = 2n0, n必然为偶数。叶子节点个数n0 = n / 2，非叶子节点个数 n1 + n2 = n / 2 ；
当n1为0，n = 2n0 - 1，n必然为奇数。叶子节点个数n0 = (n + 1) / 2， 非叶子节点个数 n1 + n2 = (n - 1) / 2
因此可以判断出来当这个完全二叉树有768个节点时，它的叶子节点个数为：384
二、二叉查找树
二叉查找树是一种特殊的二叉树，较小的值保存在左节点中，较大的值保存在右节点中。这一特性使得查找的效率很高，对于数值型和非数值型的数据，如单词和字符串，都是如此。
2.1 二叉查找树的插入逻辑
2.1.1 设根节点为当前节点
2.1.2 如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点；反之，执行第2.1.4步
2.1.3 如果当前节点的左节点为null, 就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环
2.1.4 设新的当前节点为原节点的右节点
2.1.5 如果当前节点的右节点为null, 就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环
//插入元素
function insertBST(element){
var node = new Node(element, null, null); //根节点判断
if (root == null){
root = node;
}
else{ //非根节点
var current = root;
while(true){
if (element < current.element){ //往左节点方向放
if (current.left == null){
current.left = node;
break;
}
current = current.left;
}
else if (element > current.element){ //往右节点方向放
if (current.right == null){
current.right = node;
break;
}
current = current.right;
}
else { //相等，替换
current.element = element;
return;
}
}
}
size++;
}
2.2 二叉查找树的遍历，遍历有三种方式：中序、前序、后序
中序指以升序的方式遍历所有节点；前序是指先访问根节点，再以同样的方式访问左子树和右子树；后序指的是先访问叶子节点，再从左子树到右子树，最后到根节点。
先看个效果图
遍历走势分析图：
遍历代码：
//二叉树中序遍历：以升序方式访问二叉树中所有节点
function inOrder(){
return inOrderByNode(root);
}
function inOrderByNode(node){
if (node){
var str = "";
str += inOrderByNode(node.left);
str += node.element + ", ";
str += inOrderByNode(node.right);
return str;
}
return "";
} //前序遍历：先访问根节点，再访问左子树和右子树
function preOrder(){
return preOrderByNode(root);
}
function preOrderByNode(node){
if (node){
var str = '';
str += node.element + ", "; //先访问根节点
str += preOrderByNode(node.left); //再访问左子树
str += preOrderByNode(node.right); //再访问右子树
return str;
}
return "";
} //后序遍历：先访问叶子节点，再左子树，再右子树，再到根节点
function postOrder(){
return postOrderByNode(root);
}
function postOrderByNode(node){
if (node){
var str = "";
str += postOrderByNode(node.left);
str += postOrderByNode(node.right);
str += node.element + ", ";
return str;
}
return "";
}
四则运算的表达式可以分为三种：
- 前缀表达式（prefix expression），又称波兰表达式
- 中缀表达式（infix expression）
- 后缀表达式（postfix expression），又称为逆波兰式表达式
如果将表达式的操作作为叶子节点，运算符作为父节点（假设只有四则运算），这些节点刚好可以组成一颗二叉树。
比如表达式：A / B + C * D - E ，如果对这颗二叉树进行遍历
- 前序遍历：- + / A B * C D E ，刚好就是前缀表达式（波兰表达式）
- 中序遍历：A / B + C * D - E，刚好就是中缀表达式
- 后序遍历：A B / C D * + E -，刚好就是后缀表达式（逆波兰表达式）
2.3 查找二叉查找树的最大值、最小值、是否存在某个值
最大值：因为较大的值都是在右子树上，则最大值一定是在右子树的最后一个节点上；
最小值：较小的值都是在左子树上，则最小值一定在左子树的最后一个节点上；
是否存在某个值，则是遍历查找
//查找最小值：因为较小的值都在左边，所以最小值一定是左子树的最后一个节点
function getMin(){
var minNode = getMinNode(root);
if (minNode) {
return minNode.element;
}
return null;
}
//查找最小节点
function getMinNode(node){
var current = node;
while(current){
if (current.left == null){
return current;
}
current = current.left;
}
return null;
} //查找最大值：因为较大的值都在右边，所以最大值一定是在右子树的最后一个节点
function getMax(){
var maxNode = getMaxNode(root);
if (maxNode){
return maxNode.element;
}
return null;
}
//查找最大节点
function getMaxNode(node){
var current = node;
while(current){
if (current.right == null){
return current;
}
current = current.right;
}
return null;
} //查找指定值，是否存在这个元素
function isExist(element){
var current = root;
while(current){
if (element < current.element){ //左子树寻找
current = current.left;
}
else if (element > current.element){ //右子树寻找
current = current.right;
}
else{ //存在
return true;
}
}
return false;
}
2.4 删除二叉查找树中的指定元素
从二叉查找树上删除节点的操作最复杂，其复杂程度取决于删除哪个节点。如果删除没有子节点 的节点，那么非常简单。如果节点只有一个子节点，不管是左子节点还是右子节点，就变 得稍微有点复杂了。删除包含两个子节点的节点最复杂。
//删除元素
function remove(element){
root = removeNode(root, element);
}
function removeNode(node, element){
if (node == null) {
return null;
} if (node.element == element){
size--;
//node没有左子树
if (node.left == null){
return node.right;
}
else if (node.right == null){ //node没有右子树
return node.left;
}
/**
* node有左子树和右子树，这个时候要找出最接近node节点值的节点
* 1、如果找出比node节点的element稍大的节点，则从node右节点的最小节点
* 2、如果找出比node节点的element稍小的节点，则从node左节点的最大节点
*/
//第一种方式,找出比node的element稍微大点的节点
var minNode = getMinNode(node.right);
node.element = minNode.element;
node.right = removeNode(node.right, minNode.element); // //第二种方式, 找出比node的element稍微小点的节点
// var maxNode = getMaxNode(node.left);
// node.element = maxNode.element;
// node.left = removeNode(node.left, maxNode.element); return node;
}
else if(element < node.element){ //往左子树方向继续找
node.left = removeNode(node.left, element);
return node;
}
else{
//往右子树方向继续找
node.right = removeNode(node.right, element);
return node;
}
}