二叉树

什么是树？

特点：

树是计算机科学中经常用到的一种数据结构
树是一种非线性的数据结构，以分层的方式存储数据
树被用来存储具有层级关系的数据，比如文件系统中的文件
树还被用来存储有序列表

选择树而不是那些基本的数据结构，是因为在二叉树上进行查找非常快(而在链表上查找则不是这样)，为二叉树添加或删除元素也非常快(而对数组执行添加或删除操作则不是这样)。

定义：

树由一组以边连接的节点组成

其它定义：

一棵树最上面的节点称为根节点，如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子节点。一个节点可以有 0 个、1 个或多个子节点。没有任何子节点的节点称为叶子节点

如下图所示：

沿着一组特定的边，可以从一个节点走到另外一个与它不直接相连的节点。从一个节点到另一个节点的这一组边称为路径，在图中用虚线表示。以某种特定顺序访问树中所有的节点称为树的遍历
树可以分为几个层次，根节点是第 0 层，它的子节点是第 1 层，子节点的子节点是第 2 层，以此类推。树中任何一层的节点可以都看做是子树的根，该子树包含根节点的子节点，子节点的子节点等。树的层数就是树的深度
每个节点都有一个与之相关的值，该值有时被称为键

二叉树是什么？

二叉树是一种特殊的树，它的子节点个数不超过两个,通过将子节点的个数限定为 2，可以写出高效的程序在树中插入、查找和删除数据

一个父节点的两个子节点分别称为左节点和右节点。在一些二叉树的实现中，左节点包含一组特定的值，右节点包含另一组特定的值

二叉查找树是什么？

二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中

实现二叉查找树

二叉查找树由节点组成，所以我们要定义的第一个对象就是 Node，节点

每个节点的键、左节点、右节点定义

function Node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;
 }

function show() {
    return this.data;
}

再创建一个类，用来表示二叉查找树(BST)

让类只包含一个数据成员: 一个表示二叉查找树根节点的 Node 对象。这个类的构造函数将根节点初始化为null，以此创建一个空节点

function BST() {
    this.root = null;
    this.insert = insert;
    this.inOrder = inOrder;
}

insert方法：用来向树中加入新节点

原理：

(1) 设根节点为当前节点。
(2) 如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点;反之，执行第 4 步。
(3) 如果当前节点的左节点为 null，就将新的节点插入这个位置，退出循环;反之，继续执行下一次循环。
(4) 设新的当前节点为原节点的右节点。
(5) 如果当前节点的右节点为 null，就将新的节点插入这个位置，退出循环;反之，继续执行下一次循环。

function insert(data) {
    var n = new Node(data, null, null);
    if (this.root == null) {
       this.root = n;
    } else {
       var current = this.root;
       var parent;
       while (true) {
          parent = current;
          if (data < current.data) {
            current = current.left;
            if (current == null) {
                parent.left = n;
                break; 
            }
          } else {
             current = current.right;
             if (current == null) {
                parent.right = n;
                break; 
            }
          } 
        }
    }
}

有三种遍历 BST 的方式:中序、先序和后序

中序

中序遍历以升序访问树中所有节点，先访问左子树，再访问根节点，最后访问右子树

function inOrder(node) {
    if (!(node == null)) {
       inOrder(node.left);
       document.write(node.show() + " ");
       inOrder(node.right);
    }
}

实例化一个例子：

var nums = new BST();
nums.insert(56);
nums.insert(81);
nums.insert(22);
nums.insert(30);
nums.insert(77);
nums.insert(92);
nums.insert(10);
document.write("Inorder traversal: ");
inOrder(nums.root);

运行结果： 10 22 30 56 77 81 92

先序

先序遍历先访问根节点，然后以同样方式访问左子树和右子树

function preOrder(node) {
    if (!(node == null)) {
       document.write(node.show() + " ");
       preOrder(node.left);
       preOrder(node.right);
    } 
}

var nums = new BST();
nums.insert(50);
nums.insert(70);
nums.insert(10);
nums.insert(15);
nums.insert(60);
nums.insert(5);
nums.insert(80);
document.write("preOrder traversal: ");
preOrder(nums.root);

