I wrote the code of the ternary tree.

public class Tree { public Tree right; public Tree left; public Tree middle; public int key; public Tree(int k) { key = k; } public void add(Tree aTree) { if (right == null) { right = aTree; } if (middle == null) { middle = aTree; } if (left == null) { left = aTree; } if (left != null) { left.add(aTree); } if (middle != null) { middle.add(aTree); } if (right != null) { right.add(aTree); } System.out.print(" " + aTree.key); } }

An error occurs in this place, I can not understand why.

 if (left != null) { left.add(aTree); }
  • one
    Another good thing is to show how you access this tree. And the resulting exception. NullPointerException ? - Nofate ♦
  • one
    use the if-else if construct - Kobayashi_Maru

3 answers 3

You have a problem in the algorithm. There will be a situation when you added aTree as a sheet, after that right will not be null and you will add aTree to right . And so on until the stack collapses.

@Kobayashi_Maru suggested the right direction, but he incorrectly formulated it. You need something like this:

  public void add(Tree aTree) { if (right == null) { right = aTree; } else if (middle == null) { middle = aTree; } else if (left == null) { left = aTree; } else if if (left != null) { left.add(aTree); } else if (middle != null) { middle.add(aTree); } else if (right != null) { right.add(aTree); } System.out.print(" " + aTree.key); }

UPD0 . Formally, my version is also not entirely correct. After filling all three leaves, only the left subtree will be filled. Obviously, there is not enough condition that determines which subtree the item will be sent to.

  • 2
    Strange algorithm. Unbalanced Essentially a list. Movement down only on the left branch. Does the vehicle want this ??? It is not clear what the vehicle wants. The key search tree or a balanced tree (where what it calls the key is not the search key, but the node data). For a simple balanced IMHO tree, with each link, you must store the weight of the subtree and insert it into the subtree with the minimum weight. Perhaps it makes sense to generalize the problem and build an n-ary tree. - avp
  • that's exactly what i meant, just gave a hint in which direction to move;) - Kobayashi_Maru
  • @avp, absolutely agree. - Nofate ♦

Use the if-else if construct or just the if-else construct. Sense to write first, that right == null, and then vice versa? Easier to write like this

 if (right == null ) {right = aTree; } else if ( right!= null ) {right.add( aTree );}

or so

 if (right == null ) {right = aTree; } else {right.add( aTree );}
  • I think the point is to fill empty sheets from left to right in the ternary tree, and only then subtrees. In your version only the right branch will be built. - Nofate ♦
  • No, well, you can do it for each branch, I just wrote that the copiler swears at the wrong construction of checking the values ​​.. - Kobayashi_Maru
  • @Ksenia, what do you want from this tree? What properties should it have? How do you think to use it? Answer the questions and understand how to fill the tree. - avp
  • @Ksenia, then maybe you should not fill the tree from the root? And just collect it by hand, and then take it to health? Tree subTreeA = new Tree (67); subTreeA.add (new Tree (4)); subTreeA.add (new Tree (45)); Tree subTreeB = new Tree (5); subTreeB.add (new Tree (30)); subTreeB.add (new Tree (72)); Tree subTreeC = new Tree (12); subTreeC.add (new Tree (14)); subTreeC.add (new Tree (95)); Tree myTree = new Tree (9000); myTree.add (subTreeA); myTree.add (subTreeB); myTree.add (subTreeC); - Nofate ♦
  • one
    Then for each subtree of the node, in addition to the reference to the subtree, it is necessary to keep the counter of elements of the subtree. When directing the next item to the subtree - increase the corresponding counter. If the order of the keys is not important, then sending the item to the subtree with the minimum counter is the most reasonable. - avp

@Ksenia , everyone will be grateful if you write what specific error arises . You obviously

 Exception in thread "main" java.lang.StackOverflowError

and it is natural. See, you add a new tree first to right (because the rigth is first null), then in the middle and left. Then if (left! = Null) is executed and you add aTree there again. Since at this moment left is no longer null !!! .

Everything goes in cycles.

Add an else after each if, as in the @Nofate response.

Printing will be somewhat " strange " because The key of the inserted aTree will be printed at every level of the tree (all the way from sheet to root ).

Is this the result you really wanted to get? I do not know.