Scribd Logo
Upload

Welcome to Scribd!

  • 69 views

    Tutorial 2

    Uploaded by

    Miguel Dirane
    This document contains exercises on data structures involving trees. It covers linked binary trees, building binary trees from files, AVL trees, binary trees in contiguous representation, and heaps. There are over 20 exercises involving writing functions to traverse trees, count nodes, find heights, convert between representations, insert and delete nodes while maintaining properties, and use trees to implement heapsort.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Tutorial 2

    Uploaded by

    Miguel Dirane
    69 views5 pages
    This document contains exercises on data structures involving trees. It covers linked binary trees, building binary trees from files, AVL trees, binary trees in contiguous representation, and heaps. There are over 20 exercises involving writing functions to traverse trees, count nodes, find heights, convert between representations, insert and delete nodes while maintaining properties, and use trees to implement heapsort.

    Original Description:

    test

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains exercises on data structures involving trees. It covers linked binary trees, building binary trees from files, AVL trees, binary trees in contiguous representation, and heaps. There are over 20 exercises involving writing functions to traverse trees, count nodes, find heights, convert between representations, insert and delete nodes while maintaining properties, and use trees to implement heapsort.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    69 views5 pages

    Tutorial 2

    Uploaded by

    Miguel Dirane
    This document contains exercises on data structures involving trees. It covers linked binary trees, building binary trees from files, AVL trees, binary trees in contiguous representation, and heaps. There are over 20 exercises involving writing functions to traverse trees, count nodes, find heights, convert between representations, insert and delete nodes while maintaining properties, and use trees to implement heapsort.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 5

    Pk Fokam Institute of Excellence 2015-2016

    Course: CS3424Data Structures Teacher: Dr Lossan BONDE

    Tutorial #2 Trees

    I/ LinkedBinary Trees (See LinkedBinTree module )


    Exercise #1 Write a function that counts all the nodes of linked Binary Tree.
    Exercise #2 Determine the order in which the nodes of the following binary trees will be visited under:
    1. preorder,
    2. inorder,
    3. postorder
    traversal.

    (a) 1 (b) 1 (c) 1


    2 2 2 (d) 1
    2 3
    3 3 3 4
    4 4 5 6
    4 5 6 7 8 9
    5 5 7 8
    Exercise #3 Write a function that will count the leaves of linked binary tree.
    Exercise #4 Write a function that will find the height of a linked binary tree.
    Exercise # 5 Write a procedure to perform a double-order traversal of a binary tree, meaning that at each node of the tree
    the procedure first visits the node, then traverses its left subtree (in double order), then visits the node again, then traverses
    its right subtree (in double order).
    Exercise #6 For each of the trees in exerise 2, determine the order in which the nodes will be visited in the mixed order
    given by invoking function A.

    void A(LinkedBinTree p){ void B(LinkedBinTree p){


    if (p){ if (p){
    visit(p); A(p->left);
    B(p->left); visit(p);
    B(p->right); A(p->right);
    } }
    } }

    Exercise #7 Write a function that will print the keys from a binary tree in the bracketed form.
    ( key : LT, RT )
    Where key is the key in the root, LT denotes the left subtree of the root printed in bracketed form, and RT denotes the right
    subtree in bracketed form. )
    Exercise #8 Write a function that will interchange all left and right subtrees in a linked binary tree (see example below).

    1 1

    2 3 Becomes 3 2

    4 5 6 6 5 4

    7 8 7 8

    Data Structures Exercises on Trees Dr. Lossan BONDE PKFIE 2015 Page 1/5
    Exercise # 9 Write a fucntion that will delete a node from a linked binary tree, using the following method in case when the
    node to be deleted has both subtrees non-empty. First find the immediate predecessor of the node under inorder traversal (the
    immediate successor would work just as well), by moving to its left child and then as far right as possible. The immadiate
    predecessor is guaranteed to have at most one child (why?), so it can be deleted from its current position without difficulty. It
    can then be placed into the tree in the position formerly occupied by the node that was supposed to be deleted, and the
    properties of a search tree will still be satistied (why?).
    Exercise #10 Write a function for searching, using a binary search tree with sentinel as follows. Introduce a new sentinel
    node, and keep a pointer to it. See figure below. Replace all the NULL links within the search tree with links to the sentinel.
    Then, for each search, first store the target into the sentinel. Run both this procedure and the original procedure TreeSearch
    to compare the time needed both for successful and unsuccessful search.

    X X
    Exercise #11 Write a function that will traverse a binary tree level by level. That is, the root is visited first, the immediate
    children of the root, then the grandchildren of the root, etc (Hint: remember to use a queue (BFS)).
    Exercise #12 Write a function that will return the width of a linked binary tree, that is, the maximum number of nodes on the
    same level.
    Exercise #13 Write a function that converts a binary tree into a doubly linked list, in which the nodes have the order of inorder
    traversal of the tree. At the conclusion of the function, the pointer root should point to the leftmost node of the doubly
    linked list, and the links right and left should be used to move through the list, and be NULL at the two ends of the list.

    II/ Building Binary Trees


    Exercise #14 Write a function GetNode(P) that will traverse a linked list and get each node from the list in turn.
    Exercise #15 Write a function GetNode (p) that will read a record from a file, check that the key is in the proper order, and
    return a new node containing the record. Thereby obtain a self-contained procedure for reading a balanced binary search tree
    from an ordered sequential file.

    III/ AVL Trees


    Exercise #16 In each of the following, insert the keys, in the order shown, in order to build them into an AVL tree.
    a) A, Z, B, Y, C, X
    b) A, B, C, D, E, F
    c) M, T, E, A, Z, G, P
    d) A, Z, B, Y, C, X, D, W, E, V, F
    e) A, B, C, D, E, F, G, H, I, J, K, L
    f) A, V, L, T, R, E, I, S, O, K
    Exercise #17 Delete each of the keys inserted in the above exercise from the AVL tree, in LIFO order.
    Exercise #18 Delete each of the keys inserted in the above exercise from the AVL tree, in FIFO order.
    Exercise #19 Write a C program that will accept keys from the user one at a time, build them into an AVL tree, and write out
    the tree at each stage. You will need a procedure to print a tree, perhaps in the bracketed form defined in exercise #7.
    Exercise #20 Write a C function that deletes a node from an AVL tree.

    IV/ Binary Trees in Contiguous Representation


    Binary trees can represented differently than using linked structures. It is possible to represente binary trees using contiguous
    storage. Let consider the binary tree presented below. We can put this tree into a contiguous array by storing each node in the
    position shown by its label. We state:
    The left and right children of the node with index k are in positions 2k and 2k+1, respectively. If these positions
    are beyond the bounds of the array, then these children do not exist.

    Data Structures Exercises on Trees Dr. Lossan BONDE PKFIE 2015 Page 2/5
    This sequential representation can, in fact, can be extended to arbitrary binary trees, provided that we can flag locations in the
    array to show that the corresponding nodes do not exist. The results for several binary trees are shown below.

    This kind of representation is interesting when all the leaves are on the same level, and all are as far to the left as possible.
    Heaps and Heapsort
    A heap is defined to be a binary tree with a key in each node, such that
    1. All the leaves of the tree are on two adjacent levels,
    2. All the leaves on the lower level occur to the left,
    3. The key in the root is at least as large as the keys in its childern (if any), and the left and right children (if they
    exist) are again heaps.
    The examples provided below present a heap and other trees which are not heaps.

    Data Structures Exercises on Trees Dr. Lossan BONDE PKFIE 2015 Page 3/5
    Heapsort: is a process of constructing a heap. It proceeds in two phases. In the first phase, the entries in the array being
    sorted are interpreted as a binary tree in contiguous representation. The first two properties of a heap are automatically
    satisfied, but the keys will not generally satisfy the third property. In the second phase, the first entry is moved to the last
    position, replacing an entry x. we then decrease a counter k that keeps track of the size of the list, thereby excluding the
    largest entry from further sorting. The entry x that has been moved from the last position, however, may not belong on the
    top of the heap, and therefore we must insert x into the proper position to restore the heap property before continuing to loop
    in the same way. Implementation of heapsort is provided in module heap.
    Exercise #21 Determine the contiguous representation of each of the following binary trees. Which of these are heaps? For
    those that are not, state which rule(s) is (are) violated at which node(s).

    Exercise #22 By hand, trace the action of HeapSort on each of the following lists. Draw the initial tree to which the list
    corresponds; show how it is converted into a heap; and show the resulting heap as each item is removed from the top and the
    new item inserted.
    a) The list of seven numbers : 26 33 35 29 19 12 22
    b) The list of fourteen names: Tim, Dot, Eva, Roy, Tom, Kim, Guy, Amy, Jon, Ann, Jim, Kay, Ron, Jan.
    Exercise #23 Design a function that will insert a new item into a heap, obtaining a new heap (the function InsertHeap
    provided in the module requires that the root is unoccupied, whereas for this exercise the root will already contain the item
    with largest key, which must remain in the heap. Your function will increase the count n of items in the list.) Analyse the
    time and space requirements of your function.
    Exercise #24 Design a function that will delete the item with largest key (the root) from the top of the heap, and restore the
    heap properties of the resulting, smaller list.
    Exercise #25 Design a function that will delete the item with index I from a heap, and restore the heap properties of the
    resulting, smaller list.

    V/ Lexicographic Search Trees: Tries


    Instead of searching by comparison of entire keys, we can consider a key as a sequence of characters (letters or digits, for
    example), and use these characters to determine a multi-way branch at each step. If our keys are alphabetic names, then we
    make a 26-way branch according to the first letter of the name, followed by another branch according to the second letter, and
    so on. This multi-way branching is the idea of a thumb index in a dictionary. A thumb index, however, is generally used only
    to find words with a given initial letter; some other search method is then used to continue. In a computer we can proceed
    two or three levels by multiway branching, but then the tree will become too large, and we shall need to resort to some other
    device to continue. One method is to prune from the tree all the branches that do not lead to any key. In English for example,
    there are not words that begin with the letters 'bb', 'bc', 'bd', 'bf'. Hence all the corresponding branches and nodes can be
    removed from the tree. The resulting tree is called a trie. A module called trie is provided that implements the tries data
    structure. The figure below describes a trie of words constructed from 'a', 'b', 'c'.
    Exercise #26 Draw the tries constructed fro each of the following sets of keys.
    a) All three-digit integers containing only '1', '2', '3' (in decimal representation).
    b) All three-letter sequences built from 'a', 'b', 'c', 'd' where the first letter is 'a'.
    c) all four-digit binary integers (built from '0' and '1').
    d) the words: pal, lap, a, papa, al, papal, all, ball, lab built from the letters 'a', 'b', 'l', 'p'.
    Exercise #27 Write a function that traverses a trie and print out all its words in alphabetical order.
    Exercise #28 Write a function that traverses a trie and print out all its words, with the order determined first by the length of
    the word, with shorter words first, and second, by alphabetical order for words of the same length.
    Exercise #29 Write a function that deletes a word from a trie.

    Data Structures Exercises on Trees Dr. Lossan BONDE PKFIE 2015 Page 4/5
    VI/ B-Trees
    (see module Btree provided)
    Exercise #30 Insert the keys below, in the order stated, into an initially empty B-Tree of order:
    A, B, C, D, E, F, G, H, I, J, K, L, X, W, Y, Z
    a) 3
    b) 4
    c) 7
    Exercise #31 Rewrite the function SearchNode to use a binary search.
    Exercise #32 Remove the tail-end recursion from function Search.

    Data Structures Exercises on Trees Dr. Lossan BONDE PKFIE 2015 Page 5/5

    You might also like