Transcript Building Trees

CS 163
Data Structures
Chapter 9
Building, Printing Binary Trees
Herbert G. Mayer, PSU
Status 5/21/2015
1
Syllabus
 Arithmetic Expressions and Trees
 Infix Without Parentheses
 Infix With Parentheses
 Postfix Without Parentheses
 Prefix Without Parentheses
 Interesting Examples
 Use of Postfix
 Building Trees
 Tree of Ints
2
Arithmetic Expressions and Trees

Three typical notations for dyadic operations:

Infix notation: write as the first the left operand, reading left-toright, then list the dyadic operator, finally list the right operand




Postfix notation: write left operand first, then list the right
operand, finally the operator




For CPU: Order will not work for code emission, as the CPU needs
both operands for processing the operator
For humans: requires parentheses for proper operator precedence
Note exception: programming language APL
This order will work for code emission, as operator has both
operands available at processing time
Needs no parentheses, and still obeys operator precedence
Postfix notation AKA Polish Postfix, after Jan Łukasiewicz, 1920
Prefix notation: First list the operator, next the first (left)
operand, finally the second (right) operand
3
Arithmetic Expressions and Trees
a+x^c
Infix:
(a+(x^c))
Postfix: a x c ^ +
Prefix:
+a^xc
+
a
^
x
c
^ stands for exponentiation, with highest precedence: higher than * or /
4
Arithmetic Expressions and Trees
(x–a) / b
Infix:
((x–a)) /b
Postfix: x a – b /
Prefix:
/–xab
/
-
x
b
a
/ stands for division operator, with higher precedence than, say, –
5
Arithmetic Expressions and Trees
a^(b–c) /d
Infix:
((a^(b–c)) /d)
Postfix: a b c - ^ d /
Prefix:
/
^
a
d
b
c
6
/^a–bcd
Data Structure to Print Trees
// node has class: literal, identifier, or operator.
// Parenthesized expressions have been reduced: no ( )
typedef enum { Literal, Identifier, Operator } NodeClass;
typedef struct NodeType * NodePtr;
// forward
// actual node structure; using the forward pointers
typedef struct NodeType
{
NodeClass
Class; // 3 classes. Not C++ ‘class’
char
Symbol; // stores ident or small literal
int
LitVal; // if Class == Literal: its value
NodePtr
Left;
// left subtree
NodePtr
Right; // right subtree
} s_node_tp;
7
Infix Without Parentheses
// Print in infix notation without parentheses ( )
void Print_No_Paren( NodePtr Root )
{ // Print_No_Paren
if ( Root ) {
Print_No_Paren ( Root->Left );
if ( Root->Class == Literal ) {
printf( "%d", Root->LitVal );
}else{
printf( "%c", Root->Symbol );
} //end if
Print_No_Paren ( Root->Right );
} //end if
} //end Print_No_Paren
Input: ( a + x ) / b prints as: a + x / b
8
 misleading
Infix With Parentheses
// Print in infix notation with parentheses ( and )
void Print_Infix( NodePtr Root )
{ // Print_Infix
if ( Root ) {
if ( Root->Class == Operator ) {
printf( "(" );
} //end if
Print_Infix( Root->Left );
if ( Root->Class == Literal ) {
printf( "%d", Root->LitVal );
}else{
printf( "%c", Root->Symbol );
} //end if
Print_Infix( Root->Right );
if ( Root->Class == Operator ) {
printf( ")" );
} //end if
} //end if
} //end Print_Infix
Input: ( a + x ) / b prints as: ( ( a + x ) / b ) -- OK
9
Postfix Without Parentheses
// Print in Polish Postfix notation, no parentheses
void Print_Postfix( NodePtr Root )
{ // Print_Postfix
if ( Root ) {
Print_Postfix( Root->Left );
Print_Postfix( Root->Right );
if ( Root->Class == Literal ) {
printf( "%d", Root->LitVal );
}else{
printf( "%c", Root->Symbol );
} //end if
} //end if
} //end Print_Postfix
Input: a ^ ( b – c ) / d prints as: a b c - ^ d /
10
-- OK
Prefix Without Parentheses
// Prefix: operator executes when 2 operands found
void Print_Prefix( NodePtr Root )
{ // Print_Prefix
if ( Root ) {
if ( Root->Class == Literal ) {
printf( "%d", Root->LitVal );
}else{
printf( "%c", Root->Symbol );
} //end if
Print_Prefix( Root->Left );
Print_Prefix( Root->Right );
} //end if
} //end Print_Prefix
Input: ( a + x ) / b prints as: / + a x b -- OK
11
Interesting Examples
Input 1:
a+b*c^(x–2*d)/(e–f)
Infix:
Postfix:
Prefix:
(a+((b*(c^(x–(2*d)))) / (e–f)))
abcx2d*-^*ef-/+
+a /*b^c–x*2d–ef
Input 2:
4/x^(k–l/m)*8*x-&9+n
Infix:
Postfix:
Prefix:
(((((4 / ( x^(k-(l/m))))*8)*x)-(&9))+n)
4xklm/-^/8*x*9&-n+
+-**/4^x–k/lm8x&9n
12
Use of Postfix
 Postfix, AKA Polish Postfix notation is a natural for
