二分搜索樹（Binary Search Tree，BST）是一種常見的資料結構，它能夠高效地存盤和查找資料，它的特點是每個節點都包含一個值，并且每個節點的左子樹的值都小于節點的值，右子樹的值都大于節點的值，
查找
通過這種有序的排列方式，我們可以在二分搜索樹中進行高效的查找操作，想象一下，如果我們要查找一個特定的值，我們可以從根節點開始比較它與當前節點的值的大小關系，如果它比當前節點的值小，我們就去左子樹中繼續查找；如果它比當前節點的值大，我們就去右子樹中查找，通過不斷地比較和移動，我們最終要么找到了目標值，要么確定它不在樹中，
插入
除了查找，二分搜索樹還支持插入操作，當我們要插入一個新的值時
我們從根節點開始，比較新值和當前節點的大小關系，
如果它比當前節點的值小，我們就往左子樹插入；
如果它比當前節點的值大，我們就往右子樹插入，
我們不斷地比較和移動，直到找到一個合適的位置，然后將新值插入為一個新的葉子節點，
洗掉
洗掉操作稍微復雜一些，因為我們要保持二分搜索樹的有序性質，當我們要洗掉一個節點時，有三種可能的情況需要考慮：
-
如果待洗掉節點沒有子節點，我們可以直接將其洗掉，不會破壞樹的有序性，
-
如果待洗掉節點只有一個子節點，我們可以將子節點提升到待洗掉節點的位置上，同樣不會破壞有序性，
-
如果待洗掉節點有兩個子節點，我們需要找到它的后繼節點（比待洗掉節點大的最小節點）或前驅節點（比待洗掉節點小的最大節點）來替代它，我們可以選擇將后繼節點提升到待洗掉節點的位置上，或者將前驅節點提升到待洗掉節點的位置上，然后洗掉后繼或前驅節點，
但是二叉樹的洗掉相對校招并不重要，而且代碼過于復雜，所以我們這里就不再細講，這里只是為了保證知識完整性羅列一下，
前中后序遍歷和層序遍歷
-
前序遍歷：對于每個節點，先訪問它自己，然后訪問它的左子樹，最后訪問它的右子樹，（根左右）
-
中序遍歷：對于每個節點，先訪問它的左子樹，然后訪問它自己，最后訪問它的右子樹，（左根右）
-
后序遍歷：對于每個節點，先訪問它的左子樹，然后訪問它的右子樹，最后訪問它自己，（左右根）
-
層序遍歷：從根節點開始，先訪問根節點，然后按照從左到右的順序依次訪問每一層的節點，
這些遍歷方式各有特點，適用于不同的應用場景，
前序遍歷可以用于復制整個樹的結構，
中序遍歷可以得到一個有序的節點值序列，
后序遍歷常用于釋放二叉樹的記憶體，
而層序遍歷可以逐層列印樹的結構，
二分搜索樹的特點在于每個節點的左子樹的值都小于節點的值，右子樹的值都大于節點的值，這種有序性質使得二分搜索樹成為了很多應用中的首選資料結構之一，
代碼實作：
package com.Search;
?
import java.util.LinkedList;
import java.util.Queue;
?
/**
* @Author: 翰林猿
* @Description: 二分搜索樹
**/
public class BSearchTree<E extends Comparable<E>> {
?
private class Node {
public E e;
public Node left, right;
?
public Node(E e) {
this.e = e;
left = null;
right = null;
}
}
?
private int size; //節點數量
private Node root; //根節點
?
public BSearchTree() {
size = 0;
root = null;
}
?
public int getSize() {
return size;
}
?
public boolean isEmpty() {
return size == 0;
}
?
/**
* @Description: 插入
**/
public void add(E e) {
root = add(root, e);
}
?
//向以node為根的樹插入e元素，回傳插入新節點之后的根，
private Node add(Node node, E e) {
if (node == null) { //如果沒有該元素，直接回傳一個新元素
size++;
return new Node(e);
}
if (e.compareTo(node.e) < 0) //如果小于當前根元素，就往左邊遞回，
node.left = add(node.left, e); //傳入的引數就是左邊的子節點（意思就是說，以左節點作為左邊的樹的樹根進行判斷是否為空）
else if (e.compareTo(node.e) > 0) //如果大于當前根元素，就往右邊遞回
node.right = add(node.right, e);
return node;
}
/**
* @Description: 查詢
**/
public boolean contains(E e) {
return contains(root, e);
}
private boolean contains(Node node, E e) {
if (node == null)
return false;
if (e.compareTo(node.e) == 0)
return true;
else if (e.compareTo(node.e) > 0) //如果查找的節點大于當前節點，遞回去右子樹找
return contains(node.right, e);
else //e.compareTo(node.e) > 0 //如果查找的節點小于當前節點，遞回去左子樹找
return contains(node.left, e);
}
?
/**
* @Description: 前序遍歷，根左右
**/
public void preOrder() {
preOrder(root);
}
private void preOrder(Node node) {
if (node != null) {
System.out.print(node.e + " ");
preOrder(node.left);
preOrder(node.right);
}
}
/**
* @Description: 中序遍歷，左根右
**/
public void inOrder() {
inOrder(root);
}
?
private void inOrder(Node node) {
if (node != null) {
inOrder(node.left);
System.out.print(node.e + " ");
inOrder(node.right);
}
}
/**
* @Description: 后序遍歷，左右根
**/
public void postOrder() {
postOrder(root);
}
?
private void postOrder(Node node) {
if (node != null) {
postOrder(node.left);
postOrder(node.right);
System.out.print(node.e + " ");
}
}
/**
* @Description: 層序遍歷，廣度優先遍歷
* 1.將節點入隊，進入回圈
* 2.取出一個節點并列印，并將其左右子節點（如果存在）入隊，
* 3.重復直到佇列為空
**/
public void levelOrder() {
if (root == null) {
return;
}
?
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
?
while (!queue.isEmpty()) {
Node node = queue.poll();
System.out.print(node.e + " ");
?
if (node.left != null) {
queue.offer(node.left);
}
?
if (node.right != null) {
queue.offer(node.right);
}
}
}
?
?
/**
* @Description: 測驗用例
*
* 7
* / \
* 4 9
* / \ / \
* 2 5 8 10
* / \ \
* 1 3 11
**/
public static void main(String[] args) {
BSearchTree<Integer> bst = new BSearchTree<>();
bst.add(7);
bst.add(4);
bst.add(9);
bst.add(2);
bst.add(5);
bst.add(8);
bst.add(10);
bst.add(1);
bst.add(3);
bst.add(11);
System.out.println("二叉搜索樹節點數量: " + bst.getSize());
?
System.out.println("是否存在5號節點: " + bst.contains(5));
System.out.println("是否存在100號節點: " + bst.contains(100));
?
System.out.print("前序遍歷: ");
bst.preOrder();
System.out.println();
?
System.out.print("中序遍歷: ");
bst.inOrder();
System.out.println();
?
System.out.print("后序遍歷: ");
bst.postOrder();
System.out.println();
?
System.out.print("層序遍歷: ");
bst.levelOrder();
}
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/555835.html
標籤：其他
上一篇：協議分析(一)
下一篇：返回列表