Skip to Main Content
It looks like you're using Internet Explorer 11 or older. This website works best with modern browsers such as the latest versions of Chrome, Firefox, Safari, and Edge. If you continue with this browser, you may see unexpected results.
| Brooklyn College Library & Academic IT |CISC Department

CISC 3130 Data Structures: Binary Trees

Professor Chuang Spring 2020 OER

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

Binary Tree

 

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