Xathrya Sabertooth

Programming Problem Set: 99 Problems Chapter 4

Posted: 20 Jul 2013 04:03 AM PDT

Ninety-nine Problems is generalized version to famous P-99: Ninety-Nine Prolog Problems collection used for teaching programming. The problems initially set for prolog but later many solutions come from various programming language. The purpose of this problem is to give us opportunity to practice our skills in logic programming. The goal is to find the most elegant solution of the given problem. Efficiency is important, but logical clarity is even more crucial.

The problem set are divided into seven categories / chapters: Lists, Arithmetic, Logic and Codes, Binary Trees, Multiway Trees, Graphs, and Miscellaneous.

In this chapter you will be only given a problem set. The solution might come however it would be on different page.

This chapter will cover about Binary Trees. Binary is either empty or it is composed of a root element and two successors, which are binary tree themselves.

The problems in this chapter is a continuation of previous chapter, therefore the numbering will start from the last problem.

For the sake of writing, we will denote tree node as t (value, left, right).

  45. Check whether a given object / term is a binary tree.  The predicate is succeeds if and only if its argument is a representing a binary tree.    example:  is_tree_p( t(a, t(b, null, null), null) -> true

  46. Construct a completely balanced binary trees  In a completely balanced binary tree, the following property holds for every node: The number  of nodes in its left subtree and the number of nodes in its right subtree are almost equal,  which means their difference is not greater than one.    Write cbal_tree/2 to construct completely balanced binary trees for a given number of nodes.  The predicate should generate all solutions via backtracking. Put the letter 'x' as information  into all nodes of the tree.    Example: cbal_tree_p( 4 )   ->  t(x, t(x, null, null), t(x, null, t(x, null, null)))  t(x, t(x, null, null), t(x, t(x, null, null), null))  ...etc

  47. Symmetric binary trees.  Let us call a binary tree symmetric if you can draw a vertical line through the root node  and then the right subtree is the mirror image of the left subtree. Write symmetric/1 to check  whether a given binary tree is symmetric.    <b>Hint:</b> Write mirror/2 first to check whether one tree is the mirror image of another.  We are only interested in the structure, not in the contents of the nodes.

  48. Binary search trees (dictionaries)  Write a predicate to construct a binary search tree from a list of integer numbers.    Example:  construct_p( [3,2,5,7,1] ).  -> t(3, t(2, t(1, nil, nil), nil), t(5, nil, t(7, nil, nil)))

  49. Generate and test paradigm.  Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees  with a given number of nodes.    Example: sym_cbal_trees_p( 5 )   ->  [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil),   t(x, nil, t(x, nil, nil)))]    How many such trees are there with 57 nodes? Investigate about how many solutions there are for a  given number of nodes. What if the number is even? Write the appropriate solution.

  50. Construct height-balanced binary trees.  In a height-balanced binary tree, the following property holds for every node:  The height of its left subtree and the height of its right subtree are almost equal, which means their  difference is not greater than one.    Write a predicate hbal_tree/2 to construct height-balanced binary trees for a given height.  The predicate should generate all solutions via backtracking. Put the letter 'x' as information into  all nodes of the tree.    Example: hbal_p( 3 )   ->  t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), t(x, nil, nil)))  t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), nil))  ...etc

  51. Construct height-balanced binary trees with a given number of nodes.  Consider a height-balanced binary tree of height H. What is the maximum number of nodes it can contain?  Clearly, MaxN = 2^H - 1. However, what is the minimum number MinN? This question is more difficult.  Try to find a recursive statement and turn it into a predicate minNodes/2 defined as follwos:    minNodes_p( H ) -> the minimum number of nodes in a height -balanced binary tree of height H.    On the other hand, we might ask: what is the maximum height H a height-balanced binary tree with N nodes  can have?    maxHeight_p( N ) -> the maximum height of a height balanced binary tree with N nodes    Now, we can attack the main problem: construct all the height-balanced binary trees with a given number  of nodes.    hbal_tree_nodes_p( N ) -> height-balanced binary tree with N nodes.    Find out how many height-balanced trees exist for N = 15

  52. Count the leaves of a binary tree.  A leaf is a node with no successors.    Example: count_leaves_p( t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) )   -> 3    The leaf are [ t(c, null, null), t(d, null, null)), t(e, null, null)) ]

  53. Collect the leaves of a binary tree in a list  A leaf is a node with no successors.    Example:  leaves_p( t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) )   ->  [ t(c, null, null), t(d, null, null)), t(e, null, null)) ]

  54. Collect the internal nodes of a binary tree in a list.  An internal node of a binary tree has either one or two non-empty successors.  Example: internals_p( t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) )  ->  [ t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)),    t(b, t(c, null, null), t(c, null, null)) ]

  55. Collect the nodes at a given level in a list.  A node of a binary tree is at level N if the path from the root to the node has length N-1.  The root node is at level 1.    Example: atlevel_p( 2, t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) )  ->  [ t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) ]

  56. Construct a complete binary tree.  A <i>complete</i> binary tree with height H is defined as follows:  The levels 1,2,3,...,H-1 contain the maximum number of nodes (i.e 2**(i-1) at the level i,  note that we start counting the levels from 1 at the root). In level H, which may contain less  than the maximum possible number of nodes, all the nodes are "left-adjusted". This means that in a  levelorder tree traversal all internal nodes come first, the leaves come second, and empty successors  (the nil's which are not really nodes!) come last.    Particularly, complete binary trees are used as data structures (or addressing schemes) for heaps.    We can assign an address number to each node in a complete binary tree by enumerating the nodes in  levelorder, starting at the root with number 1. In doing so, we realize that for every node X with  address A the following property holds: The address of X's left and right successors are 2*A and 2*A+1,  respectively, supposed the successors do exist. This fact can be used to elegantly construct a complete  binary tree structure. Write a predicate complete_binary_tree/2 with the following specification:    Example: complete_binary_tree_p( 3 ) -> The complete binary tre with N nodes

  57. Layout a binary tree.  Given a binary tree as the usual Prolog term t(X,L,R) (or nil). As a preparation for drawing the tree,  a layout algorithm is required to determine the position of each node in a rectangular grid.  Several layout methods are conceivable, one of them is shown in the illustration above.  In this layout strategy, the position of a node v is obtained by the following two rules:  (1) x(v) is equal to the position of the node v in the inorder  (2) y(v) is equal to the depth of the node v in the tree sequence

  58. Layout a binary tree (2).  Figure located above    An alternative layout method is depicted in the above illustration. Find out the rules and write  the corresponding solution.  Hint: On a given level, the horizontal distance between neighboring nodes is constant.    Use the same conventions as in problem 57.

  59. Layout a binary tree (3).  Figure located above    Yet another layout strategy is shown in the above illustration. The method yields a very compact  layout while maintaining a certain symmetry in every node. Find out the rules and write the  solution.  Hint: Consider the horizontal distance between a node and its successor nodes.  How tight can you pack together two subtrees to construct the combined binary tree?    Use the same conventions as in problem 57 and 58 and test your predicate in an appropriate way.  Note: This is a difficult problem. Don't give up too early!    Which layout do you like most?

  60. A string representation of binary trees  Somebody represents binary trees as strings of the following type (see example):    a(b(d,e),c(,f(g,)))    (a) Write a solution which generates this string representation, if the tree is given as  usual (as nil or t(X,L,R) term). Then write a predicate which does this inverse;  i.e. given the string representation, construct the tree in the usual form.  Finally, combine the two predicates in a single predicate tree_string/2 which can be used in  both directions.    (b) Write the same predicate tree_string/2 using difference lists and a single predicate  tree_dlist/2 which does the conversion between a tree and a difference list in both directions.    For simplicity, suppose the information in the nodes is a single letter and there are no  spaces in the string.

  61. Preorder and inorder sequence of binary trees.  We consider binary trees with nodes that are identified by single lower-case letters, as in the  example of problem 60.    <b></b>(a) Write predicates preorder/2 and inorder/2 that construct the preorder and inorder sequence of a  given binary tree, respectively. The results should be atoms, e.g. 'abdecfg' for the preorder sequence  of the example in problem 4.16.    (b) Can you use preorder/2 from problem part a) in the reverse direction;  i.e. given a preorder sequence, construct a corresponding tree? If not, make the necessary arrangements.    (c) If both the preorder sequence and the inorder sequence of the nodes of a binary tree are given,  then the tree is determined unambiguously. Write a predicate pre_in_tree/3 that does the job.    (d) Solve problems (a) to (c) using difference lists.    What happens if the same character appears in more than one node. Try for instance pre_in_tree(aba,baa,T).

  62. Dotstring representation of binary trees.  We consider again binary trees with nodes that are identified by single lower-case letters, as in  the example of problem 60. Such a tree can be represented by the preorder sequence of its nodes in  which dots (.) are inserted where an empty subtree (null) is encountered during the tree traversal.  For example, the tree shown in problem 60 is represented as <tt>'abd..e..c.fg...'</tt>.  First, try to establish a syntax (BNF or syntax diagrams) and then write a predicate tree_dotstring/2  which does the conversion in both directions. Use difference lists.

Solution:

Haskell
Lisp
Prolog
Python

Proyek Teknologi

Minggu, 21 Juli 2013