数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 JavaScript 中将键插入树
在新建的二叉树中，第一次插入会在根节点创建一个节点。之后的插入将根据二叉搜索树的特性进行，即左子节点小于父节点，右子节点大于父节点。
让我们看看如何在代码中实现这个算法：
示例
insertIter(data) {
let node = new this.Node(data);
// Check if the tree is empty
if (this.root === null) {
// Insert as the first element
this.root = node; return;
}
let currNode = this.root;
while (true) {
if (data < currNode.data) {
// Set the value here as we've reached a leaf node
if (currNode.left === null) {
currNode.left = node;
break;
} else {
currNode = currNode.left;
}
} else {
// Set the value here as we've reached a leaf node
if (currNode.right === null) {
currNode.right = node;
break;
} else {
currNode = currNode.right;
}
}
}
}让我们了解一下这个函数是如何工作的。首先，我们检查根节点是否为空，这意味着树是否为空，如果是，则将新节点赋值为根节点，我们就完成了。如果不是，我们创建一个 currNode 变量并将其指向根节点。然后我们检查我们的数据是否小于 currNode，如果是，我们检查其左子节点是否为空。如果是，则我们将数据保存在这里并退出。否则，我们将继续迭代直到到达叶子节点，最后将数据放置在那里。
您可以使用以下方法测试此函数：
示例
let BST = new BinarySearchTree(); BST.insertIter(10); BST.insertIter(15); BST.insertIter(5); BST.insertIter(50); BST.insertIter(3); BST.insertIter(7); BST.insertIter(12);
我们也可以使此函数递归。树本身就是递归结构，我们可以很容易地利用这种递归特性。让我们看看插入的递归版本：
示例
insertRec(data) {
let node = new this.Node(data);
// Check if the tree is empty
if (this.root === null) {
// Insert as the first element
this.root = node;
} else {
insertRecHelper(this.root, node);
}
}我们需要创建一个可以递归的辅助函数，但我们不想将其作为类的属性公开，因此此函数将位于类定义之外。
示例
function insertRecHelper(root, node) {
if (node.data < root.data) {
// Set the value here as we've reached a leaf node
if (root.left === null) {
root.left = node;
} else {
// Recursively call this function with the left subtree
insertRecHelper(root.left, node);
}
} else {
// Set the value here as we've reached a leaf node
if (root.right === null) {
root.right = node;
} else {
// Recursively call this function with the right subtree
insertRecHelper(root.right, node);
}
}
}您可以使用以下方法进行测试：
示例
let BST = new BinarySearchTree(); BST.insertRec(10); BST.insertRec(15); BST.insertRec(5); BST.insertRec(50); BST.insertRec(3); BST.insertRec(7); BST.insertRec(12);
更新于: 2020年6月15日
611 次浏览
广告