Binary Tree Introduction - 二叉树简介

Made by Mike_Zhang

---

数据结构与算法主题：

---

1. Introduction

I’ve discussed the general tree in the last post. Now it is time to talk about a more specific type of tree: the binary tree.

Binary is a ordered tree, where ordered tree means that there is a meaningful linear order among the children of each node, like left and right, first and second, previous and next, etc.

1.1 Binary Tree Definition

General Definition:
Binary tree is a ordered tree such that:

• The maximum number of children of any node is 2.
• Each child node is called either left or right node.
• Regrading the order of the children nodes, left node precedes the right node.

Recursive Definition:
A binary tree is:

• An empty tree, or
• A nonempty tree with a root node $r$ storing an element $e$, and two sub binary tree rooted at $r$ which are left subtree and right subtree respectively (subtree can be empty as well).

---

1.2 Binary Tree Properties

• left subtree: a subtree rooted at the left child of a internal node;
• right subtree: a subtree rooted at the right child of a internal node;
• proper binary tree (full binary tree) : each node has zero or two children, which means each internal node has both left and right node.
• improper binary tree: a binary tree that is not proper (bullshit, of course… :D)

---

2. Binary Tree ADT

Since a binary tree is a special type of tree, we can define a binary tree ADT by inheriting from the general tree ADT with few new methods added on:

• left(p): Return the position of the left child of the node p, null if p is a leaf node;
• right(p): Return the position of the right child of the node p, null if p is a leaf node;
• sibling(p): Return the position of the sibling of the node p, null if p has no sibling;

---

2.1 Binary Tree Interface in Java

Java Implementation:

(Tree interface imported from last post)

public interface BinaryTree<E> extends Tree<E> {
    Position<E> left(Position<E> p) throws IllegalArgumentException;
    Position<E> right(Position<E> p) throws IllegalArgumentException;
    Position<E> sibling(Position<E> p) throws IllegalArgumentException;
}

---

3. Abstract Binary Tree Base Class

Based on the Abstract Tree Base Class in th last post, we can define the Abstract Binary Tree Base Class by inheriting, as well as implementing the BinaryTree interface partially. Some methods in the BinaryTree interface are trivial, including sibling(p), numChildren(), and children(p), which can be implemented in the Abstract Tree Base Class, ans leave other high-level methods empty.

Java Implementation:

(AbstractTree abstract class imported from last post)

public abstract class AbstractBinaryTree<E> extends AbstractTree<E> implements BinaryTree<E> {
    public Position<E> sibling(Position<E> p) {
        Position<E> parent = parent(p);
        if (parent == null) return null;
        if (p == left(parent)) {
            return right(parent);
        }
        else {
            return left(parent);
        }
    }
    public int numChildren(Position<E> p) {
        int count = 0;
        if (left(p) != null) count++;
        if (right(p) != null) count++;
        return count;
    }

    public Iterable<Position<E>> children(Position<E> p) {
        List<Position<E>> snapshot = new ArrayList<Position<E>>(2);
        if (left(p) != null) snapshot.add(left(p));
        if (right(p) != null) snapshot.add(right(p));
        return snapshot;
    }
}

---

4. Binary Tree Implementation

There are two popular implementations of binary tree: Linked Structure and Array-based Structure.

4.1 Linked Structure Implementation

1. This implementation first defines the Node inner class to represent a node in a binary tree, which maintains the some references to its contained element, its parent node, its left child, and its right child;

2. Then the Binary Tree class maintains a node reference to the root, as well as a integer variable to count the number of nodes in the tree;

3. Finally are the utility methods, including constructor, accessor methods, update method, and methods for traversing.

Java Implementation:

