在 Javascript 中将键插入树中
web developmentfront end technologyjavascript
在新建的二叉树中第一次插入会在根节点创建一个节点。后续插入将根据二叉搜索树的属性进行，即左子节点小于父节点，右子节点大于父节点。
让我们看看如何在代码 − 中实现此算法
示例
insertIter(data) {
let node = new this.Node(data);
// 检查树是否为空
if (this.root === null) {
// 作为第一个元素插入
this.root = node; return;
}
let currNode = this.root;
while (true) {
if (data < currNode.data) {
// 在这里设置值，因为我们已经到达了叶节点
if (currNode.left === null) {
currNode.left = node;
break;
} else {
currNode = currNode.left;
}
} else {
// 在这里设置值，因为我们已经到达了叶节点
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);
我们还可以使此函数递归。树本质上是递归结构，我们可以相当轻松地利用此递归属性。让我们看一下 insert − 的递归版本
示例
insertRec(data) {
let node = new this.Node(data);
// 检查树是否为空
if (this.root === null) {
// 作为第一个元素插入
this.root = node;
} else {
insertRecHelper(this.root, node);
}
}
我们需要创建一个可以递归的辅助函数，但我们不想将其作为类的属性公开，因此该函数将超出类定义。
示例
function insertRecHelper(root, node) {
if (node.data < root.data) {
// 在这里设置值，因为我们已经到达了叶节点
if (root.left === null) {
root.left = node;
} else {
// 使用左子树递归调用此函数
insertRecHelper(root.left, node);
}
} else {
// 在此处设置值，因为我们已经到达叶节点
if (root.right === null) {
root.right = node;
} else {
// 使用右子树递归调用此函数
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);
