Brooklyn College Library LibGuides Home: CISC 3130 Data Structures: Binary Trees

Introduction

Definition: A tree with at most two children for each node.

Ordered binary trees include Binary search trees, and Binary Heaps.

References

Black, Paul E. (201-12-15). Pieterse, Vreda; Black, Paul E. (eds.). "binary tree". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Retrieved from: https://www.nist.gov/dads/HTML/binarytree.html

Concept

We can also have ordered binary trees. Some of these include:

Binary Search Trees, where the left child has a smaller value than the parent and the right child has a larger value than the parent.

Heaps that only focus on parent child relationship. Most likely heap refers to a max binary heap or max heap, meaning the maximum value is at the root of the tree and children have smaller value than the parent. You can also have a min heap where the root is the minimum value.

Java Implementattion

:Binary trees are made of nodes. Each node has links to two child notes.

class Node {
    int value;      // data value
    Node child1;    // this node’s left child
    Node child2;    // this node’s right child
}

Binary trees have a pointer to the root

class Tree {
    private Node root;  
    // the only data field in Tree
    public void find(int data) {
    ...
    }
    public void insert(int id, double dd) {
    ...
    }
    public void delete(int id) {
    ...
    }
    // various other methods
} // end class Tree