Trees

you are watching: Trees here hiddentracks.org

ADT: BINARY
SEARCH TREES

TOPICS

·  Trees – Terminology

·  ADT Binary Tree: Definitions,
Java Implementation

 

OUTLINE

1. Trees –
Terminology

 

·      
Data
structures with components arranged in linear form (unique first component and
unique last component, every other component has a unique predecessor and a
unique successor): arrays, lists, stacks, queues.

·      
Data
structures with components arranged in hierarchical form (hierarchy = nonlinear
structure in which each component may have several successors): trees.
Intuitively, hierarchical means that a “parent-child” relationship
exists between the nodes in the tree.

·      
Hierarchical
forms real-life examples: a family tree, the biological classification system, business
organization charts (department, division, group, subsidiary), etc.

·      
Definition:
Tree = a hierarchical structure in which each component, except the
topmost, is immediately beneath exactly one other component (each component may
have several successors but only one predecessor).

Definitions for terms used with general trees:

  • Nodes = vertices (tree components). Every node (except the
    root) has a unique parent. Type of nodes:
    • Root = starting (topmost)
      node in the tree. It is the only node in the tree that has no parent.
    • Internal node = a node
      with children
    • Leaf = a node without
      children. A tree must have only one root and must branch out to all
      leaves.
  • Edges = branches (lines between the nodes). Directed edges
    from parent to child.
  • Parent = The node immediately above another node
  • Parenthood relationship (ancestor and
    descendant): {a, b} an edge between nodes a and
    b and a is above node b in the tree 
    à a = parent (ancestor), b = child
    (descendant). The root has no parent. The root of any tree is an ancestor
    of every node in that tree.
  • Left child = The node to the left of another node in a tree
  • Right child = The node to the right of another node in a tree
  • Children of the same parent are called siblings.
  • A subtree in a tree is any node in the tree
    together with all of its descendants. A subtree is a tree by itself but is
    also part of a larger tree. Recursive definition:
  1. The
    empty tree is a subtree of any tree.
  2. Any
    node of a tree, together with all its descendants, is a subtree.
  • A subtree of a node n is a subtree rooted at a
    child of n.
  • Left subtree = A set of nodes to the left of a node in a tree
  • Right subtree = A set of nodes to the right of a node in a tree
  • Level (node) – The level of the root is defined to be 0, and the
    level of any other node is one more than the level of its parent.
  • Degree (node) = # of children.
  • Degree (tree) = max degree (all nodes).
  • Path = sequence of nodes n1, n2,
    ……
    , nk such that niis the parent of ni +1 for all 1 <= i <= k.
  • Length (path) = # of edges on the path
  • Height (node) = length of the longest path from node to a leaf.
  • Height (tree) = height (root). We could also define the height of a
    tree as being the maximum value of the levels of its leaves.
  • Now,
    we could reconsider the following recursive definition of a tree:

    1. A collection of no nodes is a tree (empty tree).
    2. Any single node is itself a tree.
    3. Given several trees and a separate node, the result of
      making each original root a child of the new node is a tree.

    2. ADT: Binary Tree
     

    ·      
    [Definition] Binary tree = a tree
    in which each node has at most 2 children (0, 1, or 2 children). The 2 children
    of a node have special names: the left child, and the right child. A
    parent can have at most one left child and one right child. In a binary tree, a
    unique path exists from the root to every other node.

    ·      
    Every
    node in a binary tree has two sets of nodes called the left subtree and right
    subtree which are also binary trees.

    ·      
    Possible
    configurations:

     

    Description: C:Courses-NOWWebpage237LectureNotesimage9GT.JPG

    ·      
    Structure
    of a node:

    Description: C:Courses-NOWWebpage237LectureNotesimageMUJ.JPG

    ·      
    We
    will have a class that represents each node in a binary tree (
    BinaryTreeNode), and this is going to be
    inner class defined inside the
    BinaryTree class. In our
    implementation, instance variables of the class
    BinaryTreeNode are:

    o   info: stores the information part
    of the node

    o   lLink: points to the root node of
    the left subtree

    o   rLink: points to the root node of
    the right subtree

    ·      
    Tree
    traversal:
    Algorithm
    for processing or visiting every node exactly once. “Visiting” a node
    means “doing something with or to” the node. There are many different
    ways to do a tree traversal, but we generally prefer recursive approaches.
    Traversal of a binary tree visits the tree’s nodes in one of 3 different
    orders:

    ·      
     Inorder traversal (LeftNodeRight):
    visit all nodes in the left subtree of of the node,
    visit the node, visit all nodes in the right subtree
    of the node. Used to print in alphabetical order (sorted order)


    Algorithm (recursive):

    if
    tree is not NULL


        InOrder(Left(tree))
        VisitNode(tree)
        InOrder(Right(tree))

    Java code:

    public
    void inOrderTraversal() {

        inOrder(root);
    }

    //helper method called by inOrderTraversal
    private void inOrder(BinaryTreeNode<T> t)  {
        if (t != null)  {
            inOrder(t.lLink);
            System.out.print(t.info + ” “);
            inOrder(t.rLink);
        }
    }

    ·      
    Postorder traversal (LeftRightNode): visit all nodes in the left subtree of the node, visit all
    nodes in the right subtree of the node, visit the node. Visits leaves first
    (good for deletion)


    Algorithm (recursive):

    if
    tree is not NULL


        PostOrder(Left(tree))
        PostOrder(Right(tree))
        VisitInfo(tree)

    Java code:

    public
    void postOrderTraversal() {

        postOrder(root);
    }

       
    //helper method called by postOrderTraversal

        private void postOrder(BinaryTreeNode<T> t) {
            if (t != null) {
               
    postOrder(t.lLink);

               
    postOrder(t.rLink);

               
    System.out.print(t.info + ” “);

            }
        }

    ·      
    Preorder traversal (NodeLeftRight): visit the node, visit all
    nodes in the left subtree of the node, visit all nodes in the right subtree of
    the node. Useful with binary trees (not BST)


    Algorithm (recursive):

    if
    tree is not NULL


        Visit Info(tree)
        PreOrder(Left(tree))
        PreOrder(Right(tree))

    Java code:

    public
    void preOrderTraversal() {

        preOrder(root);
    }

    //helper method called by preOrderTraversal
    private void preOrder(BinaryTreeNode<T> t) {
        if (t != null) {
            System.out.print(t.info + ” “);
            preOrder(t.lLink);
            preOrder(t.rLink);
        }
    }

    Description: C:Courses-NOWWebpage237LectureNotesimage35G.JPG

     

    ·      
    Binary
    Tree ADT – Java implemetation

    //Interface: BinaryTreeADT
    public interface BinaryTreeADT<T>
    extends Cloneable {

        public Object clone(); //Returns a clone of this BT.
        public boolean isEmpty();//Method to determine
    whether the BT is empty.

        public void inOrderTraversal();//Method to do an inorder
    traversal of a BT.


        public void preOrderTraversal();//Method to do a preorder traversal of a BT.
        public void postOrderTraversal();//Method to do a postorder
    traversal of a BT.


        public int treeHeight(); //Method to
    determine the height of a BT.

        public int treeNodeCount();//Method to
    find the number of nodes in a binary tree.

        public int treeLeavesCount();//Method to
    determine the number of leaves in a BT.

        public void destroyTree();
    //Method to destroy a BT.

        public boolean
    search(T item); //Method to determine whether item
    is in a BT.


        public void insert(T item); //Method to insert item in a BT.
        public void delete(T item);//Method to delete item from a BT.
    }

    //Class:
    BinaryTree implements

    //Interface:
    BinaryTreeADT

    //Inner
    class:
    BinaryTreeNode
    import java.util.NoSuchElementException;
    public abstract class BinaryTree<T> implements BinaryTreeADT<T>
    {

       
    //Definition of the BinaryTreeNode class

       
    protected class BinaryTreeNode<T> {

           
    public T info;

           
    public BinaryTreeNode<T> lLink;


           
    public BinaryTreeNode<T> rLink;

           
    //Default constructor

           
    public BinaryTreeNode() {

               
    info = null;

               
    lLink = null;

               
    rLink = null;

           
    }

           
    //Alternate constructor

           
    public BinaryTreeNode(T item) {

               
    info = item;

               
    lLink = null;

               
    rLink = null;

           
    }

           
    //Alternate constructor

           
    public BinaryTreeNode(T item, BinaryTreeNode<T>
    left, BinaryTreeNode<T> right) {

               
    info = item;

               
    lLink = left;

               
    rLink = right;

           
    }

           
    public Object clone() {

               
    BinaryTreeNode<T> copy = null;

               
    try {

                
    copy = (BinaryTreeNode<T>) super.clone();


               
    }

               
    catch (CloneNotSupportedException e) {

                   
    return null;

               
    }

               
    return copy;

           
    }

           
    public String toString() {


               
    return info.toString();

           
    }

        }

       
    //Instance variable vor class BinaryTree


       
    protected BinaryTreeNode<T> root;

       
    //Default constructor

       
    public BinaryTree() {

           
    root = null;

        }

        public Object clone() {
           
    BinaryTree<T> copy = null;

           
    try {

               
    copy = (BinaryTree<T>) super.clone();


           
    }

           
    catch (CloneNotSupportedException e) {

               
    return null;

           
    }

           
    if (root != null)

               
    copy.root = copyTree(root);


           
    return copy;

        }

       
    //helper method called by clone

       
    private BinaryTreeNode<T> copyTree(BinaryTreeNode<T>
    otherTreeRoot) {

           
    BinaryTreeNode<T> temp;

           
    if (otherTreeRoot == null)

               
    temp = null;

           
    else {

               
    temp = (BinaryTreeNode<T>) otherTreeRoot.clone();


               
    temp.lLink = copyTree(otherTreeRoot.lLink);

               
    temp.rLink = copyTree(otherTreeRoot.rLink);

           
    }

           
    return temp;

        }

        public boolean isEmpty()
    {

           
    return (root == null);

        }

        public void inOrderTraversal() {

           
    inOrder(root);

        }

       
    //helper method called by inOrderTraversal

       
    private void inOrder(BinaryTreeNode<T> t) 
    {

           
    if (t != null)  {

               
    inOrder(t.lLink);

               
    System.out.print(t.info + ” “);

               
    inOrder(t.rLink);

           
    }

        }

        public void preOrderTraversal() {

           
    preOrder(root);

        }

       
    //helper method called by preOrderTraversal

       
    private void preOrder(BinaryTreeNode<T> t) {


           
    if (t != null) {

               
    System.out.print(t.info + ” “);

               
    preOrder(t.lLink);

               
    preOrder(t.rLink);

           
    }

        }

        public void postOrderTraversal() {

           
    postOrder(root);

        }

       
    //helper method called by postOrderTraversal

       
    private void postOrder(BinaryTreeNode<T> t) {


           
    if (t != null) {

               
    postOrder(t.lLink);

               
    postOrder(t.rLink);

               
    System.out.print(t.info + ” “);

           
    }

        }

        public int treeHeight()
    {

           
    return height(root);

        }

       
    //helper method called by treeHeight

       
    private int height(BinaryTreeNode<T> t) {

           
    if (t == null)

               
    return 0;

           
    else if (t.lLink == null && t.rLink == null)

               
    return 0;

           
    else

               
    return 1 + Math.max(height(t.lLink),
    height(t.rLink));

        }

        public int treeNodeCount() 
    {

           
    return nodeCount(root);

        }

       
    //helper method called by treeNodeCount

       
    private int nodeCount(BinaryTreeNode<T> t) {


           
    System.out.println(“To be done later.”);


           
    return 0;

        }

        public int treeLeavesCount()
    {

           
    return leavesCount(root);

        }

       
    //helper method called by treeLeavesCount

       
    private int leavesCount(BinaryTreeNode<T> t) 
    {

           
    System.out.println(“To be done later.”);


           
    return 0;

        }

        public void destroyTree() {

           
    root = null;

        }

       
    //abstract methods

       
    public abstract boolean search(T
    item);

       
    public abstract void insert(T item);

       
    public abstract void delete(T item);

    }

    Additional Resources:
    1. Tree traversal demo (animation): http://nova.umuc.edu/~jarc/idsv/lesson1.html

    2. BST operations: http://simpleprogrammingtutorials.com/tutorials/bst-overview.php

    3. BST: http://en.wikipedia.org/wiki/Binary_search_tree

    4. BST Tree Applet (Kubo Kovac):  http://people.ksp.sk/~kuko/bak/index.html

    References:
    [1] Java Programming: From Problem Analysis to Program Design, by D.S. Malik,
    Thomson Course Technology, 2008
    [2] C++ Plus Data Structures, third edition, by Nell Dale, Jones and Bartlett
    Publishers, 2003.


     
     
     

    View more information: http://orion.towson.edu/~izimand/237/LectureNotes/8-Lecture-Trees-1.htm

    See more articles in category: Grammar
    READ:  42 arts and culture events to attend this spring

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    Back to top button