TREE DATA STRUCTURES

1. Introduction
2. Example

1. INTRODUCTION

Tree are a very common form of data structure often used in programming. A tree comprises an arrangement of nodes each of which holds information. Nodes are linked by arcs (or edges). At its simplest each node in a tree has two nodes descending from it down to the bottom most nodes (the leaf node) which have no nodes eminating from them. Such a tree is called a binary tree. The top most node is the root node; all other nodes which are not leaf nodes are then body nodes.

Trees can also be considered in terms of the labelling used to describe "familly trees", i.e. we think of child nodes, parent nodes, sibling nodes, etc.

To create a tree we can adopt a similar approach to that used to produce linked lists --- a linked list can be tghoyght of as a tree where each node has only one child node descending from it. To create a binary node each record would then have two links associated with it.

2. EXAMPLE

The code presented in Table 1 is used to generate randomly sized binary trees where each node has a sibling and a child reference (which will be set to null at the leaf nodes). Each node, represented by a record has a label and a number associated with it. The output is such that a numbering system has been used to indicate the location of each node in the tree. The number 1 is the root node, the number 3 is a sibling of the root node, the number 3.1 is a child of a sibling of the root node, and so on.

// GENERATE TREE
// Frans Coenen
// 6 April 2000
// Department of Computer Science

import java.util.*;

class GenTree {

    // Node class
    protected class Node {
        private String label;
        private int number = 1;
        private Node childRef = null;
        private Node siblingRef = null;
	
	public Node() {
	    }
	    
	public Node(String name, int num) {
            label = name;
	    number = num;
	    }  
        } 
	
    private Node startRef = null; 
    private final int START_PROB = 20;
    private final int INCREMENT = 20;
    private final int DECREMENT = 2;
    private final int START_NUMBER = (100/INCREMENT)*DECREMENT;
    
    /* GENERATE TREE */
    
    public void generateTree() {
	
	startRef = new Node("A",START_NUMBER);
	
	generateNextLevel(startRef,START_PROB,"","A",'B','B',START_NUMBER);
	}

    /* GENERATE NEXT LEVEL */
	    	
    public void generateNextLevel(Node linkRef, int prob, 
    		String grandparentLabel, String parentLabel,
    		char childPostfix, char siblingCounter,int number) {
        int ranNum; 
    	
	// Child branch
	
	ranNum = (int) ((Math.random())*100.0); 
	if (ranNum > prob) {
	    String label = parentLabel.concat(new 
	    		Character(childPostfix).toString());
	    linkRef.childRef = new Node(label,number-DECREMENT);
	    generateNextLevel(linkRef.childRef,prob+INCREMENT,parentLabel,
	    		label,(char) (childPostfix+1),(char)
			(siblingCounter+1),number-DECREMENT);
	    }
	
	// Sibling branch
	
	ranNum = (int) ((Math.random())*100.0); 
	if (ranNum > prob) {
	    String label = grandparentLabel.concat(new 
	    		Character(siblingCounter).toString());
	    linkRef.siblingRef = new Node(label,number);
	    generateNextLevel(linkRef.siblingRef,prob,grandparentLabel,
	    	label,(char) (childPostfix+1),(char) (siblingCounter+1),number);
	    }
	}

    /* OUTPUT P-TREE */

    public void outputTree() {
        outputTree1(startRef,"start",1); 
	}
	
    public void outputTree1(Node linkRef,String node, int counter) {
        int index=0;
	String newNode;

	if (linkRef != null) {
	    // Outputnode number
	    if (node == "start") newNode = Integer.toString(counter);
	    else {
	        newNode = node.concat(".");
	        newNode = newNode.concat(Integer.toString(counter));
		}
	    System.out.print("(" + newNode + ") ");
	    // Output
	    System.out.print("label = " + linkRef.label);
	    System.out.println(" , number = " + linkRef.number);
	    // Continue
	    outputTree1(linkRef.childRef,newNode,1);
	    counter++;
	    outputTree1(linkRef.siblingRef,node,counter);
	    }
	}
    }

Table 1: Code to generate random binary trees

Some sample output is presented in Table 2.

$ java GenTreeApp
(1) label = A , number = 10
(2) label = B , number = 10

$ java GenTreeApp
(1) label = A , number = 10
(1.1) label = AB , number = 8
(1.2) label = AC , number = 8
(1.2.1) label = ACD , number = 6
(1.2.2) label = ACE , number = 6
(1.2.2.1) label = ACEF , number = 4
(1.3) label = AD , number = 8
(1.3.1) label = ADE , number = 6
(1.3.1.1) label = ADEF , number = 4
(1.3.2) label = ADF , number = 6
(2) label = B , number = 10
(2.1) label = BC , number = 8
(2.2) label = BD , number = 8
(3) label = C , number = 10
(3.1) label = CD , number = 8
(3.1.1) label = CDE , number = 6
(3.1.1.1) label = CDEF , number = 4
(3.2) label = CE , number = 8
(3.3) label = CF , number = 8
(3.3.1) label = CFG , number = 6
(3.3.2) label = CFH , number = 6
(3.3.3) label = CFI , number = 6
(3.4) label = CG , number = 8
(3.4.1) label = CGH , number = 6
(3.5) label = CH , number = 8
(3.6) label = CI , number = 8

$ java GenTreeApp
(1) label = A , number = 10
(2) label = B , number = 10
(3) label = C , number = 10
(3.1) label = CD , number = 8
(3.1.1) label = CDE , number = 6
(3.1.1.1) label = CDEF , number = 4
(3.1.2) label = CDF , number = 6
(3.1.3) label = CDG , number = 6
(3.2) label = CE , number = 8
(3.2.1) label = CEF , number = 6
(3.2.1.1) label = CEFG , number = 4
(4) label = D , number = 10

Table 2: Sample output generate from the code presented in Table 1

Created and maintained by Frans Coenen. Last updated 06 April 2000

TREE DATA STRUCTURES

CONTENTS

1. INTRODUCTION

2. EXAMPLE