wangxiaohua 2017-03-15
二叉查找树(Binary Search Tree),又称二叉排序树或二叉搜索树,是属于二叉树的一种。它最大的特点是每个节点的左子节点永远比该节点小,而每个节点的右子节点却永远比该节点大,即任意节点的左子树上所有结点永远比该节点的右子树上所有结点的值小,它的任意左、右子树也分别为二叉查找树。
以下是使用js代码来实现。
/** * 树的节点 * @param data 节点的数值 * @param left 该节点的左子节点 * @param right 该节点的右子节点 */ function TreeNode(data, left, right) { this.data = data; this.left = left || null; this.right = right || null; }
/** * 二叉查找树 * @param rootNode 根节点 */ function BinarySearchTree(rootNode) { this.rootNode = rootNode || null; } BinarySearchTree.prototype = { // 后面讲的查找,新增,删除功能会放在本区域(即原型) }
插入工作必须按照二叉查找树的特性来完成。
新增代码如下:
/** * 插入节点 * @param data 需要插入节点的值 */ function insert(data) { // 生成新的节点 var newNode = new TreeNode(data); // 判断根节点是否存在 if (!this.rootNode) { this.rootNode = newNode; return; } var currentNode = this.rootNode; var parent = null; while (true) { parent = currentNode; if (data < currentNode.data) { currentNode = currentNode.left; if (!currentNode) { parent.left = newNode; return; } } else if (data > currentNode.data) { currentNode = currentNode.right; if (!currentNode) { parent.right = newNode; return; } } else { console.log("该节点已存在"); return; } } }
查找功能其实与新增功能类似,首先要判断根节点是否存在,然后需要把待查找的节点从根节点开始逐级比较查找,规则同样是左子树的节点永远小于右子树的节点,直到找到为止。
/** * 查找节点 * @param data 待查找节点的值 */ function: find(data) { // 判断根节点是否存在 if (!this.rootNode) { return; } var currentNode = this.rootNode; while (true) { if (!currentNode) { console.log("该节点不存在"); return; } if (data < currentNode.data) { currentNode = currentNode.left; } else if (data > currentNode.data) { currentNode = currentNode.right; } else { return currentNode; } } }
删除功能就比较复杂了,主要分三种情况:
具体流程如下:
1. 查找到待删除的结点和它的父节点;
2. 判断该节点有无左右子树,如果没有,那么直接删除;
3. 如果只有左右子树中的一个,那么直接它的父节点指向它的左子树或右子树,然后删除节点;
4. 如果左右子树都有,本人按照从左子树的取最大的节点方法列实行;
/** * 删除目标节点 * @param data 待删除目标节点的值 */ function removeNode(data) { // 判断根节点是否存在 if (!this.rootNode) { return; } // 目标节点的父节点 var parent = null; // 目标节点 var currentNode = this.rootNode; // 目标节点位于父节点的位置 var place = null; while (true) { if (!currentNode) { console.log("该节点不存在"); return; } if (data < currentNode.data) { parent = currentNode; currentNode = currentNode.left; place = "left"; } else if (data > currentNode.data) { parent = currentNode; currentNode = currentNode.right; place = "right"; } else { // 找到对应节点跳出循环 break; } } if (!currentNode.left) { // 删除的节点没有左孩子的情况 parent[place] = currentNode.right || null; } else if (!currentNode.right) { // 删除的节点没有右孩子的情况 parent[place] = currentNode.left || null; } else { // 用于代替的节点 var replaceNode = currentNode.left; // 代替节点的父节点 var replaceNodeParent = null; // 循环找出左子树中最大的节点(即用于代替的节点) while(replaceNode.right) { replaceNodeParent = replaceNode; replaceNode = replaceNode.right; } // 代替原位置 parent[place] = replaceNode; // 当代替节点就是删除的节点的左子节点时无需赋左子树 if (replaceNodeParent) { replaceNodeParent.right = replaceNode.left || null; parent[place].left = currentNode.left; } // 获取删除的节点的右子树 parent[place].right = currentNode.right; } return; }
以上即是具体讲解,整套代码如下: