Algorithms and Data Structures
Excercise 7
Tree 2 (Binary Tree Traverse)

This exercise explains how to traverse the binary tree.

Problem 1PostScript for printing

(1) Write down the tree which is created by putting the following data into an empty tree in order. The key of left child is less than or equal to the key of parent, while the key of right child is more than or equal to the key of parent. Include all intermediate stages.

O L D F A S H I O N

(2) Write the result of traversing a tree made from (1) by inorder.

木の作り方

Problem 2

Write the following function that generates a tree from the input data by using recursion.

void treeinsert_r(char c, NodePointer p);

c means a input data. p means a current node. And display the traversed result by inorder.

Example:
% ./a.out
INPUT DATA:  NAOKI
inorder:  A I K N O 

木の実際のデータ構造

Problem 3

Write a function that removes a datum from the tree. However, add the information of deletion to the node rather than deleting the node. And judge whether a node is deleted or not by looking at this value.

% ./a.out
INPUT DATA:  NAOKI
inorder:  A I K N O 

DELETE:  N
inorder:  A I K O 

The original Japanese document was written by Naoki Wakamatsu.
This translation document was written by Kenichi Maezu <m5061121@u-aizu.ac.jp>
and Hajime Matsui <m5061122@u-aizu.ac.jp> and checked by L. Pichl.