天天看點
傳回

資料結構與算法系列——二叉查找樹

資料結構與算法系列（1）

    • 1、查找樹ADT——二叉查找樹
      • 1.1 類的整體定義
      • 1.2 節點定義 BinaryNode
      • 1.2 判斷是否存在 contains()
      • 1.3 插入元素 insert()
      • 1.4 删除元素 remove()
      • 1.5 測試代碼
      • 1.6 完整代碼 BinarySearchTree

1、查找樹ADT——二叉查找樹

性質：對于二叉查找樹中的任意節點X，它的左子樹中所有項中的值小于X中的項，而它的右子樹中所有項中的值大于X中的項。

平均深度：O(log N)

資料結構與算法系列——二叉查找樹

1.1 類的整體定義 

/**
 * @ClssName：BinarySearchTree.java
 * @Description：
 * @createtime：2021/4/9 3:38 下午
 * @author：Joker
 */
public class BinarySearchTree<T extends Comparable<? super T>> {
    public static class BinaryNode<T> {
        // ... ...
    }

    private BinaryNode<T> root;

    public BinarySearchTree() {
        root = null;
    }

    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public boolean contains(T t) {
        // ... ...
    }

    public T findMin() {
        // ... ...
    }

    public T findMax() {
        // ... ...
    }

    public void insert(T t) {
        // ... ...
    }

    public void remove(T t) {
        // ... ...
    }

    public void printTree() {
        // ... ...
    }
}

1.2 節點定義 BinaryNode 

public static class BinaryNode<T> {
    T element;
    BinaryNode<T> left;
    BinaryNode<T> right;

    BinaryNode(T element) {
      this.element = element;
    }

    BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
      this.element = element;
      this.left = left;
      this.right = right;
    }
}

1.2 判斷是否存在 contains()

利用遞歸查找是否包含元素，很簡單 
private boolean contains(T t, BinaryNode<T> node) {
  // 邊界驗證
  if (node == null) {
    return false;
  }

  int compareResult = t.compareTo(node.element);
  if (compareResult > 0) {
    return contains(t, node.right);
  } else if (compareResult < 0) {
    return contains(t, node.left);
  } else {
    return true;
  }
}

1.3 插入元素 insert()

遞歸周遊，(插入元素比節點值)小了往左，大了往右，直到遇到葉子節點 
public void insert(T t) {
  this.root = insert(t, root);
}

private BinaryNode<T> insert(T t, BinaryNode<T> node) {
  if (node == null) {
    return new BinaryNode<T>(t);
  }

  int compare = t.compareTo(node.element);
  if (compare < 0) {
    node.left = insert(t, node.left);
  } else if (compare > 0) {
    node.right = insert(t, node.right);
  } else {
    // 相同元素，什麼都不做
  }

  return node;
}

1.4 删除元素 remove()

  1. 如果删除的節點是樹葉，則直接删除即可
  2. 如果删除的節點有一個子節點，則可以操作此節點的父節點的指向此節點的子節點，以達到删除的目的
  3. 如果删除的節點有兩個子節點，則從右子樹中擷取到最小的值，取代需要删除的節點值，然後直接删除右子樹最小的值即可。 
public void remove(T t) {
  	this.root = remove(t, root);
}

private BinaryNode<T> remove(T t, BinaryNode<T> node) {
    if (node == null) {
      return node;
    }

    int compareResult = t.compareTo(node.element);
    if (compareResult < 0) {
      node.left = remove(t, node.left);
    } else if (compareResult > 0) {
      node.right = remove(t, node.right);
    } else if (node.left != null && node.right != null) {
      // 當删除的節點存在左右雙子樹的時候，取其子樹最小的元素與其交換，然後删除最小的元素（轉換成删除非雙子節點）
      node.element = findMin(node.right).element;
      node.right = remove(node.element, node.right);
    } else {
      node = (node.left != null) ? node.left : node.right;
    }

    return node;
}

1.5 測試代碼 

public class BinarySearchTreeTest {
    @Test
    public void test() {
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
        binarySearchTree.insert(6);
        binarySearchTree.insert(2);
        binarySearchTree.insert(5);
        binarySearchTree.insert(7);
        binarySearchTree.insert(9);
        binarySearchTree.insert(1);
        binarySearchTree.insert(3);

        System.out.println("===>" + binarySearchTree.contains(7));
        binarySearchTree.remove(2);
        System.out.println("===>" + binarySearchTree.contains(2));
        System.out.println("===>" + binarySearchTree.contains(1));

    }
}

