二叉搜索樹
- 概念
- 特點
- 基本操作
- 1.插入元素
- 2.查找元素
- 3.洗掉元素
概念
二叉搜索樹是一種特殊的二叉樹
特點
左子樹中的值都小于根節點，右子樹中的值都大于根節點
故：中序遍歷結果就會得到一個有序序列
最大的特點：就是能夠高效的進行查找元素
查找程序類似于二分查找：先從根節點出發開始比較，看待查找元素是小于根節點還是大于根節點，進一步決定是去左子樹中找，還是右子樹
查找的時間復雜度：O(N) (單支樹)
解決方案：采取更加平衡的二叉搜索樹，AVL樹(絕對平衡)，紅黑樹
基本操作
1.插入元素
其實和查找非常相似，需要先找到待插入元素的合適位置
若樹為空樹，直接插入為根節點即可
對于二叉搜索樹來說，插入元素的時候，元素都是被插入到葉子節點上的
2.查找元素
也很簡單，簡單畫圖理解即可~
3.洗掉元素
需要考慮很多種不同的情況：
- 情況1：待洗掉元素是父節點的左子樹
且，待洗掉元素左子樹為空，右子樹非空
直接讓父節點的左子樹，指向待洗掉元素的右子樹即可
- 情況2：待洗掉元素是父節點的右子樹
待洗掉元素的左子樹為空，右子樹非空
直接讓父節點的右子樹，指向待洗掉節點的右子樹即可
- 情況3：待洗掉元素是父節點的左子樹
待洗掉元素左子樹非空，右子樹為空
直接將父節點的左子樹，指向待洗掉結點的左子樹即可
- 情況4：待洗掉元素是父節點的右子樹
待洗掉元素左子樹非空，右子樹為空
直接將父節點的右子樹，指向待洗掉結點的左子樹即可
- 情況5：待洗掉元素是父節點的左子樹
待洗掉元素左 / 右子樹均非空
- 情況6：待洗掉元素是父節點的右子樹
待洗掉元素左 / 右子樹均非空
代碼實作：
public class BinarySearchTree {
public static class Node{
int key;
Node left;
Node right;
public Node(int key) {
this.key = key;
}
}
// 根節點 root 為null，表示為空樹
private Node root = null;
//查找操作
public Node find(int key){
// 查找 key 是否存在
// 若存在，回傳對應的Node
// 若不存在，回傳null
Node cur = root;
while (cur != null){
if(key < cur.key){
//此時去左子樹中找
cur = cur.left;
}
else if(key > cur.key){
// 此時去右子樹找
cur = cur.right;
}
else{
// 找到了
return cur;
}
}
// key 不存在
return null;
}
//插入操作
public boolean insert(int key){
// 二叉搜索樹中 是不允許存在相同 key 的元素的
// 若新插入的 key 重復，就插入失敗，回傳 false
// 插入成功 回傳 true
// 空樹判斷
if(root == null){
root = new Node(key);
return true;
}
//先找到合適的位置,再去插入元素
Node cur = root;
// 讓 parent 始終指向 cur 的父節點
Node parent = null;
while (cur != null){
if(key < cur.key){
parent = cur;
cur = cur.left;
}
else if(key > cur.key){
parent = cur;
cur = cur.right;
}
else{
// 某個元素和待插入元素值相同
return false;
}
}
// 回圈結束，cur 指向 null
// 當前元素就要插到 parent 子樹的位置上
if(key < parent.key){
parent.left = new Node(key);
}
else{
parent.right = new Node(key);
}
return true;
}
//洗掉操作
public boolean remove(int key){
// 先找到 待洗掉節點的位置,再進行洗掉
// 找到待洗掉元素后，再來判斷是那種情況
Node cur = root;
Node parent = null;
while (cur != null){
if(key < cur.key){
parent = cur;
cur = cur.left;
}
else if(key > cur.key){
parent = cur;
cur = cur.right;
}
else{
// 找到了 待洗掉元素,就是 cur 指向的元素
removeNode(parent,cur);
return true;
}
}
return false;
}
private void removeNode(Node parent, Node cur) {
// 1.待洗掉元素左子樹為空
if(cur.left == null){
//1.1 若要洗掉節點為 root
if(cur == root){
root = cur.right;
}
//1.2 cur 是 parent 的左子樹
else if(cur == parent.left){
parent.left = cur.right;
}
//1.3 cur 是 parent 的右子樹
else{
parent.right = cur.right;
}
}
// 2.待洗掉元素右子樹為空
else if(cur.right == null){
//2.1 若要洗掉節點為 root
if(cur == root){
root = cur.left;
}
//2.2 cur 是 parent 的左子樹
else if(cur == parent.left){
parent.left = cur.left;
}
//2.3 cur 是 parent 的右子樹
else{
parent.right = cur.left;
}
}
// 3.待洗掉節點有兩個子樹
else{
// ①找到右子樹的最小元素 / 左子樹的最大元素(替罪羊)
Node goatParent = cur;
Node scapeGoat = cur.right;
while (scapeGoat.left != null){
goatParent = scapeGoat;
scapeGoat = scapeGoat.left;
}
// 當回圈結束時，scapeGoat 指向了右子樹中的最小值
// ②將找到的元素，賦值給待洗掉節點
cur.key = scapeGoat.key;
// ③洗掉替罪羊節點
// 替罪羊節點一定沒有左子樹
if(scapeGoat == goatParent.left){
goatParent.left = scapeGoat.right;
}
else{
goatParent.right = scapeGoat.right;
}
}
}
}
插入測驗：
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.insert(9);
tree.insert(5);
tree.insert(2);
tree.insert(7);
tree.insert(3);
tree.insert(6);
tree.insert(8);
//為了查看樹的結構，可以列印樹的先序和中序遍歷結果
tree.preOrder(tree.root);
System.out.println();
tree.inOrder(tree.root);
}
// 先序遍歷
public void preOrder(Node root){
if(root == null){
return;
}
System.out.print(root.key + " ");
preOrder(root.left);
preOrder(root.right);
}
// 中序遍歷
public void inOrder(Node root){
if(root == null){
return;
}
inOrder(root.left);
System.out.print(root.key + " ");
inOrder(root.right);
}
輸出結果：
根據先 、中序遍歷結果，來還原二叉樹，得到：
除錯代碼：
得到的結果和我們圖上還原的結果一樣
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/344237.html
標籤：其他
上一篇：資料結構之鏈表（1）
下一篇：Linux系統安裝與實驗基礎