Page 201 - DCAP407_DATA_STRUCTURE

Data Structure

10.4.3 Decision Trees
Decision trees represent a program in the form of tree with branches. Here, each node represents a
decision. First, the root node is tested and then the control is passed to one of its sub-trees, depending
on the result of the test. This flow is continued until the leaf node with the element of interest is reached.
An example for a decision tree is given in figure 10.23. This decision tree decides the ascending order
among three numbers x, y, and z.
Figure 10.23 Decision Tree that Determines the
Ascending Order for Three Numbers

First, we check if x is lesser than y. If the condition is true, then check if y is lesser than z. If yes, then the
ascending order of these numbers is x<y<z. If not, check if x is lesser than z. If yes, then the ascending
order of these numbers is x<z<y. If not, then the ascending order of these numbers is z<x<y. If the
condition x<y is false, i.e., if x is not lesser than y, then check if y is lesser than z. If this is true, then
check whether x is lesser than z. If yes, then the ascending order of these numbers is y<x<z. If the
condition y<z is false, i.e., if y is not lesser than z, then the ascending order of these numbers is z<y<x.

Construct a decision tree for finding the greatest number among a given set of
numbers.

10.5 Summary

• A tree structure is a way of presenting the hierarchical nature of a structure in a graphical form.
• The trees can be represented as graphs.
• The three types of graphs are directed graphs, undirected graphs, and mixed graphs.
• The different kinds of trees include binary tree, binary search tree, 2-3 tree, and Huffman tree.
• The two ways to represent trees are linked representation and array representation.

• The applications of trees include expression trees, game trees, and decision trees.
• To evaluate an expression tree, we recursively evaluate the left and right sub-trees and then apply
the operator at the root.
• A game tree is a graphical representation of a sequential game. It is a directed graph whose nodes
are positions in a game and whose edges are moves.
• In decision trees, each node represents a decision.

194 LOVELY PROFESSIONAL UNIVERSITY