Data Structures and Algorithms
Chapter 8
General Trees Basics
• Agraphisasetofnodesandasetofedges.
• Formally, a graph G = (V, E), where V is a set of nodes
(or vertices) and E is a set of edges.
• Each edge connects two nodes, and is represented as (u,
v), where u and v are nodes.
• A tree is a connected, acyclic, undirected graph with a
distinguished node called root.
• Connected: There is a path from every node to every
other node.
• Acyclic: There is no cycle
• Undirected: Edges have no direction
• Example
General Trees Basics
• Root, parent, child, siblings
• Internal node, external node (or leaf node)
• Ancestor, descendant
• Path
General Trees Basics
• Ordered tree: There is meaningful ordering among siblings:
General Trees Basics
• Inthesubsequentslides,“position”isusedin many examples. You can consider it as a “node” or an “element” in the data structure.
• The source programs that come with our textbook uses “position.”
• If you are required to write a program that uses our textbooks source code that uses “position,” I will give you a substitute code that does not use “position.”
• Accessor methods
General Trees Tree ADT
– root( ): Returns the position of the root of the tree, or null if the tree is empty.
– parent(p): Returns the position of the parent of position p, or null if p is the root.
– children(p): Returns the children of position p, if any. If the tree is an ordered tree, children are ordered in the result.
– numChildren(p): Returns the number of children of position p.
• Query methods
General Trees Tree ADT
– isInternal(p): Returns true if position p is an internal node.
– isExternal(p): Returns true if position p is an external node (or a leaf node).
– isRoot(p): Returns true if position p is the root of the tree.
• Other general methods
General Trees Tree ADT
– size( ): Returns the number of positions (or the elements) in the tree.
– isEmpty( ): Returns true if the tree does not have any position (or element).
– iterator( ): Returns an iterator for all elements in the tree. So, the tree is Iterable.
– positions( ): Returns an iterable collection of all positions of the tree.
• Tree interface
1
2
3
4
5
6
7
8
9
10 11 12 13 }
General Trees Tree ADT
public interface Tree
Position
Position
throws IllegalArgumentException;
int numChildren(Position
boolean isInternal(Position
boolean isEmpty();
Iterator
• AbstractTree abstract class
General Trees Tree ADT
1 public abstract class AbstractTree
2 public boolean isInternal(Position
3 public boolean isExternal(Position
4 public boolean isRoot(Position
5 public boolean isEmpty() { return size() == 0; }
6 …
7}
• Depth
General Trees Depth and Height
– Ifpistheroot,thedepthofpis0.
– Otherwise, the depth of p is one plus the depth of its parent.
1 {
public int depth(Position
2
3
4
5 6}
if (isRoot(p)) return 0;
else
return 1 + depth(parent(p));
Running time = O(dp + 1) dp is the depth of p
General Trees Depth and Height
• The height of a tree is the length of the longest path from the root downward to an external node.
• Recursive definition:
– If p is a leaf, then the height of p is 0.
– Otherwise, the height of p is one more than the maximum of the heights of p’s children.
1
2
3
4
5 6}
h = Math.max(h, 1 + height(c)); return h;
Running time = O(n)
n is the number of positions
public int height(Position
for (Position
• Example
General Trees Depth and Height
• c:\
• depth 0
• height 4 • CS526
• depth 2
• height 2
• Program Files
• depth 1
• height 2
Binary Trees
• A binary tree is an ordered tree with the following properties:
– Every node has at most two children.
– Each child node is labeled as being a left child or a
right child.
– A left child precedes a right child in the order of children of a node
Binary Trees
• The subtree rooted at the left or right child of an internal node v is called the left subtree or the right subtree, respectively, of v.
• A binary tree is proper if each node has either zero or two children. (also referred to as full binary tree).
• So, in a proper binary tree, every internal node has exactly two children.
• A binary tree that is not proper is improper.
Binary Trees • Example (a decision tree)
yes
no
Will buy
Will not buy
Credit Rating ? Own Savings
Will not buy
high
Account?
Will not buy
yes
no
Young ?
low
Binary Trees • Example (arithmetic expression tree)
• ((((3*7)–(3*5))+5)+(2–(8/2)))
Binary Trees
• A binary tree can be recursively defined as follows:
– A binary tree is either
• An empty tree, or
• A nonempty tree with a root node r and two binary trees that are the left subtree and the right subtree of r. One or both of these subtrees can be empty, by definition.
Binary Trees ADT
• The binary tree ADT is a specialization of the Tree ADT.
• Following additional methods are defined:
– left(p): Returns the position of the left child of p. Returns null if p has no left child.
– right(p): Returns the position of the right child of p. Returns null if p has no right child.
– sibling(p): Returns the position of the sibling of p. Returns null if p has no sibling.
• BinaryTree interface
1
2
3
4 5}
Position
Binary Trees ADT
public interface BinaryTree
Position
Position
• Additional methods: – sibling
Interface Tree (Section 8.1.2)
– numChildren – children
Class AbstractTree (Section 8.1.2)
Interface BinaryTree (Section 8.2.1)
• AbstractBinaryTree.java
Binary Trees ADT
• AbstractBinaryTree: extends AtstractTree and implements BinaryTree
implements
extends
extends
implements
Class AbstractBinaryTree (Section 8.2.1)
Binary Trees Binary Tree Properties
• Let level d of a binary tree T be the set of nodes at depth d of T.
• The maximum number of nodes at level d is 2d.
Binary Trees Binary Tree Properties
• n: the number of nodes in T
• nE: the number of external nodes in T
• nI: the number of internal nodes in T
• h: the height of T
• h+1≤n≤2h+1 –1
• 1≤nE≤2h
• h≤nI≤2h–1
• log(n+1)–1≤h≤n–1
• If T is a proper binary tree:
Binary Trees Binary Tree Properties
• 2h+1≤n≤2h+1 –1
• h+1≤nE≤2h
• h≤nI≤2h–1
• log(n+1)–1≤h≤(n–1)/2
• nE=nI+1
Binary Trees Implementation Using Linked Structure
• A node has the following linked structure.
Binary Trees Implementation Using Linked Structure
• LinkedBinaryTree extends AbstractBinaryTree abstract class with the following update methods:
– addRoot(e): Creates a new node with element e and make it the root of an empty tree. Returns the position of the root. An error occurs if the tree is not empty.
– addLeft(p, e): Creates a new node with element e and make it a left child of position p. Returns the position of the new node (left child). An error occurs if p already has a left child.
– addRight(p, e): Creates a new node with element e and make it a right child of position p. Returns the position of the new node (right child). An error occurs if p already has a right child.
Binary Trees Implementation Using Linked Structure
• Update methods (continued):
– set(p, e): Replaces the element of p with element e. Returns the previously stored element.
– attach(p, T1, T2): Attaches internal structure of T1 and T2 as the left subtree and the right subtree, respectively, of a leaf node position p and resets T1 and T2 to empty trees. If p is not a leaf node, an error occurs.
– remove(p): Removes the node at position p, replacing it with its child (if any). Returns the element that had been stored at p. An error occurs if p has two children.
•
A node is a position (instance variables shown below)
•
LinkedBinaryTree has two instance variables
Binary Trees Implementation Using Linked Structure
1 2 3 4 5
protected static class Node
private Node
// a reference to the parent node (if any) // a reference to the left child (if any)
private Node
// a reference to the right child (if any)
protected Node
• LinkedBinaryTree.java
(a)
Binary Trees Implementation Using Array
• Nodes are stored in an array.
• Level numbering scheme is used.
0 12 3456
7 8 9 10 11 12 13 14
• A number above a node is the index in the array.
• Example
(b)
0
Binary Trees Implementation Using Array
– 12
+* 3456
8
/3-
9
10 13
14
62 89
-+*8/3- 62 89 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Binary Trees
Linked Structure for General Trees
parent
children
element
Nevada Maine Idaho Oregon
Ohio
• Preorder tree traversal: – visit the root
– visit all children
Algorithm preorder(p) visit p
Binary Trees Tree Traversal
• A traversal of a tree T is a systematic way of visiting all positions in T.
for each child c in children(p) preorder(c)
Binary Trees Tree Traversal
• Preorder tree traversal illustration:
• Postorder tree traversal:
– Visit all children (recursively) – Visit the root
Algorithm postorder(p)
for each child c in children(p)
postorder(c) visit p
Binary Trees Tree Traversal
Binary Trees Tree Traversal
• Postorder tree traversal illustration
• Breadth-first tree traversal
Binary Trees Tree Traversal
– Also called breadth-first search or BFS
– Visits all positions at depth d before visiting positions at depth d + 1.
d=0
d=1
d=2
Binary Trees Tree Traversal
• Breadth-first tree traversal (continued)
Algorithm breadthfirst( )
initialize Q to contain the root of the tree while Q is not empty
p = Q.dequeue( ) // remove the oldest entry in Q visit p
for each child c in children(p)
Q.enqueue(c) // add all children of p to the rear of Q
• Running time
– Each node is enqued and dequeued once each. – O(n)
Algorithm inorder(p)
if p has a left child lc
// visit left subtree
// visit right subtree
inorder(lc) visit p
if p has a right child rc inorder(rc)
Binary Trees Tree Traversal
• Inorder tree traversal of binary tree – Visit the left subtree
– Visit the root
– Visit the right subtree
Binary Trees Tree Traversal
• Inorder tree traversal of binary tree illustration:
0
– 12
+* 3456
8
/3-
9
10 13
14
62 89
• Inordertreetraversalgenerates:8+6/2–3*8–9 • Correct expression without parentheses
Binary Trees Binary Search Tree
• A binary search tree is a binary tree with additional properties:
– Each position p stores an element, denoted as e(p).
– All elements in the left subtree of a position p (if any)
are less than e(p).
– All elements in the right subtree of a position p (if any) are greater than e(p).
• A binary search tree example:
Binary Trees Binary Search Tree
• Inorder tree traversal generates:
3, 8, 17, 20, 26, 31, 52, 54, 57, 72, 78, 94
y = x;
x = left child of x; x = right child of x;
} else {
y = x;
} // end of while
}
Binary Trees Binary Search Tree
Algorithm add(p, e) // an incomplete code if p == null // this is an empty tree
create a new node with e and make it the root of the tree x = p; y = x; // y follows x
while (x is not null) {
if (the element of x) is the same as e, return null else if (the element of x) > e{
add(root, 13)
Add 13 x
yy Add 13
25
25
Binary Trees Binary Search Tree
x
12 36 12 36
3 15 31 47 3 15 31 47
25 41 25 41
Add 13
Add 13
y
add(root, 13)
25
25
12 x 36
3 15 31 47
12 y 36
3 15 31 47
Binary Trees Binary Search Tree
25 41
x
null
25 41
add(root, 13)
Binary Trees Binary Search Tree
25
12 y 36
3 15 31 47 13 25 41
References
• M.T. Goodrich, R. Tamassia, and M.H. Goldwasser, “Data Structures and Algorithms in Java,” Sixth Edition, Wiley, 2014.