Data Structures
Lecture 06: Trees
Edirlei Soares de Lima
Trees
A tree data structure allows data to be organized hierarchically.
Examples: file directories, arithmetic expressions, route planning...
Trees
A tree comprises a set of nodes, such that:
There is a node r, called root, with zero or more subtrees, whose roots
The root nodes of these subtrees are the children of r;
The inner nodes of the tree are the nodes with children;
The leaves (or outer nodes) of the tree are the nodes without children;
root
subtrees
Trees
Tree structure
public class TreeNode<T> : IComparable
{
private T data;
...
root
level
height
leaves
Binary Trees
A binary tree is a tree where each node has zero, one or two
children;
public class BTreeNode<T>
{
private T data;
private BTreeNode<T> left;
private BTreeNode<T> right;
.
..
}
Binary Trees
Example: a binary tree can be used to represent
arithmetic expressions:
Leaf nodes represent operands;
Internal nodes operators;
Example: (3+6)*(4-1)+5
Binary Trees
Binary Tree Structure
public class BTreeNode<T>{
private T data;
private BTreeNode<T> left;
private BTreeNode<T> right;
public BTreeNode<T> Left{
get { return left; }
set { left = value; }
}
Data
public BTreeNode<T> Right{
get { return right; }
set { right = value; }
}
Left
Right
public T Data{
get { return data; }
set { data = value; }
}
}
Binary Tree
Basic operations:
Create: creates a node.
IsEmpty: returns true if the tree is empty.
Traverse: iterates over the tree performing an operation over the
nodes (such as printing their values).
Different traversal orders are possible.
Search: checks if a value exists in the tree an
Remove: removes a node from the tree.
Binary Tree
Tree operations:
Recursive implementation
Use of the recursive structure of the tree
A binary tree is:
An empty tree; or
A root node with two subtrees:
The left subtree (lst);
root
The right subtree (rst);
empty
lst
rst
Binary Tree Create
Creates a root node given the information and the two
subtrees, the one on the left and the one on the right.
Constructor method of the BTreeNode class:
public BTreeNode(T t, BTreeNode<T> l, BTreeNode<T> r)
{
left = l;
right = r;
data = t;
}
Binary Tree IsEmpty
Indicates whether a given tree is empty or not.
The operation is not part of the generic node class, so a type for the
data must be defined (example: string).
public bool IsEmpty(BTreeNode<string> node)
{
if (node == null)
return true;
else
return false;
}
Binary Tree Traverse
Recursively iterates over the tree, visiting all nodes and
performing an operation over the data (example: printing the
data).
The operation is not part of the generic node class, so a type for the
data must be defined (example: string).
public static void PrintTree(BTreeNode<string> node)
{
if (!IsEmpty(node))
{
Debug.Log(node.Data);
PrintTree(node.Left);
PrintTree(node.Right);
}
}
Binary Tree Creating a Tree
/
* subtree "d" */
BTreeNode<string> a1 = new BTreeNode<string>("d", null, null);
* subtree "b" */
BTreeNode<string> a2 = new BTreeNode<string>("b", null, a1);
* subtree "e" */
BTreeNode<string> a3 = new BTreeNode<string>("e", null, null);
* subtree "f" */
BTreeNode<string> a4 = new BTreeNode<string>("f", null, null);
* subtree "c" */
BTreeNode<string> a5 = new BTreeNode<string>("c", a3, a4);
* subtree "a" */
BTreeNode<string> root = new BTreeNode<string>("a", a2, a5);
/
/
/
/
/
Binary Tree Creating a Tree
BTreeNode<string> root = new BTreeNode<string>("a",
new BTreeNode<string>("b",
null,
new BTreeNode<string>("d", null, null)
),
new BTreeNode<string>("c",
new BTreeNode<string>("e", null, null),
new BTreeNode<string>("f", null, null)
));
Binary Tree Traverse
It is possible to format the printing to better show the tree
structure.
public static void PrintTreeFormated(BTreeNode<string> node,
int level){
if (!IsEmpty(node))
{
PrintTreeFormated(node.Right, level + 1);
string spaces = "";
for (int i = 0; i < level; i++)
spaces += "\t";
Debug.Log(spaces + node.Data);
PrintTreeFormated(node.Left, level + 1);
Does not work
well on Unity
console
}
}
Binary Tree Search
Checks for the occurrence of a string s in one of the nodes;
Returns a Boolean value indicating whether s exists or not in the tree.
public static bool SearchTree(BTreeNode<string> node, string s)
{
if (IsEmpty(node))
return false;
else{
if (node.Data.Equals(s))
return true;
else if (SearchTree(node.Left, s))
return true;
else if (SearchTree(node.Right, s))
return true;
else
return false;
}
}
Binary Trees Traverse Order
Pre-order:
Access data, traverse lst, traverse rst;
Example: a b d c e f
In-order:
Traverse lst, acess data, traverse rst;
Example: b d a e c f
Post-order:
Traverse lst, traverse rst, acess data;
Example: d b e f c a
Binary Tree Example
Considering a binary tree to represent arithmetic expressions:
Leaf nodes represent operands;
Internal nodes operators;
Example: (3 + 6) * (4 - 1) + 5
Binary Tree Example
Create a function to print the expression that is encoded in a
binary tree.
For the tree example, the function must print the following
expression:
(((3+6)*(4-1))+5)
Binary Tree Example
Create the tree:
BTreeNode<string> node1 = new BTreeNode<string>("3", null, null);
BTreeNode<string> node2 = new BTreeNode<string>("6", null, null);
BTreeNode<string> node3 = new BTreeNode<string>("4", null, null);
BTreeNode<string> node4 = new BTreeNode<string>("1", null, null);
BTreeNode<string> node5 = new BTreeNode<string>("5", null, null);
BTreeNode<string> node6 = new BTreeNode<string>("+", node1, node2);
BTreeNode<string> node7 = new BTreeNode<string>("-", node3, node4);
BTreeNode<string> node8 = new BTreeNode<string>("*", node6, node7);
BTreeNode<string> node9 = new BTreeNode<string>("+", node8, node5);
Binary Tree Example
Print the expression:
public static string PrintTreeExp(BTreeNode<string> node){
string exp = "";
if (!IsEmpty(node)){
if ((IsEmpty(node.Left)) && (IsEmpty(node.Right)))
exp = node.Data;
else{
exp = "(";
exp += PrintTreeExp(node.Left);
exp += node.Data;
exp += PrintTreeExp(node.Right);
exp += ")";
}
}
return exp;
}
Binary Tree Example
Create a function to evaluate the expression encoded in a
binary tree.
For the example, the result of the expression is: 32
Binary Tree Example
Evaluate the expression:
public static float EvaluateTreeExp(BTreeNode<string> node)
{
if ((IsEmpty(node.Left)) && (IsEmpty(node.Right)))
return float.Parse(node.Data);
else{
if (node.Data.Equals("+"))
return EvaluateTreeExp(node.Left) + EvaluateTreeExp(node.Right);
else if (node.Data.Equals("-"))
return EvaluateTreeExp(node.Left) - EvaluateTreeExp(node.Right);
else if (node.Data.Equals("*"))
return EvaluateTreeExp(node.Left) * EvaluateTreeExp(node.Right);
else
return EvaluateTreeExp(node.Left) / EvaluateTreeExp(node.Right);
}
}
Assignment 1 Tree
1) Create a class to represent a general tree data structure.
Every node of the tree can have N children.
root
subtrees
The children must be stored in a linked list:
public class TreeNode<T> : IComparable
{
private T data;
...
The following operations must be implemented:
Create, IsEmpty, Print, and Search.
Binary Search Tree (BST)
The value associated with the root is
always greater than the value associated
with any node in the left subtree (lst);
The value associated with the root is
always less than or equal than the value
associated with any node in the right
subtree (rst);
When the tree is traversed in symmetrical
order (lst - root - rst), the values are
found in ascending order;
Search in a Binary Search Tree
Compare the given value with the value
associated with the root:
If it is equal, the value was found;
If it is smaller, the search continues on the lst;
If it is larger, the search continues on rst;
Search in a Binary Search Tree
In balanced trees the inner nodes have all, or almost all, 2
children;
Any node can be reached from the root in O(log n) steps;
Search in a Binary Search Tree
In degenerated trees, all nodes have only 1 child, except for the
(single) leaf;
Any node can be reached from the root in O(n) steps;
Completly
Unbalanced
Degenerated)
Completly
Balanced
Balanced
Unbalanced
(
Binary Search Tree Traverse
It is possible to print the values in ascending order, traversing
the nodes in symmetrical order:
public static void PrintBST(BTreeNode<int> node)
{
if (!IsEmpty(node))
{
PrintBST(node.Left);
Debug.Log(node.Data);
PrintBST(node.Right);
}
}
Binary Search Tree Search
Explores the ordering property of the tree;
The computational performance is proportional to the height of the
tree;
public static BTreeNode<int> SearchBST(BTreeNode<int> node, int v)
{
if (node == null)
return null;
else if (node.Data > v)
return SearchBST(node.Left, v);
else if (node.Data < v)
return SearchBST(node.Right, v);
else
return node;
}
Binary Search Tree Insert
Input: a value v to be inserted;
Output: a possible new root node for the tree/subtree;
To insert v on the correct position:
If the subtree is empty:
Create a tree whose root contains v;
If the subtree is not empty:
Compare v with the value in the root;
Try to insert v in lst or rst, depending on the result of the comparison;
Binary Search Tree Insert
public static BTreeNode<int> InsertBST(BTreeNode<int> node, int v)
{
if (node == null)
node = new BTreeNode<int>(v, null, null);
else if (node.Data > v)
node.Left = InsertBST(node.Left, v);
else
node.Right = InsertBST(node.Right, v);
return node;
}
Binary Search Tree Insert
create
insert 6
insert 4
insert 8
insert 2
insert 5
insert 1
insert 3
insert 7
insert 9
Binary Search Tree Insert
create
insert 6
insert 4
insert 8
insert 2
insert 5
insert 1
insert 3
insert 7
insert 9
insert 6
Binary Search Tree Insert
create
insert 6
insert 4
insert 8
insert 2
insert 5
insert 1
insert 3
insert 7
insert 9
insert 6
Binary Search Tree Insert
public static BTreeNode<int> InsertBST(BTreeNode<int> node, int v)
{
if (node == null)
node = new BTreeNode<int>(v, null, null);
else if (node.Data > v)
node.Left = InsertBST(node.Left, v);
else if(node.Data < v)
node.Right = InsertBST(node.Right, v);
return node;
}
Binary Search Tree Remove
Input: a value v to be removed;
Output: a possible new root node for the tree/subtree;
To remove v:
If the subtree is empty:
nothing has to be done;
If the subtree is not empty:
compare the value stored at the root node with v:
if it is greater than v, remove the element from the left subtree;
if it is less than v, remove the element from the right subtree;
if it is equal to v, remove the root from the tree;
Binary Search Tree Remove
To remove the root from the tree, there are 3 cases:
Case 1: the node to be removed is a leaf node;
Case 2: the node to be removed has a single child;
Case 3: the node to be removed has two children;
BST Remove Leaf Node
Case 1: the node to be removed is a leaf node:
Remove the node by returning the updated node, which will be null
remove 3
remove
node 3
BST Remove Single Child Node
Case 2: the node to be removed has a single child :
The child node becomes the child of the parent node;
remove 4
remove
node 4
BST Remove Two Children Node
Case 3: the node to be removed r has two children
find the node N that precedes r in the ordering (the rightmost element
of the left subtree)
swap the value of r with the value of N
remove N from the left subtree (which now contains the value to be
removed)
removing the rightmost node N is simple, as N is a leaf node or N is a node with a
single child (in this case, the right child never exists)
remove 6
swap 6
and 4
remove
node 6
public static BTreeNode<int> RemoveBST(BTreeNode<int> node, int v){
if (node == null)
return null;
else if (node.Data > v)
node.Left = RemoveBST(node.Left, v);
else if (node.Data < v)
node.Right = RemoveBST(node.Right, v);
else{
/* found the node to remove */
if (node.Left == null && node.Right == null) /* case 1: leaf node */
node = null;
else if (node.Left == null) /* case 2: single child to the left */
node = node.Right;
else if (node.Right == null) /* case 2: single child to the right */
node = node.Left;
else{
/* case 3: node has two children */
BTreeNode<int> f = node.Left;
while (f.Left != null) /* search for a single child or leaf node */
f = f.Right;
node.Data = f.Data; /* swap the values */
f.Data = v;
node.Left = RemoveBST(node.Left, v);
}
}
return node;
}
Applications in Game Programming
Branching narrative structures: each node represents a
narrative event or a sequence of events.
Dialog trees: branching nodes represent dialog choices that
Pathfinding: pathfinding algorithms use tree structures to
store the search data.
Decision trees, behavior trees, etc.
Assignment 2 Tree
1
) Implement a tree-based dialog system to represent the
following
Every node of the tree must store the dialog text and the interaction option
that led to the node.
A way to see and interact with the dialog tree must be implemented.
No graphical interface is required. The dialogs can be displayed in the console and the player
interaction can be done by pressing keys (e.g.: 1 selects the first child option; 2 selects
the second child option).