运行结果：50 10 5 15 70 60 80

inOrder() 和 preOrder() 方法的唯一区别，就是 if 语句中代码的顺序。

(1) 在 inOrder() 方法中，show() 函数像三明治一样夹在两个递归调用之间;
(2) 在 preOrder() 方法中，show() 函数放在两个递归调用之前

后序

后序遍历先访问叶子节点，从左子树到右子树，再到根节点

function postOrder(node) {
    if (!(node == null)) {
       postOrder(node.left);
       postOrder(node.right);
       document.write(node.show() + " ");
    }
}

var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
document.write("postOrder traversal: ");
preOrder(nums.root);

运行结果： 3 22 16 37 99 45 23

在二叉查找树上进行查找

对 BST 通常有下列三种类型的查找: (1) 查找给定值; (2) 查找最小值; (3) 查找最大值。

查找 BST 上的最小值和最大值非常简单。因为较小的值总是在左子节点上，在 BST 上查找最小值，只需要遍历左子树，直到找到最后一个节点

查找最小值

function getMin() {
    var current = this.root;
    while (!(current.left == null)) {
       current = current.left;
    }
    return current.data;
}

查找最大值

function getMax() {
    var current = this.root;
    while (!(current.right == null)) {
       current = current.right;
    }
    return current.data;
}

初始化个例子：

var nums = new BST();
nums.insert(56);
nums.insert(81);
nums.insert(22);
nums.insert(30);
nums.insert(77);
nums.insert(92);
nums.insert(10);

var min = nums.getMin();
document.write("The minimum value of the BST is: " + min);
document.write("--------");
var max = nums.getMax();
document.write("The maximum value of the BST is: " + max);

运行结果：

查找给定值

在 BST 上查找给定值，需要比较该值和当前节点上的值的大小。通过比较，就能确定如果给定值不在当前节点时，该向左遍历还是向右遍历

function find(data) {
     var current = this.root;
     while (current != null) {
         if (current.data == data) {
             return current;
         } else if (data < current.data) {
             current = current.left;
         } else {
             current = current.right;
         }
    }
    return null;
}

如果找到给定值，该方法返回保存该值的节点;如果没找到，该方法返回 null

从二叉查找树上删除节点

从 BST 上删除节点的操作最复杂，其复杂程度取决于删除哪个节点。如果删除没有子节点的节点，那么非常简单。如果节点只有一个子节点，不管是左子节点还是右子节点，就变得稍微有点复杂了。删除包含两个子节点的节点最复杂

原理：

从 BST 中删除节点的第一步是判断当前节点是否包含待删除的数据，如果包含，则删除该节点;如果不包含，则比较当前节点上的数据和待删除的数据。如果待删除数据小于当前节点上的数据，则移至当前节点的左子节点继续比较;如果删除数据大于当前节点上的数据，则移至当前节点的右子节点继续比较。
如果待删除节点是叶子节点(没有子节点的节点)，那么只需要将从父节点指向它的链接指向 null。
如果待删除节点只包含一个子节点，那么原本指向它的节点久得做些调整，使其指向它的子节点。
如果待删除节点包含两个子节点，正确的做法有两种:要么查找待删除节点左子树上的最大值，要么查找其右子树上的最小值。这里选择后一种方式

整个删除过程由两个方法完成。remove() 方法只是简单地接受待删除数据，调用 removeNode()删除它

function remove(data) {
    root = removeNode(this.root, data);
}

function removeNode(node, data) {
    if (node == null) {
       return null;
    }

    if (data == node.data) {
        // 没有子节点的节点
        if (node.left == null && node.right == null) {
           return null;
        }
        // 没有左子节点的节点
        if (node.left == null) {
           return node.right;
        }

        // 没有右子节点的节点
        if (node.right == null) {
           return node.left;
        }

        // 有两个子节点的节点
        var tempNode = getSmallest(node.right);
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode.data); return node;
    } else if (data < node.data) {
       node.left = removeNode(node.left, data);
       return node;
    } else {
       node.right = removeNode(node.right, data);
       return node;
    } 
}