1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Array-list implementation of tree problem
Loading...