1.6 完整代碼 BinarySearchTree 

package com.tree.adt;
/**
 * @ClssName：BinarySearchTree.java
 * @Description：
 * @createtime：2021/4/9 3:38 下午
 * @author：Joker
 */
public class BinarySearchTree<T extends Comparable<? super T>> {
    public static class BinaryNode<T> {
        T element;
        BinaryNode<T> left;
        BinaryNode<T> right;

        BinaryNode(T element) {
            this.element = element;
        }

        BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }
    }

    private BinaryNode<T> root;

    public BinarySearchTree() {
        root = null;
    }

    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public boolean contains(T t) {
        return contains(t, root);
    }

    public T findMin() {
        if (isEmpty()) {
            return null;
        }

        return findMin(root).element;
    }

    public T findMax() {
        if (isEmpty()) {
            return null;
        }

        return findMax(root).element;
    }

    public void insert(T t) {
        this.root = insert(t, root);
    }

    public void remove(T t) {
        this.root = remove(t, root);
    }

    public void printTree() {
        printTree(root);
    }

    private BinaryNode<T> insert(T t, BinaryNode<T> node) {
        if (node == null) {
            return new BinaryNode<T>(t);
        }

        int compare = t.compareTo(node.element);
        if (compare < 0) {
            node.left = insert(t, node.left);
        } else if (compare > 0) {
            node.right = insert(t, node.right);
        } else {
            // do nothing
        }

        return node;
    }

    /**
     * 查找二叉樹的最大值一定在右子樹上
     *
     * @param node 初始節點
     * @return
     */
    private BinaryNode<T> findMax(BinaryNode<T> node) {
        if (node == null) {
            return null;
        } else if (node.right == null) {
            return node;
        }

        return findMax(node.right);
    }

    /**
     * 查找二叉樹的最小值一定在左子樹上
     *
     * @param node 初始節點
     * @return
     */
    private BinaryNode<T> findMin(BinaryNode<T> node) {
        if (node == null) {
            return null;
        } else if (node.left == null) {
            return node;
        }

        return findMax(node.left);
    }

    private void printTree(BinaryNode<T> node) {}

    /**
     * 1. 如果删除的節點是樹葉，則直接删除即可
     * 2. 如果删除的節點有一個子節點，則可以操作此節點的父節點的指向此節點的子節點，以達到删除的目的
     * 3. 如果删除的節點有兩個子節點，則從右子樹中擷取到最小的值，取代需要删除的節點值，然後直接删除右子樹最小的值即可。
     *
     * @param t
     * @param node
     * @return
     */
    private BinaryNode<T> remove(T t, BinaryNode<T> node) {
        if (node == null) {
            return node;
        }

        int compareResult = t.compareTo(node.element);
        if (compareResult < 0) {
            node.left = remove(t, node.left);
        } else if (compareResult > 0) {
            node.right = remove(t, node.right);
        } else if (node.left != null && node.right != null) {
            // 當删除的節點存在左右雙子樹的時候，取其子樹最小的元素與其交換，然後删除最小的元素（轉換成删除非雙子節點）
            node.element = findMin(node.right).element;
            node.right = remove(node.element, node.right);
        } else {
            node = (node.left != null) ? node.left : node.right;
        }

        return node;
    }

    /**
     * 使用遞歸查找是否包含元素，很簡單
     *
     * @param t
     * @param node
     * @return
     */
    private boolean contains(T t, BinaryNode<T> node) {
        // 邊界驗證
        if (node == null) {
            return false;
        }

        int compareResult = t.compareTo(node.element);
        if (compareResult > 0) {
            return contains(t, node.right);
        } else if (compareResult < 0) {
            return contains(t, node.left);
        } else {
            return true;
        }
    }
}
本文根據《資料結構與算法分析：Java語言描述（原書第3版）.[美]Mark Allen Weiss》進行代碼編寫，如有什麼問題，歡迎留言
資料結構-樹 算法 資料結構 二叉樹 java 平衡二叉樹
上一篇: Leetcode-标簽為Tree 110. Balanced Binary Tree
下一篇: 資料結構之平衡二叉樹（AVL樹）

繼續閱讀