Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Array-list implementation of tree problem

  1. Nov 13, 2017 #1

    s3a

    User Avatar

    1. The problem statement, all variables and given/known data
    a) Draw a single binary tree that gave the following traversals:
    Inorder: T N C K V A S M W Q B R L
    Postorder: T C N V S A W M B Q L R K

    b) Assume that the binary tree from the above part (a) of this question is stored in an array-list as a complete binary tree as discussed in class. Specify the contents of such an array-list for this tree.

    2. Relevant equations
    If the first element's index starts at pos=1, the index of the left child of a certain element is 2*pos, and the index of the right child of a certain element is 2*pos+1.

    3. The attempt at a solution
    Here is the tree sought by part a.:
    ......K
    ....../\
    ..N......R
    ../\....../\
    T..C...Q..L
    ........./\
    ......M..B
    ....../\
    ....A..W
    ..../\
    ..V..S

    I am trying to do part b.

    If I (incorrectly) assume that the above tree is a complete tree (like it seems that the question wants me to do), I get stuck when implementing the tree into an array(list), as can be seen below. (Sorry about the formatting.):

    Indices: 0 1 2 3 4 5 6 7 8 9 10 11 12
    Elements in the same order as the indices above: K N R T C Q L ? ? ? ? M B

    What am I doing wrong?

    Any input would be GREATLY appreciated!
     
  2. jcsd
  3. Nov 13, 2017 #2

    Mark44

    Staff: Mentor

  4. Nov 13, 2017 #3

    s3a

    User Avatar

    I do understand part a.

    As for part b, I'm not 100% sure. Is it the case that the array-list would have a lot of cells with no values filled in as shown in my array-list representation below (unlike a tree that were complete, whose array-list representation would have indices 0 to 12, where each cell would contain an element)?:
    Index | Element Contained
    0 | K
    1 | N
    2 | R
    3 | T
    4 | C
    5 | Q
    6 | L
    7 | empty
    8 | empty
    9 | empty
    10 | empty
    11 | M
    12 | B
    13 | empty
    14 | empty
    15 | empty
    16 | empty
    17 | empty
    18 | empty
    19 | empty
    20 | empty
    21 | empty
    22 | empty
    23 | A
    24 | W
    25 | empty
    26 | empty
    27 | empty
    28 | empty
    29 | empty
    30 | empty
    31 | empty
    32 | empty
    33 | empty
    34 | empty
    35 | empty
    36 | empty
    37 | empty
    38 | empty
    39 | empty
    40 | empty
    41 | empty
    42 | empty
    43 | empty
    44 | empty
    45 | empty
    46 | empty
    47 | V
    48 | S
     
  5. Nov 13, 2017 #4

    Mark44

    Staff: Mentor

    Your binary tree has 6 levels, with 13 entries, so a complete binary tree with this many levels would have at most 63 entries (1 at the root at level 0, 2 at the level 1, 4 at level 2, and so on down to 32 at level 5). 1 + 2 + 4 + 8 + 16 + 32 = 63.

    Based on what you wrote in Relevant Equations, K should be at index 1 in the array. K's left child N should be at index 2*1 = 2, and the right child R should be at index 2*1 + 1 = 3. Treating N as the root of a subtree, its left child T should be stored at index 2*2 = 4, and the right child C stored at index 2*(3) + 1 = 7. Continue the indexing with the subtree headed by R until you all of the tree entries are indexed.

    If you do this in C or other C-based languages, array indexes start at 0, so all the numbers I wrote are too large by 1, and can be adjusted accordingly. Inasmuch as your tree isn't complete, there will be a 63 - 13 = 50 entries in the array that are empty.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted