Page 199 - DCAP407_DATA_STRUCTURE

Data Structure

An alternate traversal strategy is to recursively print the left sub-tree, the right sub-tree, and then the
operator. If we apply this strategy to the tree above, the output is a b c * + d e * f + g * +. This traversal
strategy is generally known as a post order traversal.
A third traversal strategy is to print the operator first and then recursively print the left and right sub-
trees. The resulting expression, + + a * b c * + * d e f g, is the less useful prefix notation and the traversal
strategy is called a preorder traversal.

Construct an expression tree for the expression (2 * (5 + (6 + 4))).

10.4.2 Game Trees
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. The complete game tree for a game starts at the initial
position and contain all possible moves from each position.
The game Nim is played by two players A and B. A board which initially contains a pile of n toothpicks
describes the game. The players A and B make moves alternately with A making the first move. A legal
move consists of removing either 1, 2, or 3 of the toothpicks from the pile. A player cannot remove more
toothpicks than that present in the pile. The player who picks the last toothpick loses the game and the
other player wins. The board configuration at any time is absolutely specified by the number of
toothpicks remaining in the pile. At any time of the game, the status is determined by the board
configuration together with the player whose turn it is to make the next move. A terminal board
configuration is one which denotes both a win, lose, or draw situation and the further configurations
are non-terminal. The only terminal configuration in Nim is the one in which there are no toothpicks in
the pile. This configuration is a win for player A if B makes the last move, or else it is a win for B. The
game of Nim cannot end in a draw.
A sequence C 1, ..., C m of board configurations is assumed to be valid if:
1. C 1 is the starting configuration of the game

2. C i, 0 < i < m, are non-terminal configurations
3. C i+1 is obtained from C i by a legal move made by player A if i is odd and by player B if i is even.
A valid sequence C 1, ...,C m of board configurations with C m a terminal configuration is an example of
the game. The length of the order C 1,C 2, ...,C m is m. A finite game is the game in which there are no
valid sequences of infinite length. All possible instances of a finite game may be represented by a game
tree. In a game tree for nim, each node of the tree represents a board configuration. The root node
denotes the starting configuration C 1. The transitions from one level to the next level are made because
of a move of A or B. Transitions from an odd level represents moves made by A. All other transitions
are the result of moves made by B. Square nodes are used to represent the board configurations when it
is A's turn to move. Circular nodes are used for other configurations. The edges from various levels are
labeled with the move made by A and B respectively (for example, an edge labeled 1 means 1 toothpick
is to be removed).
The terminal configurations are represented by leaf nodes. Leaf nodes are labeled by the name of the
player who wins when that configuration is reached. In the game of Nim, player A can win only at leaf
nodes on odd levels while B can win only at leaf nodes on even levels. The degree of any node in a
game tree is equal to the number of distinct legal moves. In Nim, there are maximum 3 legal moves
from any configuration. The number of legal moves from any configuration is finite.

In Nim, we represent the configuration of the piles by a monotone sequence of
integers, such as (1,3,5,7) or (2,2,3,9,110). A player may remove, in one turn, any
number of toothpicks from one pile of his/her choice. Thus, (1,3,5,7) would
become (1,1,3,5) if the player were to remove 6 toothpicks from the last pile. The
player who takes the last toothpicks loses. The Nim game (1, 2, 2) is shown in
figure 10.22.

192 LOVELY PROFESSIONAL UNIVERSITY