資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告