如何在Java中實現二叉搜尋樹（ binary search tree）？
二叉搜尋樹或BST是一種流行的資料結構，用於保持元素的順序。二叉搜尋樹是二叉樹，其中左子節點的值小於或等於父節點，右子節點的值大於或等於父節點。由於它是二叉樹，它只能有0，1或2個子節點。二叉搜尋樹之所以與眾不同，是因為它能夠減少諸如新增、刪除和搜尋（也稱為插入、刪除和查詢）等基本操作的時間複雜性。在BST中，所有這些操作（插入，刪除和查詢）都可以在O（log（n））時間內執行。這種速度提高的原因是由於二叉搜尋樹的獨特屬性，對於每個節點，左子節點中的資料小於（或等於），右子節點中的資料大於（或等於）到所述節點中的資料。
在程式設計面試中，您將看到許多基於二叉搜尋樹的資料結構和演算法問題，例如：檢查二叉樹是否是BST？或者，編寫一個程式來檢查BST是否平衡。為了解決這個問題，您必須知道如何在Java中實現BST。
在這，我將教您如何在Java中實現二叉搜尋樹，您可以使用它來解決任何二叉搜尋樹或基於二叉樹的編碼問題。
Java中的二叉搜尋樹
在這裡，您將學習如何建立具有整數節點的二叉搜尋樹。我使用泛型不僅僅是為了使程式碼簡單，如果您願意，可以將問題擴充套件到使用泛型，這將允許您建立一個字串、整數、浮點或雙精度的二叉樹。記住，確保BST的節點必須實現Comparable介面。這是許多Java程式設計師在嘗試使用泛型實現二叉搜尋樹時容易忘記的。
這裡是Java中的二叉搜尋樹的實現。這只是一個結構，我們隨後將新增方法在二叉搜尋樹中新增節點，從二叉搜尋樹中刪除節點，並在後續部分中從BST中查詢節點。
在這個實現中，我建立了一個Node類，它類似於我們的連結串列節點類，在向您展示如何在Java中實現連結串列時建立的。它有一個數據元素，一個整數和一個Node引用，指向二叉樹中的另一個節點。
我還建立了四個基本功能，如下所示：
getRoot(), 返回二叉樹的根
isEmpty(), 用於檢查二叉搜尋樹是否為空
size(), 查詢BST中的節點總數
clear(), 清除BST
以下是使用Java建立二叉搜尋樹或BST的示例程式碼，不使用任何第三方庫。
<b>import</b> java.util.Stack;
<font><i>/**
* Java Program to implement a binary search tree. A binary search tree is a
* sorted binary tree, where value of a node is greater than or equal to its
* left the child and less than or equal to its right child.
*
* @author WINDOWS 8
*
*/</i></font><font>
<b>public</b> <b>class</b> BST {
<b>private</b> <b>static</b> <b>class</b> Node {
<b>private</b> <b>int</b> data;
<b>private</b> Node left, right;
<b>public</b> Node(<b>int</b> value) {
data = value;
left = right = <b>null</b>;
}
}
<b>private</b> Node root;
<b>public</b> BST() {
root = <b>null</b>;
}
<b>public</b> Node getRoot() {
<b>return</b> root;
}
</font><font><i>/**
* Java function to check if binary tree is empty or not
* Time Complexity of this solution is constant O(1) for
* best, average and worst case.
*
* @return true if binary search tree is empty
*/</i></font><font>
<b>public</b> <b>boolean</b> isEmpty() {
<b>return</b> <b>null</b> == root;
}
</font><font><i>/**
* Java function to return number of nodes in this binary search tree.
* Time complexity of this method is O(n)
* @return size of this binary search tree
*/</i></font><font>
<b>public</b> <b>int</b> size() {
Node current = root;
<b>int</b> size = 0;
Stack<Node> stack = <b>new</b> Stack<Node>();
<b>while</b> (!stack.isEmpty() || current != <b>null</b>) {
<b>if</b> (current != <b>null</b>) {
stack.push(current);
current = current.left;
} <b>else</b> {
size++;
current = stack.pop();
current = current.right;
}
}
<b>return</b> size;
}
</font><font><i>/**
* Java function to clear the binary search tree.
* Time complexity of this method is O(1)
*/</i></font><font>
<b>public</b> <b>void</b> clear() {
root = <b>null</b>;
}
}
</font>