code generation, targeted for stack machines
 Operands are needed first: Two for dyadic, or one
for monadic operations
 Once generated and available on stack, stack
machine can execute the next operation
 Easy for compiler writer, natural for stack machine
 Stack poor for execution, as all references are
through memory: top of stack
 Even a GPR architecture needs both operands
available somewhere (in regs) to execute operator
13
Building Trees
 Now you understand: Trees constitute
inherently recursive data structures
 You learned how to traverse them, and in
various orders
 Now we learn how to build them
 Initially trees may be unbalanced
 Worst case, they may be so-called leftspine (or right-spine) trees, i.e. no different
from linear lists, but more costly to process
14
Building Trees
 Let tree nodes be simple int data structures
 Each node holds an integer value named info
 Info numbers don’t need to be unique
 Provide data from input files, or hard-coded
 Since node numbers may be repeated, each node
includes a count
 Let the left and right subtrees be named smaller
and greater, alluding to info ordering
 Thus we have sufficient information to define the
node data structure in C++
15
Building Trees, Node Type
typedef struct node_tp * node_ptr_tp;
typedef struct node_tp
{
int
info;
// the node!
int
count;
// how many?
node_ptr_tp
smaller; // left subtree
node_ptr_tp
greater; // and right
} str_node_tp;
node_ptr_tp
root
= NULL;
16
// key Datum
Allocate Node Off Heap
//use C malloc() or C++ new operator
node_ptr_tp make_node( int info )
{ // make_node
node_ptr_tp node = new str_node_tp;
if( node ) {
node->info
= info;
node->smaller = NULL;
node->greater = NULL;
node->count
= 1;
}else{
error( ” . . .” );
} //end if
return node;
} //end make_node
17
Tree of Ints
 Tree is pointed to by root, initially nil
 Type of root is pointer to node, in C++ node_ptr_tp
 When the next info element is searched in an empty
tree, i.e. if root == NULL, new node is inserted, count
set to 1, root points to that new node, and root is
returned
 Done by node_ptr_tp function insert()
 Else, since tree is not empty, the current info is
compared; if yields a match, count is incremented
and root to that existing node is returned
18
Tree of Ints
 Else, if there is no match, traverse the left
or the right subtree, depending on whether
root->greater or root->smaller
 I.e., whether info > root->info
 Or whether info < root->info
 And recurse!
19
Tree of Ints
// Given “info”, insert in tree: “root”
node_ptr_tp insert( node_ptr_tp & root, int info )
{ // insert
if ( NULL == root ) {
// why in this order?
root = make_node( info );
}else if( info > root->info ) {
root->greater = insert( root->greater, info );
}else if( info < root->info ) {
root->smaller = insert( root->smaller, info );
}else{
root->count++;
} //end if
return root;
} //end insert
20
Traverse Tree of Ints In-order
 When the complete tree is constructed, it is
pointed to by global root, of node_ptr_tp
 To traverse, we can use pre-order, postorder or in-order
 In-order handles left subtree first
 Then looks at node
 And finally traverses right subtree
21
Traverse Tree of Ints In-order
// traverse binary tree, root, in in-order
void in_order( node_ptr_tp root )
{ // in_order
if ( root ) {
in_order( root->smaller );
printf( "%d(%d) ", root->info,
root->count );
in_order( root->greater );
} //end if
} //end in_order
22
Sample Tree Traversal
 Let’s build a binary tree of ints, pointed to by root
 The input sequence we consider is given here:
-5 -14 -2 -11 1 -8 4 -5 7 -2 10 1 13 4 16 7 19 10
 We build the tree as shown above
 Tracking the count of each integer value, by giving
this in parentheses
 E.g. -11(3) would mean: integer value -11 is in the
tree and did occur 3 times in the input provided
23
Sample Tree Traversal
 Hard-coded input of data to build tree:
// enter some arbitrary ints
void get_data( void )
{ // get_data
for ( int node = -5; node < 20; node += 3 ) {
root = insert( root, node );
root = insert( root, node - 9 );
// printf( "%d %d ", node, node - 9 );
} //end for
} //end get_data
24
Sample Tree Traversal
int main()
{ // main
printf( "Entering fixed list of: " );
get_data( );
printf( "\n in order
in_order( root );
printf( "\n" );
return 0;
} //end main
25
: " );
Sample Output
in order : -14(1) -11(1) -8(1) -5(2) -2(2)
1(2) 4(2) 7(2) 10(2) 13(1) 16(1) 19(1)
26
References
 Łukasiewicz:
http://www.calculator.org/Lukasiewicz.aspx
 http://cslibrary.stanford.edu/110/BinaryTrees.html
27