常用樹結構
- 二分搜尋樹
- 平衡二叉樹：AVL、紅黑樹
- 堆；并查集
- 線段樹；Trie（字典樹、字首樹）
二叉樹基礎
和連結清單一樣，二叉樹是一種動态資料結構，資料存儲在“節點”（Node）中，left指向左孩子，right指向右孩子
二叉樹具有唯一根節點，每個節點最多有兩個孩子，沒有孩子的節點稱為葉子節點
二叉樹具有天然的遞歸結構，每個節點的左右子樹也是二叉樹
二分搜尋樹基礎
二分搜尋樹是二叉樹，其每個子樹也是二分搜尋樹
二分搜尋樹的根節點的值滿足：大于左子樹的所有節點值，小于右子樹的所有節點值，不能重複
也就是根節點相當于二分查找法中的mid，隻需比較target和根節點的大小，就可以快速的判斷出其在左子樹還是右子樹，然後用遞歸的方式直到查找到目标
遞歸實作二分搜尋樹
增、删、改、查，前序、中序、後序周遊
public class Algorithm {
public static void main(String[] args) {
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
int[] nums = {5,3,6,8,4,2};
for (int i : nums) {
bst.add(i);
}
bst.preOrder();
System.out.println();
bst.inOrder();
System.out.println();
bst.postOrder();
System.out.println();
System.out.println(bst.removeMin());
System.out.println();
System.out.println(bst.removeMax());
System.out.println();
bst.remove(5);
System.out.println();
bst.preOrder();
}
}
class BinarySearchTree<E extends Comparable<E>> {
/**
* 節點類Node
*/
private class Node{
public E e;
public Node leftNext;
public Node rightNext;
private Node(E e){
this.e = e;
leftNext = null;
rightNext = null;
}
}
private Node root;
private int size;
public BinarySearchTree(){
root = null;
size = 0;
}
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
/**
* 添加節點
* 将根節點和要添加的節點值傳入可遞歸的私有add()方法
* 從根節點挨個進行遞歸比較，值相同則抛棄，左右孩子為空則添加
* 最後傳回添加節點後新的根節點
*/
public void add(E e) {
root = add(root, e);
}
private Node add(Node root, E e){
if (root == null){
size++;
return new Node(e);
}
if (root.e.compareTo(e) < 0){
root.rightNext = add(root.rightNext, e);
}
else if (root.e.compareTo(e) > 0) {
root.leftNext = add(root.leftNext, e);
}
return root;
}
/**
* 删除最小的節點
* Min()方法在樹為空時已經做出判斷了，故無需再次判斷
* 傳入根節點進行遞歸查找，如果左孩子為空，說明該節點就是最小節點
* 删除最小節點以後新的根節點就是右孩子，最後傳回新的根節點
*/
public E removeMin(){
E value = Min();
root = removeMin(root);
return value;
}
private Node removeMin(Node root){
if (root.leftNext == null){
Node newRoot = root.rightNext;
root.rightNext = null;
size--;
return newRoot;
}
root.leftNext = removeMin(root.leftNext);
return root;
}
/**
* 删除最大的節點
*/
public E removeMax(){
E value = Max();
root = removeMax(root);
return value;
}
private Node removeMax(Node root){
if (root.rightNext == null){
Node newRoot = root.leftNext;
root.leftNext = null;
size--;
return newRoot;
}
root.rightNext = removeMax(root.rightNext);
return root;
}
/**
* 删除任意節點（Hubbard Deletion）
* 先找到待删除節點，如果該節點有左右孩子，那就讓右子樹的最小節點或者左子樹的最大節點頂替該節點的位置
* 先擷取右子樹的最小節點，其就是新的根節點，讓其指向待删除節點的左右孩子，注意右孩子是删除最小節點後新的右孩子，最後安全删除節點，傳回新的根節點
* 注意不能直接把最大/小節點值直接指派給該節點，因為其可能也有左右子樹
*/
public void remove(E e){
root = remove(root, e);
}
private Node remove(Node root, E e){
if (root == null){
return null;
}
if (root.e.compareTo(e) < 0){
root.rightNext = remove(root.rightNext, e);
return root;
}
else if (root.e.compareTo(e) > 0){
root.leftNext = remove(root.leftNext, e);
return root;
}
else {
if (root.leftNext == null) {
Node newRoot = root.rightNext;
root.rightNext = null;
size--;
return newRoot;
} else if (root.rightNext == null) {
Node newRoot = root.leftNext;
root.leftNext = null;
size--;
return newRoot;
} else {
/**
* removeMin()方法中已經進行過size--
*/
Node newRoot = Min(root.rightNext);
newRoot.rightNext = removeMin(root.rightNext);
newRoot.leftNext = root.leftNext;
root.leftNext = null;
root.rightNext = null;
return newRoot;
}
}
}
/**
* 修改節點
* 前序周遊，先通路根節點，再遞歸通路左子樹和右子樹
*/
public void preOrder(){
preOrder(root);
}
private void preOrder(Node root){
if (root == null) {
return;
}
System.out.println(root.e);
preOrder(root.leftNext);
preOrder(root.rightNext);
}
/**
* 中序周遊，先遞歸通路左子樹，再通路根節點，最後遞歸通路右子樹
* 該結果就是所有節點的升序排列
*/
public void inOrder(){
inOrder(root);
}
private void inOrder(Node root){
if (root == null){
return;
}
inOrder(root.leftNext);
System.out.println(root.e);
inOrder(root.rightNext);
}
/**
* 後序周遊，先遞歸通路左子樹，再遞歸通路右子樹，最後通路根節點
*/
public void postOrder(){
postOrder(root);
}
private void postOrder(Node root){
if (root == null){
return;
}
postOrder(root.leftNext);
postOrder(root.rightNext);
System.out.println(root.e);
}
/**
* 查詢節點
*/
public boolean contains(E e){
return contains(root, e);
}
private boolean contains(Node root, E e){
if (root == null) {
return false;
}
if (root.e.compareTo(e) == 0){
return true;
}
else if (root.e.compareTo(e) > 0){
return contains(root.leftNext, e);
}
else {
return contains(root.rightNext, e);
}
}
/**
* 查找最小的節點
* 如果左孩子為空，則目前節點就是最小節點
*/
public E Min(){
return Min(root).e;
}
private Node Min(Node root){
if (root == null){
return null;
}
if (root.leftNext == null){
return root;
}
return Min(root.leftNext);
}
/**
* 查找最大的節點
*/
public E Max(){
return Max(root).e;
}
private Node Max(Node root){
if (root == null){
return null;
}
if (root.rightNext == null){
return root;
}
return Max(root.rightNext);
}
@Override
public String toString(){
StringBuilder str = new StringBuilder();
generateString(root, 0, str);
return str.toString();
}
public void generateString(Node root, int depth, StringBuilder str){
if (root == null) {
str.append(generateDepth(depth) + "null\n");
return;
}
str.append(generateDepth(depth) + root.e + "\n");
generateString(root.leftNext, depth + 1, str);
generateString(root.rightNext, depth + 1, str);
}
public String generateDepth(int depth){
StringBuilder str = new StringBuilder();
for (int i = 0; i < depth; i++) {
str.append("--");
}
return str.toString();
}
}
深入了解前中後序周遊（深度優先周遊DFS）
前中後指的是通路根節點的順序，前序周遊第一次遇到該節點就列印，中序周遊第二次遇見該節點才列印，後序周遊則是第三次遇見該節點才列印
中序周遊相當于排序，可以列印出按順序排列的所有節點
後序周遊的應用：為二分搜尋樹釋放記憶體，隻有先釋放了子樹，才能釋放根節點
拓展：使用棧實作前序周遊的非遞歸寫法
public void preOrder(){
preOrder(root);
}
public void preOrder(Node root) {
/**
* 前序周遊，在每次彈出節點後，先後壓入自己的右子節點和左子節點
* 然後對棧頂節點，也就是左子節點執行相同的操作，直到所有的左子樹都周遊完了，再周遊右子樹
* 棧空了說明所有節點都周遊并且彈出了
*/
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node cur = stack.pop();
System.out.println(cur.e);
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
}
中序周遊和後序周遊的非遞歸實作更複雜，實際應用也不廣
層序周遊（廣度優先周遊BFS）
public void levelOrder(){
levelOrder(root);
}
public void levelOrder(Node root) {
/**
* 層序周遊，每次節點出隊後，先後将自己的左右子節點入隊
* 然後對隊首節點，也就是左子節點執行相同的操作，再讓左子節點的左右子節點入隊
* 隊列空了說明所有節點都周遊并且出隊了
*/
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node cur = queue.remove();
System.out.println(cur.e);
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}