資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 JavaScript 中實現二叉搜尋樹
樹形資料結構
樹是由一些邊連線起來的節點集合。按照慣例，樹的每個節點都包含一些資料及其子節點的引用。
二叉搜尋樹
二叉搜尋樹是一種二叉樹，其中值較小的節點儲存在左邊，而值較大的節點儲存在右邊。
例如，有效 BST 的視覺化表示為：
25 / \ 20 36 / \ / \ 10 22 30 40
現在讓我們用 JavaScript 語言實現我們自己的二叉搜尋樹。
步驟 1：節點類
此類將表示 BST 中各個點處單個節點。BST 不過是根據上述規則放置的資料和子節點引用的節點集合。
class Node{
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
};
};要建立一個新的 Node 例項，我們可以像這樣使用一些資料呼叫此類：
const newNode = new Node(23);
這將建立一個新的 Node 例項，其中資料設定為 23，左右引用均為 null。
步驟 2：二叉搜尋樹類
class BinarySearchTree{
constructor(){
this.root = null;
};
};這將建立二叉搜尋樹類，我們可以使用 new 關鍵字呼叫它來建立一個樹例項。
現在我們完成了基本工作，讓我們繼續在正確的位置插入一個新節點（根據定義中描述的 BST 規則）。
步驟 3：在 BST 中插入節點
class BinarySearchTree{
constructor(){
this.root = null;
}
insert(data){
var newNode = new Node(data);
if(this.root === null){
this.root = newNode;
}else{
this.insertNode(this.root, newNode);
};
};
insertNode(node, newNode){
if(newNode.data < node.data){
if(node.left === null){
node.left = newNode;
}else{
this.insertNode(node.left, newNode);
};
} else {
if(node.right === null){
node.right = newNode;
}else{
this.insertNode(node.right,newNode);
};
};
};
};示例
完整的二叉搜尋樹程式碼
class Node{
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
};
};
class BinarySearchTree{
constructor(){
this.root = null;
}
insert(data){
var newNode = new Node(data);
if(this.root === null){
this.root = newNode;
}else{
this.insertNode(this.root, newNode);
};
};
insertNode(node, newNode){
if(newNode.data < node.data){
if(node.left === null){
node.left = newNode;
}else{
this.insertNode(node.left, newNode);
};
} else {
if(node.right === null){
node.right = newNode;
}else{
this.insertNode(node.right,newNode);
};
};
};
};
const BST = new BinarySearchTree();
BST.insert(1);
BST.insert(3);
BST.insert(2);
更新於：2021年3月3日
4K+ 次瀏覽
廣告