在Java语言中将键插入树中

在新创建的二叉树中的第一次插入会在根节点创建一个节点。根据左子代小于父代而右子代大于父代的二叉搜索树属性，将插入更多插入。

让我们看看如何在代码中实现该算法-

示例

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);