What is the warm up in a data structure

Task 1: Trees and traversing trees

Christoph Garbe: Algorithms and Data structures, SS 09 exercise sheet 2

Submission: by April 16, 2009

task 1: Treesand binary search trees

12 points

In the lecture you have general (n-are) Trees already met. A special case of one

such a tree is a binary tree in which each node can have a maximum of two descendants. In C

one could represent a node in a binary tree like this:

key

struct node {

node * left; // left child node

node * right; // right child node

left right

int key; // stored value / key

};

a) To warm up: How would you have to adapt the above data structure to create a tree with a maximum of 5

To represent child nodes? How is a leaf in the above data structure (i.e. a node without children)

shown?

(2 points)

b) How can any (n-ary) tree be represented as a binary tree? How must the

above data structure have to be adapted? Draw the binary tree resulting from the following

general tree results!

(5 points)

c) There is a binary possibility Trees in a field (array). How can you do that

do? Provide the tree task 1b) as a field!

(5points)

task 2: Binary search tree

36 points

A binary search tree is now a special binary tree with the following "search tree property" in

every node is fulfilled:

Let x be any node in a binary search tree. For any node y l from the

left child tree of x holds that key [y l] ≤ key [x]. For any node y r from the

right child tree of x holds that key [y r]> key [x].

a) How can you add a new key to a binary search tree in the simplest possible way

insert and how to delete? Write down the procedures in C ++ (use the node definition above) or

in pseudo-code! Which possible error conditions need to be handled? To output your

A print () function has already been implemented in the search tree. You can initially use this as a black box

consider that outputs the tree in level order.

(7 + 7 points)


Christoph Garbe: Algorithms and Data structures, SS 09 exercise sheet 2

Submission: by April 16, 2009

b) Draw the tree that arises when you put the following numbers in the order given

enters: 1,5,2,10,4,8,9,20,19,22. What do you notice about the tree? How big would the array have to be if the

Tree like in task 1c) should be shown?

(3 + 2 points)

c) Give a method with which one can find the largest or the

can find the smallest key efficiently. Indicate how many nodes your two methods are in

Search tree task b) must check. How many are there in the tree shown below?

(5 points)

Dates as a list: 10, 5, 3, 15, 6, 14, 16, 28, 7, 17

d) How can you check whether a certain key is contained in the search tree? Give

again the number of visited nodes for the Trees out task b) and c) if 19 or 17

should be searched for.

(5 + 2 points)

e) The numbers in the search tree from 2c) can also be displayed as an array (see example there). How many

On average, comparisons are necessary to determine whether a particular element is in such a list of

Length N is included. How many comparisons do you need on average in a binary search tree

To consider a certain element included? (Tip: Think about how deep a search tree is

is in the mean. Leave extreme cases out of the way!)

(2 + 3 points)

task 3: Syntax tree

28 points

Syntax trees are used to represent mathematical expressions in the computer. Hereinafter

you should consider syntax trees that use the operations addition (+) and Multiplication (*) on whole

Numbers 0..9 can represent. The rule point-before-line should be observed! The following C code

can be used to represent a knot.

struct node {

node * left; // left child node

node * right; // right child node

char type; // Operation: '+' (Add.), '*' (Mul.), '' (Number)

int value; // stored number

};

a) How does the following mathematical expression (given in infix notation) look like and Prefix-

Notation?

(1 point)


Christoph Garbe: Algorithms and Data structures, SS 09 exercise sheet 2

Submission: by April 16, 2009

3*(5+8*9)+2

b) How can you build a tree from a prefix text representation of an expression? Give

The syntax tree resulting from the following entry:

(5 points)

+3*5+43 *+*458+*+8921

c) According to which traversing method is the expression shown in infix, prefix and to

which one in postfix notation? In what procedure is the issue of Need brackets?

(3 points)

d) Implement the recursive Traversal a syntax tree in C ++ according to the three procedures

out task c). Use the attached code structure for this purpose. Do not use any additional

Data structures (stack, field, ...).

(9 points)

e) Implement a procedure that consists of a string in Postfix notation

Syntax tree builds up. You can submit either C ++ or pseudocode. In the first case, use that

Code framework for task. You can use the data structure Stack for this purpose, which is defined in the C ++ standard

Library is already implemented (see http://www.cplusplus.com/reference/stl/stack/). The

It is used in the code template for this task in a nutshell.

(10 points)

Hints:

If you Trees If you want to draw graphs, you can of course use paper, or whatever

Graphics program, but there are also specialized tools for such purposes. The graph on this

Exercise sheets were created with GraphViz, for example, that you can find on the Internet at http://www.graphviz.org/

Find.

In the C ++ standard library there are many grandlegendary data structures already implemented. A

You can find detailed documentation with many examples at http://www.cplusplus.com/.

The code blocks on which you should build can be found under

http://ipm.uni-hd.de/teaching/Algorithmen/Uebung/CodeBlatt2.zip