在新创建的二叉树中的第一次插入会在根节点创建一个节点。根据左子代小于父代而右子代大于父代的二叉搜索树属性,将插入更多插入。
让我们看看如何在代码中实现该算法-
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);
二叉搜索树(BST)和二叉树(BT)中的插入有什么区别?我知道,在BST中,您将新节点的值与根进行比较,如果较小,则添加到其左侧,如果较大,则将其添加到根的右侧。BT的程序是否相同?如果没有,插入和移除的步骤是什么?
这是我的servlet类 这是我在servlet类中使用的普通java类 当我运行时,我得到如下错误 类型异常报告 消息 说明服务器遇到内部错误(),无法满足此请求。 例外 javax。servlet。ServletException:Servlet执行引发异常 根本原因 为什么我会出现这个错误。有人能帮我吗?
我试图在二叉树中插入节点,如果我用addNode(Node root)替换方法addNode(Node Node)代码运行良好。这是因为我在第一行声明了吗?请解释一下。addNode方法由于字数限制而不完整,否则它是完整的,运行良好。
目标 认识 Java 语言中的保留字 理解 Java 类与 Java 对象之间的关系。 了解 Java 类中的每种结构的功能和语法 OOP 与对象密切相关。本单元介绍两个与 Java 语言如何处理对象紧密相关的主题:保留字和 Java 类的结构。 保留字 跟任何编程语言一样,Java 语言指定了一些编译器认为具有特殊含义的关键字。出于该原因,不允许您使用它们来命名您的 Java 结构。保留字(也称
本文向大家介绍在Javascript AVL树中插入节点,包括了在Javascript AVL树中插入节点的使用技巧和注意事项,需要的朋友参考一下 我们可以学习如何在AVL树中插入节点。AVL树中的插入与BST相同,只要我们在树上向下移动,我们只需在插入过程中执行一个额外的步骤,称为平衡树。 这需要计算我们之前已经看到的平衡因子。并且根据配置,我们需要调用适当的旋转方法。在以上说明的帮助下,这些都
我试图在二叉树中插入节点,如果我用addNode(Node root)替换方法addNode(Node Node)代码运行良好。这是因为我在第一行声明了吗?请解释一下。addNode方法由于字数限制而不完整,否则它是完整的,运行良好。