Star

数据结构:二叉树

本文是总结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