Tree
Tree Data Structure: Design
and Implementation in Java
Presented to
Sir Naeem Aslam Presented by
Ahmad AbdulRehman
Khayam Shah
9-1
Outline
w Why Trees?
w Trees
w Tree Terminology
w Difference between Tree & Binary
Trees
w Applications of Tree
w Huffman Coding Tree
w One Recursive Tree Algorithm
Implementation
9-2
Storing Many Objects
w We have examined 2 major ways
to store data in the main
memory of the computer
— arrays
• use subscripts to immediately
access elements
• fast access, but in the old
days would consume more
memory that you would like
it to (not true anymore)
— linked structures
• each node refers to the next
in the collection. To get 9-3
to
Another Linked Structure
w We now turn our attention to
another major way of storing
data: the Tree
— One implementation of a tree has
nodes with a left
nodes and right
link
root field (binary tree)
w 1
2 3
edges 9-4
First Some Definitions
w A tree has a set of nodes and
directed edges that connect
them
— a directed edge connects a
parent to its children
w Tree properties
— one node is distinguished as the
root
— every node (except the root) is
connected by an edge from
9-5
exactly one other node
General Trees
w Trees store data in a
hierarchical
A manner
•
•
Trees have layers of nodes,
•
B C D where some are higher,
others are lower.
•
w
•
E F
•
— Root node is A
— A's children are B, C, and D
— E, F, and D are leaves
— Length of path from A to E is
9-6 2
Some tree terminology
• Node An element in the tree references
data and other nodes
• Root The node at the top It is upside
down!
• Parent The node directly above
another node (except root)
• Child The node(s) below a given node
• Size The number of descendants plus
one for the node itself
• Leaves Nodes with no children
• Levels The root A is at level 0, E
9-7
and F are at level 2
Differences Between A Tree & A Binary Tree
w No node in a binary tree may have a
degree more than 2, whereas there is
no limit on the degree of a node in a
tree.
w A binary tree may be empty; a tree
cannot be empty.
w The subtrees of a binary tree are
ordered; those of a tree are not
ordered.
•More…
w Are different when viewed as binary
trees. 9-8
Java’s Classes Example •
• Root
•
Object
•
• children of root
•
Number Throwable OutputStream
• grand children of root
•
• Integer Double great
Exception grand FileOutputStream
w
RuntimeException
9-9
Applications of trees
w File Systems
— Hierarchical files systems include
Unix and DOS
— In DOS, each \ represents an edge
(In Unix, it's /)
— Each directory is a file with a list
of all its children
w Store large volumes of data
— data can be quickly inserted,
removed, and found
w Data structure used in a variety of
situations
— implement data vase management systems9-10
— compilers: expression tree, symbol tree
Huffman Coding Tree
w Binary trees in a famous file
compression algorithm Huffman
Coding Tree
w Each character is stored in a
leaf
w The code is found by following
the path
— 0 go left, 1 go right 'e'
— a is 01
— e is 1 't' 'a'
9-11
Importing Packages …
import java.awt.*;\\ importing abstract
•
windowing toolkit
•
import java.awt.event.*;
• \\ importing awt.event
•
import javax.swing.*;
• \\ importing javax.swing
•
import javax.swing.tree.*;\\ importing
•
swing.tree package
•
9-12
Creating Tree1 class
public class Tree1 extends Jframe \\ extending
•
class using Jframe
•
•{
•public static void main(String args[])
•Tree1 frame = new Tree1(" A Tree");\\ creataing
tree
•frame.setSize(200,200); \\ set frame size
frame.setVisible(true); \\ if false then no
•
visibility
•
9-13
Creating Nodes…
•}
•public Tree1(String title) \\ creating class
setTitle(title); \\ setting title
•
DefaultMutableTreeNode root=new \\ creating root
•
DefaultMutableTreeNode ("Engineering");\\ root
•
name
•
•
DefaultMutableTreeNode style=new \\ declare new
•
style of root node
•
•
9-14
Creating Style to Nodes….
DefaultMutableTreeNode ("Information
•
Technology");
•
root.add(style);
• \\ add sub root or leaf node.
•
JTree jt=new JTree(root); \\
•
Container contentPane=getContentPane();\\
•
container can contain other awt component panel
•
contentPane.add(new JScrollPane(jt));\\ including
•
scrollpane class for manage a viewprt
9-15
w Each Tree object has
— a reference to an object object so we
can store anything
— a link to the left subtree which
could be an empty tree
— a link to the right subtree which
could be an empty tree
w 3 Constructors
— two set some data fields to null
(left and right)
w The data fields are private
— Like LinkNode, methods in the
enclosing class can reference9-16
Memory linked structure diagram
Root
Engineering
“Computer Science "
‘0’ ‘0’
9-17
•import java.awt.*;
•import java.awt.event.*;
•import javax.swing.*;
•import javax.swing.tree.*;
•
•public class Tree1 extends JFrame
•{
•public static void main(String args[])
•{
•Tree1 frame = new Tree1(" A Tree");
•frame.setSize(200,200);
•frame.setVisible(true);
•}
•public Tree1(String title)
•{
•setTitle(title);
•DefaultMutableTreeNode root=new
DefaultMutableTreeNode ("Engineering");
•DefaultMutableTreeNode style=new
DefaultMutableTreeNode ("Information
Technology");
•root.add(style);
9-18
•style=new
DefaultMutableTreeNode("Electronics")
;
•root.add(style);
•style=new DefaultMutableTreeNode
("Computer Science");
•root.add(style);
•style=new DefaultMutableTreeNode
("Mechanical");
•root.add(style);
•style=new DefaultMutableTreeNode
("Electrical");
•root.add(style);
•style=new DefaultMutableTreeNode
("Sound");
•root.add(style);
•JTree jt=new JTree(root);
•Container contentPane=getContentPane();
•contentPane.add(new JScrollPane(jt));
•}
•}
9-19
Any Questions ?
•
9-20
Thank you
9-21
