做自己的网站的好处域名查询备案

往期

• 论如何监听一个对象所有属性的变化
• 论如何监听一个对象某个属性的变化

前言

本文分为入门和进阶两部分，建议有经验的读者直接阅读进阶部分。

入门

关于二叉树的概念

先说几个定义，看下面这张图:

橙色的圆代表的是根结点，构造一棵树其实也就是构造一棵树的根结点。橙色边框的圆代表叶子结点(也叫外部结点external node), 它没有子结点。灰色边框的圆代表内部结点，它至少有一个子结点。

值得注意的是，高度和深度都是对于结点而言的，一棵树的高度和深度其实代表的是根结点的高度和深度。

本文定义根结点的深度为0, 叶子结点的高度为0， 根结点的高度等于树中所有结点深度的最大值。(你也可以把高度和深度认为是同一个值，但是本文还是根据国外教材的定义做出了区分)

还有个概念叫做度，代表某个结点子结点的数量，叶子结点的度为0, 对于二叉树而言每个结点的度最大值为2。

有两种典型的二叉树: 满(full)二叉树和完全(complete)二叉树。用定义说有点抽象，看下面的图像, 这就是一棵满二叉树:

这是一棵完全二叉树:

这棵就不是完全二叉树, 把value为K的结点移到虚线位置才是完全二叉树:

创建二叉树

如上文所说，创建二叉树其实也就是构造其根结点,下面是结点的数据结构，记住它, 我们后面会用到。

function Node(val) {this.val = val;this.left = null;this.right = null;
}
复制代码

接下来我们先用层次遍历(level order)生成的数组来创建二叉树。

层次遍历顾名思义就是一层一层去的遍历树的所有结点，比如以下的完全二叉树:

     1/ \2   3/ \ /4  5 6
复制代码

层次遍历得到的数组便为[1, 2, 3, 4, 5, 6]

以下的二叉树:

     1/ \2   3/   /4   5
复制代码

层次遍历得到的数组为[1, 2, 3, 4, null, 5]

如果你以前没有接触过递归，下面的代码理解起来可能会有些许困难(不过没关系，你可以先继续读下去)。核心思想就是先构建好最左边的分支，再去添加剩余的结点。

function buildCompleteTree(arr, i, root) {if (i < arr.length) {root = new Node(arr[i]);// 如果难以理解的话，试试打印i的值 :)root.left = buildCompleteTree(arr, (i * 2) + 1, root.left);root.right = buildCompleteTree(arr, (i * 2) + 2, root.right);}// 创建二叉树其实也就是构造其根结点return root;
}
复制代码

让我们来试一试

const a = [1, 2, 3, 4, 5, 6];
const r = buildCompleteTree(a, 0, new Node());
// 当然没有什么问题
console.assert(r.left.right.val === 5);
复制代码

递归遍历二叉树

好了我们有一棵二叉树了，接下来我们试着用不同的方式去遍历它。

二叉树有三种常见的遍历方式，分别是前序，中序和后序, 以下面的二叉树为例:

          1/   \2     3/ \   / \4  5  6  7/ \  \   /8  9  10 11
复制代码

让我们定义一些操作:

• 操作A: 访问某个结点，再访问该结点的左子结点，然后访问该子结点的左子结点，直到叶子结点则执行操作B
• 操作B: 访问某个结点的父结点的右子结点, 若该父结点的右子结点为叶子结点，访问该叶子结点。若该父结点的右子结点不为叶子结点，则执行操作A

*注: 访问在这里代表的是访问结点并记录结点的值, 即下文中的result.push

前序遍历，就是对根结点进行操作A, 得到的数组就是[1, 2, 4, 8, 9, 5, null, 10, 3, 6, null, null, 7, 11]。

所以递归的写法就是这样的:

function preorderTraversal(root, result) {if (root) {result.push(root.val);// 访问结点的左子结点，直到叶子结点preorderTraversal(root.left, result);preorderTraversal(root.right, result);}return result;
}
复制代码

中序遍历的操作为:

• 操作A: 访问某个结点的最左叶子结点，并执行操作B
• 操作B: 访问某个结点的父结点, 若该父结点的右子结点为叶子结点，访问该叶子结点。若该父结点的右子结点不为叶子结点，则执行操作A

中序遍历，就是对根结点进行操作A, 得到的数组就是[8, 4, 9, 2, null, 5, 10, 1, null, 6, null, 3, 11, 7]。

function inorderTraversal(root, result) {if (root) {// 访问某个结点的最左叶子结点, 然后call stack弹出，访问该叶子结点的父结点inorderTraversal(root.left, result);result.push(root.val);inorderTraversal(root.right, result);}return result;
}
复制代码

后序遍历的操作为:

• 操作A: 访问某个结点的最左叶子结点，并执行操作B
• 操作B: 访问某个结点父结点的右子结点, 若该父结点的右子结点为叶子结点，访问该叶子结点，然后访问该父结点。若该父结点的右子结点不为叶子结点，则执行操作A

后序遍历，就是对根结点进行操作A, 得到的数组就是[8, 9, 4, null, 10, 5, 2, null, null, 6, 11, 7, 3, 1]。

function postorderTraversal(root, result) {if (root) {postorderTraversal(root.left, result);// 访问某个结点父结点的右子结点postorderTraversal(root.right, result);result.push(root.val);}return result;
}
复制代码

进阶

关于二叉搜索树

由于单纯讨论的二叉树的结点插入和删除没有太大的现实意义，笔者还是决定介绍二叉搜索树的结点插入和删除。

二叉搜索树也叫二叉查找树, 或是二叉排序树，简写为BST(Binary Search Tree)

它有个非常重要的性质: 若左子树不为空，则左子树上所有结点的值小于等于其根结点的值; 若右子树不空，则右子树上所有结点的值大于等于其根结点的值。例如:

      5/   \3     7/ \   / \2  5  6   8
复制代码

由这个性质不难推断出BST中序遍历得到的序列是升序的。

BST插入结点

由于BST的有序性质，我们只需要给定value就可以做到插入结点, 以上面的BST为例，插入value分别为4, 5, 10的结点

function insertIntoBST(root, val) {if (!root) {// 找到叶子结点，赋值为左/右结点return new Node(val);}// 你也可以把与根结点value相同的结点放在根结点的右子树if (val <= root.val) {root.left = insertIntoBST(root.left, val);} else if (val > root.val) {root.right = insertIntoBST(root.right, val);}return root;
}
复制代码

const a = [5, 3, 7, 2, 5, 6, 8];
const r = buildCompleteTree(a, 0, new Node());insertIntoBST(r, 4);
insertIntoBST(r, 5);
insertIntoBST(r, 10);
// 当然依然是有序的
console.warn(inorderTraversal(r, []));
复制代码

还有一种写法虽然增加了一些代码量, 但是可以少递归一层

function insertNode(root, val) {if (val <= root.val) {if (!root.left) {root.left = new Node(val);} else {insertNode(root.left, val);}} else if (val > root.val) {if (!root.right) {root.right = new Node(val);} else {insertNode(root.right, val);}}return root;
}
复制代码

BST删除结点

删除结点需要分三种情况讨论:

• 第一种是删除的结点为叶子结点，这种情况非常简单，将该叶子结点置为null即可。
• 第二种是删除的结点有左结点/右结点，这种情况也非常简单，将删除的结点置为该子结点即可。
• 第三种是删除的结点有左右两个子结点，这种情况就比较复杂了，需要将删除结点的右子结点的最左叶子结点, 置为删除结点的左子结点, 再将删除结点置为删除结点的右子结点。

          8/   \6     12/ \   / \4  7  9  13/ \  \   /2  5  8 13
复制代码

假如我们要删除value为12的那个结点, 删除后的BST为:

          8/   \6     13/ \    /4  7   13/ \  \  /2  5  8  9
复制代码

function deleteNode(root, val) {if (!root) {return null;}if (root.val === val && (!root.left || !root.right)) {return root.left || root.right;} else if (root.val === val) {let temp = root.right;while (temp.left) {temp = temp.left;}// 删除结点的右子结点的最左叶子结点, 置为删除结点的左子结点temp.left = root.left;return root.right;}if (val < root.val) {// 若为叶子结点，置为null, 否则置为给定的结点root.left = deleteNode(root.left, val);} else if (val > root.val) {root.right = deleteNode(root.right, val);}return root;
}
复制代码

非递归遍历二叉树

非递归的写法也是需要掌握的，注意注释里的内容!

function preorderTraversal(root) {const result = [];const stack = [root];while(stack.length > 0) {const current = stack.pop();result.push(current.val);// 先push右子结点，保证先访问到左子结点(后push的先pop)stack.push(current.right);stack.push(current.left);}return result;
}
复制代码

function inorderTraversal(root) {const result = [];const stack = [];let current = root;while (current || stack.length > 0) {while (current) {stack.push(current);current = current.left;}// 访问某个结点的最左叶子结点, 然后call stack弹出，访问该叶子结点的父结点current = stack.pop();result.push(current.val);// 若该父结点的右子结点为叶子结点，访问该叶子结点。若该父结点的右子结点不为叶子结点，则执行操作Acurrent = current.right;}return result;
}
复制代码

function postorderTraversal(root) {const result = [];// 保证根结点在结果的末尾const stack = [root];while (stack.length > 0) {const current = stack.pop();if (current) {result.unshift(current.val);stack.push(current.left);// 后push右子结点，保证先访问到左子结点(先push的先unshift)stack.push(current.right);}}return result;
}
复制代码

好了，以上就是关于二叉树CRUD的全部内容。