7-二叉树（第10章）
树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式存储数据 。本章将研究一种特殊的树： 二叉查找树。
7.1 什么是树
树是一种数据结构，由一组以边线连接的节点组成。以下就是一颗普通的树
树的节点：一棵树最上面的节点称为根节点，如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子节点。一个节点可以有 0 个、 1 个或多个子节点。没有任何子节点的节点称为叶子节点。
树的遍历：沿着树的一组特定的边，可以从一个节点走到另外一个与它不直接相连的节点。从一个节点到另一个节点的这一组边称为路径，在图中用虚线表示。以某种特定顺序访问树中所有的节点称为树的遍历
树的深度：树可以分为几个层次，根节点是第 0 层，它的子节点是第 1 层，子节点的子节点是第 2层，以此类推。树中任何一层的节点可以都看做是子树的根，该子树包含根节点的子节点，子节点的子节点等。我们定义树的层数就是树的深度
7.2 二叉树
首先我们要了解下什么是二叉树，二叉树是一种特殊的树，它的子节点个数不超过两个。二叉查找树是在二叉树的基础上对树的结构进行了进一步的约束。
二叉查找树又名二叉排序树，有时候也叫二叉搜索树。它具有以下特征：
- 若左子树不为空，则左子树上所有的结点的值均小于它根节点的值
- 若右子树不为空，那么右子树上所有节点的值均大于它根节点的值
- 左右子树也分别为二叉查找树
- 没有键值相等的节点
7.3 实现一个二叉树
二叉树都是由节点组成的，所以我们要实现二叉树必须要先实现节点，一个节点通常包含三部分——数据、左子节点、右子节点。因此我们可以定义这样的一个node对象来代表我们的节点。
class Node { constructor(data, left, right) { this.data = data this.left = left this.right = right }}复制代码 Node 对象既保存数据，也保存和其他节点的链接
现在我们可以创建一个类，用来表示二叉查找树，我们让类只包含一个数据成员：一个表示二叉查找树根节点的 Node 对象。该类的构造函数将根节点初始化为 null，以此创建一个空节点。
接下来我们来实现一个insert方法，用来向树中插入新的节点。实现这个方法的算法如下：
- 如果跟节点为null,则把根节点设置为要插入的节点
- 如果待插入节点保存的数据小于当前节点，则获取当前节点的左节点，如果左节点存在则与待插入的节点进行比较，重复步骤2。如果当前节点的左节点不存在，则直接把待插入的节点设置为当前节点的左节点
- 如果待插入节点保存的数据大于当前节点，则获取当前节点的右节点，如果右节点存在则与待插入的节点进行比较，重复步骤2。如果当前节点的右节点不存在，则直接把待插入的节点设置为当前节点的右节点
实现二叉树
class BST { constructor() { this.root = null } insert(data) { let n = new Node(data, null, null) if (this.root === null) { this.root = n } else { var current = this.root while (true) { if (n.data < current.data) { if (current.left === null) { current.left = n break } current = current.left } else { if (current.right === null) { current.right = n break } current = current.right } } } }}复制代码 *验证二叉树
let bst = new BST()bst.insert(8)bst.insert(3)bst.insert(6)bst.insert(4)bst.insert(9)bst.insert(11)bst.insert(2)bst.insert(5)bst.insert(7)console.log('bst:',bst)复制代码 真实的打印结果很难显示在博客里，画成图的话如下：
实现是正确的，说明我们的二叉树程序没有问题
7.4 二叉树的遍历
二叉树遍历常用的有以下三种。
- 前序遍历：先访问根->遍历左子树->遍历右子树
- 中序遍历：遍历左子树->访问根->遍历右子树
- 后序遍历：遍历左子树->遍历右子树->访问根
遍历的前中后顺序其实是指访问根节点的顺序
前序遍历：
// 前序遍历 preOrder(node) { if (node != null) { console.log(node.data) this.preOrder(node.left) this.preOrder(node.right) } }复制代码 中序遍历：
// 中序遍历 inOrder(node) { if (node != null) { this.inOrder(node.left) console.log(node.data) this.inOrder(node.right) } }复制代码 后序遍历
// 后序遍历 postOrder(node) { if (node !== null) { this.postOrder(node.left) this.postOrder(node.right) console.log(node.data) } }复制代码 **遍历的方法使用的是递归，非常绕，需要多理解理解
完整代码如下
class Node { constructor(data, left, right) { this.data = data this.left = left this.right = right }}class BST { constructor() { this.root = null } insert(data) { let n = new Node(data, null, null) if (this.root === null) { this.root = n } else { var current = this.root while (true) { if (n.data < current.data) { if (current.left === null) { current.left = n break } current = current.left } else { if (current.right === null) { current.right = n break } current = current.right } } } } // 前序遍历 preOrder(node) { if (node != null) { console.log(node.data) this.preOrder(node.left) this.preOrder(node.right) } } // 中序遍历 inOrder(node) { if (node != null) { this.inOrder(node.left) console.log(node.data) this.inOrder(node.right) } } // 后序遍历 postOrder(node) { if (node !== null) { this.postOrder(node.left) this.postOrder(node.right) console.log(node.data) } }}复制代码 测试：
let bst = new BST()bst.insert(8)bst.insert(3)bst.insert(6)bst.insert(4)bst.insert(9)bst.insert(11)bst.insert(2)bst.insert(5)bst.insert(7)bst.preOrder(bst.root) // 8 3 2 6 4 5 7 9 11bst.inOrder(bst.root) // 2 3 4 5 6 7 8 9 11bst.postOrder(bst.root) // 2 5 4 7 6 3 11 9 8复制代码
测试没有，说明我们的遍历是正确的。
7.5 二叉树查找
-
查找给定的值
-
查找最大值
-
查找最小值
// 查找最大是getMax() { let node = this.root while (true) { if (node.right === null) { console.log(node.data) break } node = node.right }}// 查找最小值getMin() { let node = this.root while (true) { if (node.left === null) { console.log(node.data) break } node = node.left }}getSomeNum(num) { let node = this.root while (node) { if (num < node.data) { node = node.left } else if (num > node.data) { node = node.right } else if (num === node.data) { console.log('node.data:', node.data) break } }}复制代码
测试
bst.getMax() // 11bst.getMin() // 2bst.getSomeNum(9) // node.data: 9bst.getSomeNum(1) // 复制代码
7.6 从二叉树上删除节点
在二叉树上删除节点会比较复杂，如果要删除的节点没有子节点还好，如果要删除的节点有一个节点或者两个节点，都要考虑到这些节点的处理情况，这时就比较难以处理。
- 如果待删除节点是叶子节点（没有子节点的节点），那么只需要将从父节点指向它的链接改为 null
- 如果待删除节点只包含一个子节点，那么原本指向它的节点就得做些调整，使其指向它的子节点。
- 最后，如果待删除节点包含两个子节点，正确的做法有两种：要么查找待删除节点左子树上的最大值，要么查找其右子树上的最小值。这里我们选择后一种方式。
程序如下：
getSmallest(ndoe) { while (node.left !== null) { node = node.left } return node } remove(data) { this.root = this.removeNode(this.root, data) } // 如果要删除的节点是当前节点，则返回null，否则返回原节点，并按照规则，递归查找下一个节点是不是目标节点 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 } // 有两个字节点 let tempNode = this.getSmallest(node.right) node.data = tempNode.data node.right = this.removeNode(node.right, tempNode.data) return node } else if (data < node.data) { node.left = this.removeNode(node.left, data) return node } else { node.right = this.removeNode(node.right, data) return node } }复制代码 测试
class Node { constructor(data, left, right) { this.data = data this.left = left this.right = right }}class BST { constructor() { this.root = null } insert(data) { let n = new Node(data, null, null) if (this.root === null) { this.root = n } else { var current = this.root while (true) { if (n.data < current.data) { if (current.left === null) { current.left = n break } current = current.left } else { if (current.right === null) { current.right = n break } current = current.right } } } } // 前序遍历 preOrder(node) { if (node != null) { console.log(node.data) this.preOrder(node.left) this.preOrder(node.right) } } // 中序遍历 inOrder(node) { if (node != null) { this.inOrder(node.left) console.log(node.data) this.inOrder(node.right) } } // 后序遍历 postOrder(node) { if (node !== null) { this.postOrder(node.left) this.postOrder(node.right) console.log(node.data) } } // 查找最大是 getMax() { let node = this.root while (true) { if (node.right === null) { console.log(node.data) break } node = node.right } } // 查找最小值 getMin() { let node = this.root while (true) { if (node.left === null) { console.log(node.data) break } node = node.left } } getSomeNum(num) { let node = this.root while (node) { if (num < node.data) { node = node.left } else if (num > node.data) { node = node.right } else if (num === node.data) { console.log('node.data:', node.data) break } } } getSmallest(ndoe) { while (node.left !== null) { node = node.left } return node } remove(data) { this.root = this.removeNode(this.root, data) } // 如果要删除的节点是当前节点，则返回null，否则返回原节点，并按照规则，递归查找下一个节点是不是目标节点 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 } // 有两个字节点 let tempNode = this.getSmallest(node.right) node.data = tempNode.data node.right = this.removeNode(node.right, tempNode.data) return node } else if (data < node.data) { node.left = this.removeNode(node.left, data) return node } else { node.right = this.removeNode(node.right, data) return node } }}let bst = new BST()bst.insert(8)bst.insert(3)bst.insert(6)bst.insert(4)bst.insert(9)bst.insert(11)bst.insert(2)bst.insert(5)bst.insert(7)bst.remove(9)bst.inOrder(bst.root)// 打印结果234567811复制代码 从打印结果看，需要删除的数据被删除了，bst能正常遍历，中序遍历顺序也正确，说明我们删除程序没有问题。自此关于二叉树的知识点就基本讲完了。有实际情况时根据实际情况再调整。