0

For example, one way to do it is you could transform the tree into a complete binary tree, with null elements in place of previously non-existing elements (to fill out the tree), and starting at the root (1st array element) traverse it by going to the 2*ith + 1 element for left child and 2*ith + 2 element for right child. However, the array would be huge for a one-sided tree. Is there a more efficient way to do this?

I wrote my program to just traverse an array with the formula used above, 2N for left child, 2N+1 for right child. It is a guessing game that uses a “decision tree” to correctly guess an animal you think of. It asks yes or no questions to traverse a tree and eventually narrows down to one animal. If the animal isn’t the one you were thinking of, it asks for a question to differentiate between the new animal and the old one, and stores this new info in the tree.

In my implementation I didn’t use a tree, and to add new elements into the array I replaced the old answer with the question and added two spaces into the array for the two answers (children). I know it is inefficient to move the rest of the array forward to make a space for the new elements but I did that anyway. Then I realized that using the 2N+1 formula would be very inefficient for one-sided trees. So I am wondering if there is a way to structure the array or implement it so I can use some kind of formula for traversing it, and have it take up less space.

Aleks Vetushko
  • 13
  • 5
  • 2
    But title says about **full** binary trees... – MBo May 15 '17 at 06:30
  • In what order do you want to traverse the tree, and what operations do you want the tree to support? – Petar Petrovic May 15 '17 at 08:43
  • If this is a real problem, and the heap-array format isn't working for you, then "storing a tree in an array without building a tree" is probably not the best way to think about solving it. You should probably tell us what you really need to accomplish. – Matt Timmermans May 15 '17 at 14:31
  • 1
    I think you need to remove the word "full" from your title, as it's rather confusing. The words "full" and "complete" have specific meanings when talking about binary trees. See http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html – Jim Mischel May 16 '17 at 12:34
  • I meant full, I just listed an example where you could make the full tree into a complete tree. – Aleks Vetushko May 17 '17 at 02:35
  • Look at @trincot's answer to this question: – Adarsh Jain Aug 06 '17 at 10:39
  • Look at @trincot's answer to this question: https://stackoverflow.com/questions/43504632/take-every-k-th-element-from-the-1-n-natural-numbers-series/ – Adarsh Jain Aug 06 '17 at 10:40

3 Answers3

0

Normally the array variant is favourable and often used together with AVL-trees. These are binary search trees with a balancing method that guarantee that the tree stays balanced.

Clearly one could actually implement the tree like a list structure with separate objects that one links to.

gue
  • 1,868
  • 1
  • 16
  • 21
0

Your requirements describe a heap data structure. Depending on whether you want the largest or smallest value at the root, you would implement either a max-heap or a min-heap.

J. Michael Wuerth
  • 272
  • 1
  • 6
0

Do you mean something like this:

   1
 2   3      => [4,2,5,1,6,3,7]
4 5 6 7

The array can be extracted from the tree traversing the tree in-order.

Now the root is at index = n/2 = 3. Step s = (n+1)/4 = 2. Now going left is index-step and going right is index+step. Each time you go down you divide the step by two.

One level more: [8,4,9,2,10,5,11,1,12,6,13,3,14,7,15]. Root at n/2 = 7 and initial step s = (n+1)/4 = 4.

maraca
  • 8,468
  • 3
  • 23
  • 45