在新创建的二叉树中的第一次插入会在根节点创建一个节点。根据左子代小于父代而右子代大于父代的二叉搜索树属性,将插入更多插入。
让我们看看如何在代码中实现该算法-
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,如果小于,则检查其左子节点是否为null。如果是,那么我们将数据保存在此处并退出。否则,我们将继续进行迭代,直到到达一片叶子,最后将数据放置在那里。
您可以使用-测试此功能
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);
// 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);