public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> {

    // --- Inner Node class implements Position<E> ---
    protected static class Node<E> implements Position<E> {
        private E element;
        private Node<E> left;
        private Node<E> right;
        private Node<E> parent;

        public Node(E inElement, Node<E> inLeft, 
                Node<E> inRight, Node<E> inParent) {
            element = inElement;
            left = inLeft;
            right = inRight;
            parent = inParent;
        }

        public E getElement() {
            return element;
        }

        // Getters
        public Node<E> getParent() {
            return parent;
        }

        public Node<E> getLeft() {
            return left;
        }

        public Node<E> getRight() {
            return right;
        }

        // Setters
        public void setElement(E inElement) {
            element = inElement;
        }

        public void setParent(Node<E> inParent) {
            parent = inParent;
        }

        public void setLeft(Node<E> inLeft) {
            left = inLeft;
        }

        public void setRight(Node<E> inRight) {
            right = inRight;
        }
    }
    // --- End of inner Node class ---

    // --- Only two fields inside the Tree class ---
        // 1. reference to the root node
    protected Node<E> root;

        // 2. Variable of tree size
    private int size;

    // --- Constructor for empty tree ---
    public LinkedBinaryTree() {
        root = null;
        size = 0;
    }

    // --- accessor methods ---
    public Position<E> root() {
        return root;
    }

    public int size() {
        return size;
    }

    // Used to check Node's validity before returning it
    protected Node<E> validate(Position<E> p) 
                        throws IllegalArgumentException {
        if (!(p instanceof Node)) {
            throw new 
            IllegalArgumentException("Not valid position type");
        }
        Node<E> node = (Node<E>) p; // safe cast !!!
        if (node.getParent() == null) {
            throw new 
            IllegalArgumentException("Position no longer in the tree");
        }
        return node;
    }

    // Return the Position of the parent of Position p, 
    // cast Position to Node first using validate()
    public Position<E> parent(Position<E> p) 
                        throws IllegalArgumentException {
        Node<E> node = validate(p);
        return node.getParent();
    }

    // Return the Position of the left child of Position p, 
    // cast Position to Node first using validate()
    public Position<E> left(Position<E> p) 
                        throws IllegalArgumentException {
        Node<E> node = validate(p);
        return node.getLeft();
    }

    // Return the Position of the right child of Position p, 
    // cast Position to Node first using validate()
    public Position<E> right(Position<E> p) 
                        throws IllegalArgumentException {
        Node<E> node = validate(p);
        return node.getRight();
    }

    // --- update methods ---
    protected Node<E> createNode(E inElement, Node<E> inParent, 
                                Node<E> inLeft, Node<E> inRight) {
        return new Node<E>(inElement, inLeft, inRight, inParent);
    }

    public Position<E> addRoot(E e) throws IllegalStateException {
        if (!isEmpty()) {
            throw new IllegalStateException("Tree is not empty");
        }
        root = new Node<E>(e, null, null, null);
        size = 1;
        return root;
    }

    public Position<E> addLeft(Position<E> p, E e) 
                        throws IllegalArgumentException {
        Node<E> parent = validate(p);
        if (parent.getLeft() != null) {
            throw new 
            IllegalArgumentException("Left child already exists");
        }
        Node<E> leftChild = createNode(e, parent, null, null);
        parent.setLeft(leftChild);
        size++;
        return leftChild;
    }

    public Position<E> addRight(Position<E> p, E e) 
                        throws IllegalArgumentException {
        Node<E> parent = validate(p);
        if (parent.getRight() != null) {
            throw new 
            IllegalArgumentException("Right child already exists");
        }
        Node<E> rightChild = createNode(e, parent, null, null);
        parent.setRight(rightChild);
        size++;
        return rightChild;
    }

    // Replace the element at Position p with e and 
    // return the replaced element
    public E set (Position<E> p, E e) throws IllegalArgumentException {
        Node<E> node = validate(p);
        E temp = node.getElement();
        node.setElement(e);
        return temp;
    }

    public void attach(Position<E> p, LinkedBinaryTree<E> ta, 
                LinkedBinaryTree<E> tb) throws IllegalArgumentException {
        Node<E> node = validate(p);
        if (isInternal(p)) {
            throw new IllegalArgumentException("p is not a leaf!");
        }
        size += (ta.size() + tb.size());
        if (!ta.isEmpty()) {
            node.setLeft(ta.root);
            ta.root.setParent(node);
            ta.root = null;
            ta.size = 0;
        }
        if (!tb.isEmpty()) {
            node.setRight(tb.root);
            tb.root.setParent(node);
            tb.root = null;
            tb.size = 0;
        }
    }

    public E remove(Position<E> p) 
                throws IllegalArgumentException {
        Node<E> node = validate(p);
        if (numChildren(p) == 2) {
            throw new IllegalArgumentException("p has two children");
        }
        Node<E> child = 
        (node.getLeft() != null) ? node.getLeft() : node.getRight();
        // 1. p is a leaf
        if (child != null) {
            child.setParent(node.getParent());
        }
        // 2. p is the root
        if (isRoot(p)) {
            root = child;
        }
        // 3. p is internal with only one child
        else {
            Node<E> parent = node.getParent();
            if (node == parent.getLeft()) {
                parent.setLeft(child);
            } else {
                parent.setRight(child);
            }
        }
        size--;
        E result = node.getElement();
        node.setElement(null); // GC
        node.setLeft(null); // GC
        node.setRight(null); // GC
        node.setParent(node);
        return result;
    }

    // --- traversal methods ---
    public Iterator<E> iterator() {
        // will discuss and be implemented soon...
        return null;
    }

    public Iterable<Position<E>> positions() {
        // will discuss and be implemented soon...
        return null;
    }
}

---

4.2 Linked Structure Performance

Linked structure implementation deals with references instead of traversing and shifting. Thus, it has a good performance on most of the operations.

Method	Run time
size() isEmpty()	$O(1)$
root() parent() left() right() sibling() children() numChildren()	$O(1)$
isExternal() isInternal() isRoot()	$O(1)$
addRoot() addLeft() addRight() attach() remove() set()	$O(1)$

---

5. Outro

Besides, Binary Tree interface can be implemented by Array as well, which maintains a mathematical relationship between the position and the index. I will discuss it in the later section.

We still have the iterator() and positions() methods left empty. In following sections, we will discuss the binary tree traversals and their implementations accordingly. See you next time!

---

References

Goodrich, M., Tamassia, R., & O’reilly, A. (2014). Data Structures and Algorithms in Java, 6th Edition. John Wiley & Sons.

---

写在最后

Binary Tree 相关的知识会继续学习，继续更新.
最后，希望大家一起交流，分享，指出问题，谢谢！

---

原创文章，转载请标明出处
Made by Mike_Zhang

感谢你的支持