一、什么是二叉树
二叉树是指每个节点最多含有两个子树的树结构。
特点：
- 所有节点最多拥有两个子节点，即度不大于2
- 左子树的键值小于根的键值，右子树的键值大于根的键值。
二、二叉树结构
每一个结点（除叶子结点外）都有左子树和右子树.
// 结点
var Node = function(key) {
this.key = key;
this.left = null;
this.right = null;
}
三、遍历二叉树
- 先序遍历 （根 => 左结点 => 右结点）
- 中序遍历 （左结点 => 根 => 右结点）
- 后序遍历 （左结点 => 右结点 => 根）
根据上图：
- 先序遍历：ADBEFGC
- 中序遍历：DBEAFGC
- 后序遍历：DEBGFCA
代码封装:
// 中序遍历
function(node) {
if (node !== null) { // 判断参数（左孩子、右孩子、根结点）的值是否不为空
//访问左子树
inOrderTraverseNode(node.left);
console.log(node.key)
inOrderTraverseNode(node.right);
}
//如果为空，程序回溯，将结点的值输出
}
// 前序遍历
function(node) {
if (node !== null) { // 判断参数（左孩子、右孩子、根结点）的值是否不为空
console.log(node.key)
//访问左子树
preOrderTraverseNode(node.left);
preOrderTraverseNode(node.right);
}
//如果为空，程序回溯，将结点的值输出
}
// 后序遍历
function(node) {
if (node !== null) { // 判断参数（左孩子、右孩子、根结点）的值是否不为空
//访问左子树
postOrderTraverseNode(node.left);
postOrderTraverseNode(node.right);
console.log(node.key);
}
//如果为空，程序回溯，将结点的值输出
}
四、结点插入二叉树
根据二叉树的特点：左子树的键值小于根的键值，右子树的键值大于根的键值
比如：687234501这串数字插入到二叉树中
代码封装：
// 插入到二叉树
var insertNode = function(node, newNode) {
if (newNode.key < node.key) { //左子树
if (node.left === null) { // 左孩子为空
node.left = newNode
} else {
// 再次与左孩子的左孩子的值进行比较
insertNode(node.left, newNode)
}
} else { //右子树
if (node.right === null) {
node.right = newNode
} else {
insertNode(node.right, newNode)
}
}
};
// 创建结点及判断该结点是否为根结点并插入到二叉树中
this.insert = function(key) {
var newNode = new Node(key)
if (root === null) { // 二叉树中根节点为空
root = newNode;
} else {
insertNode(root, newNode)
}
};
五、寻找二叉树的最大最小值
根据二叉树的特点：左子树的键值小于根的键值，右子树的键值大于根的键值
得：
- 最小值是二叉树最左边的叶子结点。
- 最大值是二叉树最右边的叶子结点。
代码封装：
// 最小值
function(node) {
if (node) {
while (node && node.left !== null) {
node = node.left
}
return node.key
}
return null
}
// 最大值
function(node) {
if (node) {
while (node && node.right !== null) {
node = node.right
}
return node.key
}
return null
}
六、寻找二叉树的特定值
根据二叉树的特点：左子树的键值小于根的键值，右子树的键值大于根的键值
得：
- 如果该值小于该结点则向左子树遍历。
- 如果该值大于该结点则向右子树遍历。
- 遍历到叶结点，还为找到该值，则该树没有改特定值。
代码封装：
var searchNode = function(node, key) {
if (node === null) {
return false;
}
if (key < node.key) {
return searchNode(node.left, key)
} else if (key > node.key) {
return searchNode(node.right, key)
} else {
return true;
}
}
七、删除结点并保持二叉树结构不变
- 情况一：删除的结点是叶子结点：直接删除。
- 情况二：该结点小于(大于)当前遍历结点的值，则继续遍历左子树(右子树)。
- 情况三：结点刚好等于当前遍历结点值，此时还有分四种情况进行讨论（有左右子树，没有左子树，没有右子树，没有左右子树）
- 没有左右子树情况下，直接删除（node =null return node），即第一种情况。
- 没有左子树 将 删除结点的右子树 赋值给 上层结点 的左子树或者右子树。
- 没有右子树 将 删除结点的左子树 赋值给 上层结点 的左子树或者右子树。
- 有左右子树 （1）在该结点的右子树中查找到最小值结点，（2）更新要删除结点的值为最小值，（3）删除最小值结点
代码封装：
//找到最小值的结点
function(node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}
return node
}
return null
}
//删除结点
function(node, key) {
if (node === null) {
return null;
}
if (key < node.key) {
node.left = removeNode(node.left, key)
return node;
} else if (key > node.key) {
node.right = removeNode(node.right, key)
} else { //相等
//没有左右子树，直接node 赋值为 null 返回null通过程序的回溯将node.left 或 node.right 赋值为 null
if (node.left === null && node.right === null) {
node = null;
return node;
}
//没有左子树，将 删除结点的右子树 赋值给 上层结点 的左子树或者右子树
if (node.left === null) {
node = node.right;
return node;
}
//没有右子树，将 删除结点的左子树 赋值给 上层结点 的左子树或者右子树
if (node.right === null) {
node = node.left;
return node;
}
//结点包含左子树和右子树
//在该结点的右子树中查找到最小值结点
var aux = findMinNode(node.right);
//更新要删除结点的值为最小值
node.key = aux.key;
//删除最小值结点
node.right = removeNode(node.right, aux.key);
return node;
}
}
