Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » Principles of Object-Oriented Programming » Binary Tree Structure

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • OrangeGrove display tagshide tags

    This collection is included inLens: Florida Orange Grove Textbooks
    By: Florida Orange Grove

    Click the "OrangeGrove" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Rice Digital Scholarship

    This collection is included in aLens by: Digital Scholarship at Rice University

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

  • Bookshare

    This collection is included inLens: Bookshare's Lens
    By: Bookshare - A Benetech Initiative

    Comments:

    "Accessible versions of this collection are available at Bookshare. DAISY and BRF provided."

    Click the "Bookshare" link to see all content affiliated with them.

Also in these lenses

  • Busbee's Compter Science display tagshide tags

    This collection is included inLens: Busbee's Computer Science Lens
    By: Kenneth Leroy Busbee

    Comments:

    "Texas Common Course Numbering: COSC1337 or COSC1437"

    Click the "Busbee's Compter Science" link to see all content selected in this lens.

    Click the tag icon tag icon to display tags associated with this content.

  • eScience, eResearch and Computational Problem Solving

    This collection is included inLens: eScience, eResearch and Computational Problem Solving
    By: Jan E. Odegard

    Click the "eScience, eResearch and Computational Problem Solving" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Binary Tree Structure

Module by: Stephen Wong, Dung Nguyen. E-mail the authors

Summary: Explains the binary tree structure, and gives a sample implementation in Java, along with example tree algorithms.

Up until now, we have been organizing data in a "linear" fashion: one item after another. The corresponding data structures are the immutable scheme list (IList) and the mutable linear recursive structure (LRStruct). Now, suppose we want to model something like the following organization chart.

Figure 1
Figure 1 (graphics1.png)

A structure of data such as the above is called a tree. We first design a special kind of mutable tree structure called binary trees.

1. Binary Tree Object Model

Definition 1: Binary Tree
A (mutable) binary tree, BiTree, can be in an empty state or a non-empty state:
  • When it is empty, it contains no data.
  • When it is not empty, it contains a data object called the root element, and 2 distinct BiTree objects called the left subtree and the right subtree.

We implement the above object structure with a combination of state/composite/visitor patterns, in a manner analogous to LRStruct.

Below is the public interface of the binary tree framework. Click here for javadoc documentation.

Figure 2
Figure 2 (graphics2.png)

The implementation details are given in the following UML class diagram. Click here for javadoc documentation.

Figure 3
Figure 3 (graphics3.png)

2. Implementation Details

The code for BiTree is trivial, as it simply delegates most calls to its state, the root node. The real work is done in the state. The code for EmptyNode and DatNode for the most part are equally trivial. The insertion and removal of the root data of a BiTree require some work and need some explanation. When does it make sense to remove the root node from a (binary) tree? That is, when can one unambiguously remove the root node from a binary tree?

Clearly, when both subtrees of a root node are non-empty, then removing the root node is problematic. However, it makes sense to allow root removal when at least one of the subtrees is empty. Suppose one of the subtrees is empty, then BiTree.remRoot() will change the state of this BiTree to the state of the other subtree. For example, when the left subtree is empty, root removal of the parent tree will set the parent tree to its right subtree.

Figure 4
EmptyNodeDatNode
(a) EmptyNode(b) DatNode

/**
 * Asks the owner tree to set the root node to a new
 * DatNode containing dat,
 * resulting in a state change from empty to non-empty.
 * @param dat a given data Object.
 * @param owner the context of this state.
 */
void insertRoot(Object dat, BiTree owner) {
	owner.setRootNode(new DatNode(dat));
}

/**
 * Throws java.util.NoSuchElementException.
 * @param owner the BiTree holding this EmptyNode.
 */
Object remRoot (BiTree owner) {
	throw new NoSuchElementException ("EmptyNode.remRoot()");
}

/**
 * Calls algo's emptyCase() method to execute the algorithm algo.
 * @param owner the BiTree holding this EmptyNode.
 * @param algo an algorithm on owner.
 * @param inp the input algo needs.
 * @return the output for the emptyCase() of algo.
 */
Object execute(BiTree owner, IVisitor algo, Object... inp) {
	return algo.emptyCase (owner, inp);
}

/**
* Stores data and represents a non-empty state.
* @author Dung X. Nguyen - Copyright 2005 - All rights reserved.
*/
class DatNode extends ANode {
    /**
     * Data Invariant: != null.
     */
    private BiTree _leftTree = new BiTree ();

    /**
    * the stored data element.
    */
    private Object _dat;
    /**
    * Data Invariant: != null.
    */
    private BiTree _rightTree = new BiTree ();

    /**
    * Throws an IllegalStateException because the owner tree is not empty.
    * @exception IllegaStateException.
    */
    void insertRoot(Object dat, BiTree owner) {
        throw new IllegalStateException ("DatNode.insertRoot().");
    }

    /**
    * Removes and returns the root element from the owner tree by asking the
    * left subtree and, if necessary, the right subtree to help do the job.
    * The subtrees help determine whether or not the root element can be removed
    * by executing appropriate anonymous visitors.
    * @param owner the BiTree holding this DatNode.  Why is it final?
    * @exception IllegaStateException if both subtrees of owner are non-empty.
    */
    Object remRoot(final BiTree owner) {
        return _leftTree.execute(new IVisitor() {
            /**
             * The left subtree is empty. The parent tree can simply become the
             * right subtree.
             */
            public Object emptyCase(BiTree host, Object... notUsed) {
                owner.setRootNode(_rightTree.getRootNode());
                return _dat;
            }

            /**
             * The left subtree is not empty!  The right subtree must determine
             * whether or not the parent root can be removed.
             */
            public Object nonEmptyCase(BiTree host, Object... notUsed) {
                 return _rightTree.execute(new IVisitor() {

                    /**
                     * At this point both the lef and right subtrees are empty.
                     */
                    public Object emptyCase(BiTree h, Object... notUsed) {
                        owner.setRootNode(_leftTree.getRootNode());
                        return _dat;
                    }

                    /**
                    * Both left and right subtrees are not empty!  Cannot remove root.
                    */
                    public Object nonEmptyCase(BiTree h, Object... notUsed) {
                        throw new IllegalStateException ("Both subtrees are non-empty");
                    }
                });
            }
        });
    }

    /**
    * Calls algo's nonEmptyCase() method to execute the algorithm algo.
    * @param owner the BiTree holding this DatNode.
    * @param algo an algorithm on owner.
    * @param inp the input algo needs.
    * @return the output for the nonEmptyCase() of algo.
    */
    Object execute(BiTree owner, IVisitor algo, Object... inp) {
        return algo.nonEmptyCase (owner, inp);
    }
}

3. The Best Tree Printing Algorithm in Texas

Consider the binary tree displayed in the following "horizontal" manner:


                                               62                   
                                 _______________|_________________
                                |                                 |  
                               20                                 7
                           _____|____________               ______|______
                          |                  |             |             |
                         [ ]                 18           [ ]           [ ]
                                    _________|______
                                   |                |
                                   39              [ ]
                               _____|_____
                              |           |
                             [ ]         [ ]

Such horizontal display of a tree is not very convenient when the tree is wide. It is more convenient to display the tree in a "vertical" manner.

The following visitor and its helper print the above tree "vertically" as shown below:


62
|_ 20
| |_ []
| |_ 18
|    |_ 39
|    |  |_ []
|    |  |_ []
|    |_ []
|_ 7
   |_ []
   |_ []

Let's study the algorithm.

Figure 5
(a) (b)

/**
 * Computes a String representation of the binary tree host so
 * that it can be
 * printed vertically.
 * @author Dung X. Nguyen - Copyright 2005 - All rights reserved.
 */
public class ToString implements IVisitor {
   
    public final static ToString Singleton = new ToString ();
   
    private ToString () {
    }

   

    /**
     * Returns "[]", a String representation of an empty binary
     * tree.
     * @param host an empty binary tree.
     * @param nu not used.
     * @return String
    */
   
    public Object emptyCase(BiTree host, Object... nu) {
       
        return "[]";
    }

   

    /**
     * Computes a String representation of the binary tree host
     * so that it can be printed vertically. There is no '\n'
     * at the end of the String.  Passes appropriate leftmost
     * leading String to a
     * helper visitor to compute the
     * String representations of the left and right subtrees.
     * @param host a non-empty binary tree.
     * @param nu not used.
     * @return String
     */
   
    public Object nonEmptyCase(BiTree host, Object... nu) {
        String ls
        = (String)host.getLeftSubTree().execute(ToStringHelp.Singleton,
								"|  ");
       
        String rs
        = (String)host.getRightSubTree().execute(ToStringHelp.Singleton,
								"   ");
       
        return (host.getRootDat() + "\n" + ls + "\n" + rs);
       
        // EXERCISE FOR STUDENTS: Rewrite using anonymous inner classes.
    }
}

/**
 * Computes a String representation of the binary tree host so
 * that it can be printed vertically, given a leftmost leading
 * string for the two subtrees.
 * Called by ToString.
 * Should be implemented as an anonymous inner class in the
 * call by ToString.
 * @author Dung X. Nguyen - Copyright 2005 - All rights reserved.
 */
public class ToStringHelp implements IVisitor {
   
    public final static ToStringHelp Singleton = new ToStringHelp ();
   
    private ToStringHelp () {
    }

   

    /**
    * Returns "|_[]" to denote an empty tree subtree.
    * @param host an empty binary (sub)tree.
    * @param nu not used.
    * @return String
    */
   
    public Object emptyCase(BiTree host, Object... nu) {
       
        return "|_ []";
    }

   

    /**
    * Computes a String representation of the binary tree host
        * so that it can be printed vertically.
    * There is no '\n' at the end of the String.
    * @param host a non-empty binary (sub)tree.
    * @param leftLead[0] appropriate leftmost leading String to
       * help compute the
    * String representations of the left and right subtrees.
    * @return String
    */

   

    public Object nonEmptyCase(BiTree host, Object... leftLead) {
        String ls
            = (String)host.getLeftSubTree().execute(this, 
                                                
                                                
                                                leftLead[0] + "|  ");
               String rs
            = (String)host.getRightSubTree().execute(this,
      						leftLead[0] + "   ");
       
        return ("|_ " + host.getRootDat()+ "\n" +
                leftLead[0] + ls + "\n" +
                leftLead[0] + rs);
    }
}

Collection Navigation

Content actions

Download:

Collection as:

PDF | More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks