Star

数据结构：二叉树

Posted on | In |

本文是总结Tree这种结构的常用知识点，暂时总结Binary Tree。

Binary Tree二叉树

Why Tree?

因为树结合了其他数据结构的优势：

  • 顺序数组： 用Binary Search查找会很快。
  • 链表：插入和删除会非常快，不需要shift值。

基本概念：

  • 根： 树的顶部。
  • 父节点
  • 子节点
  • 叶节点：没有子节点的节点。
  • Leve（高度）：代表有几代。

平衡树和非平衡树

平衡树： 左右子树及其的高度相差<=1，并且左右子树也是平衡树。

Full Tree 和 Complete Tree：

  • Full Tree:每个节点都有0/2个子节点。
  • Complete Tree:除了最右边的节点，其他节点都是满节点，并且都靠左。

Binary Tree代码实现

Binary Tree Interface

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public interface BSTInterface {
    /**
     * Searches for the specified key in the tree.
     * @param key key of the element to search
     * @return boolean value indication of success or failure
     */
    boolean find(int key);
    /**
     * Inserts a new element into the tree.
     * @param key key of the element
     * @param value value of the element
     */
    void insert(int key, double value);
    /**
     * Deletes an element from the tree using the specified key.
     * @param key key of the element to delete
     */
    void delete(int key);
    /**
     * Traverses and prints values of the tree in ascending order based on key.
     */
    void traverse();
}

Binary Tree功能实现

  1. Find: 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    public boolean find(int key) {
        // tree is empty
        if (root == null) {
            return false;
        }
        Node curr = root;
        // while not found
        while (curr.key != key) {
            if (curr.key < key) {
                // go right
                curr = curr.right;
            } else {
                // go left
                curr = curr.left;
            }
            // not found
            if (curr == null) {
                return false;
            }
        }
        return true; // found
    }

  2. Insert 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    public void insert(int key, double value) {
        Node newNode = new Node(key, value);
        // empty tree
        if (root == null) {
            root = newNode;
            return;
        }
        Node parent = root; // keep track of parent
        Node curr = root;
        while (true) {
            // no duplicate keys allowed
            // simply keep the existing one here
            if (curr.key == key) {
                return;
            }
            parent = curr; // update parent
            if (curr.key < key) {
                // go right
                curr = curr.right;
                if (curr == null) {
                    // found a spot
                    parent.right = newNode;
                    return;
                }
            } else {
                // go left
                curr = curr.left;
                if (curr == null) {
                    // found a spot
                    parent.left = newNode;
                    return;
                }
            } // end of if-else to go right or left
        } // end of while
    } // end of insert method

  3. Delete 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    public void delete(int key) {
        // empty tree
        if (root == null) {
            return;
        }
        Node parent = root;
        Node curr = root;
        /*
         * flag to check left child
         *
         * need this flag because actual deletion process happens after the
         * while loop that is to find the key to delete
         */
        boolean isLeftChild = true;
        while (curr.key != key) {
            parent = curr; // update parent first
            if (curr.key < key) { // go right
                isLeftChild = false;
                curr = curr.right;
            } else { // go left
                isLeftChild = true;
                curr = curr.left;
            }
            // case 1: not found
            if (curr == null) {
                return;
            }
        }
        if (curr.left == null && curr.right == null) {
            // case 2: leaf
            if (curr == root) {
                root = null;
            } else if (isLeftChild) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        } else if (curr.right == null) {
            // case 3: no right child
            if (curr == root) {
                root = curr.left;
            } else if (isLeftChild) {
                parent.left = curr.left;
            } else {
                parent.right = curr.left;
            }
        } else if (curr.left == null) {
            // case 3: no left child
            if (curr == root) {
                root = curr.right;
            } else if (isLeftChild) {
                parent.left = curr.right;
            } else {
                parent.right = curr.right;
            }
        } else {
            // case 4: with two children
            // here we use successor but using predecessor is also an option
            Node successor = getSuccessor(curr);
            if(curr == root) {
                root = successor;
            } else if(isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = curr.left;
        }
    }

  4. 找到下一个节点 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    /**
     * Helper method to find the successor of the toDelete node.
     * This tries to find the smallest value of the right subtree
     * of the toDelete node by going down to the left most node in the subtree
     * @param toDelete node to delete
     * @return the successor of the toDelete node
     */
    private Node getSuccessor(Node toDelete) {
        Node successorParent = toDelete;
        Node successor = toDelete;
        // start the search from the root of the right subtree
        Node curr = toDelete.right;
        // move down to left as far as possible in the right subtree
        // successor's left child must be null
        while (curr != null) {
            successorParent = successor;
            successor = curr;
            curr = curr.left;
        }
        /*
         * If successor is NOT the right child of the node to delete, then
         * need to take care of two connections in the right subtree
         */
        if (successor != toDelete.right) {
            successorParent.left = successor.right;
            successor.right = toDelete.right;
        }
        return successor;
    }

  5. Traverse Binary Tree: 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public void traverse() {
        inOrderHelper(root);
        System.out.println();
    }
    private void inOrderHelper(Node toVisit) {
        if(toVisit != null) {
            inOrderHelper(toVisit.left);
            System.out.print(toVisit);
            inOrderHelper(toVisit.right);
        }
    }

Reference: @Terry Lee