Open fxxqq opened 6 years ago
二叉查找树(Binary Search Tree),又称二叉排序树或二叉搜索树,是属于二叉树的一种。它最大的特点是每个节点的左子节点永远比该节点小,而每个节点的右子节点却永远比该节点大,即任意节点的左子树上所有结点永远比该节点的右子树上所有结点的值小,它的任意左、右子树也分别为二叉查找树。
任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 任意节点的左、右子树也分别为二叉查找树; 没有键值相等的节点。二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合、multiset、关联数组等。
在写的时候需要足够理解二叉搜素树的特点,需要先设定好每个节点的数据结构
/** * 树的节点 * @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; } } }
删除功能就比较复杂了,主要分三种情况: 待删除节点无子节点时,直接删除节点即可; 待删除节点只有右子树或只有左子树时,直接把待删除节点的父节点的指针指向待删除节点的右子树或右子树即可,然后删除节点; 这种情况相对较复杂,就是待删除节点既有左节点又有右节点。通常有两种方法来解决: 从待删除节点的左子树选出最大的节点即最靠近右边的节点来顶替删除后腾出的节点位置; 从待删除节点的右子树选出最小的节点即最靠近左边的节点来顶替删除后腾出的节点位置;
具体流程如下:
/** * 删除目标节点 * @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; }
以上即是具体讲解,整套代码如下:
/** * 树的节点 * @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 = { // 插入子节点 insert: function(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; } } }, // 查找节点 find: function(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; } } }, // 删除目标节点 removeNode: function (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; } }
本文来自 伤包子 的CSDN 博客 ,全文地址请点击:https://blog.csdn.net/wl812peter/article/details/56663373?utm_source=copy
理论
二叉查找树(Binary Search Tree),又称二叉排序树或二叉搜索树,是属于二叉树的一种。它最大的特点是每个节点的左子节点永远比该节点小,而每个节点的右子节点却永远比该节点大,即任意节点的左子树上所有结点永远比该节点的右子树上所有结点的值小,它的任意左、右子树也分别为二叉查找树。
在写的时候需要足够理解二叉搜素树的特点,需要先设定好每个节点的数据结构
代码
先定义二叉查找树的节点:
定义二叉树:
二叉查找树的新增功能
二叉查找树的新增功能
首先判断该二叉树是否有根节点,如果没有则把新节点作为根节点,反之则继续; 从根节点开始逐级比较,即如果新结点的值小于根节点的值,则将新结点与根节点的左子树中的节点去比较,大于则与根节点的右子树中的节点去比较; 逐级比较直到找到需要插入的空位为止,把新节点放入即可;
新增代码如下:
二叉查找树的查找功能
查找功能其实与新增功能类似,首先要判断根节点是否存在,然后需要把待查找的节点从根节点开始逐级比较查找,规则同样是左子树的节点永远小于右子树的节点,直到找到为止。
二叉查找树的节点删除功能
具体流程如下:
以上即是具体讲解,整套代码如下:
本文来自 伤包子 的CSDN 博客 ,全文地址请点击:https://blog.csdn.net/wl812peter/article/details/56663373?utm_source=copy