Java- печати дерева рекурсивно с скобкой

Question

* Я ответил на свой вопрос ниже *

Есть другие большие решения, а в этой теме.

* Оригинальный вопрос: *

Я пытался распечатать дерево, которое я построил так:

дерева (корень (20), дерево (корень (15), лист (10), лист (18)), дерево (корень (25), лист (22), лист (27)))

у меня есть следующий код:

static int childlev = 0;//This is global var used to keep track of parentheses 

public static void printStruct(MyTree tree, int level) {//This prints out the data structure of the tree 
    assert tree != null; 
    if (tree instanceof MyLeaf) {//reached the bottom leaf 
     MyLeaf leaf = (MyLeaf)tree; 
     System.out.print(",leaf('" + leaf.value+ "':" + leaf.frequency + ")"); 
     childlev=level; 

    } else if (tree instanceof MyNode) {//reached a parent 
     if(childlev>level){//print parentheses when right child leaf is reached and level goes back to parent 
      for(int i=0;i<childlev-level;i++)//child level minus parent level that we are backing up to 
       System.out.print(")"); 
      childlev=0; 
     } 
     if(level!=0){ 
      System.out.print(","); 
     } 

     MyNode node = (MyNode)tree; 
     System.out.print("tree(root("+node.frequency+")"); 
     // traverse left 
     printStruct(node.left, level+1); 

     // traverse right 
     printStruct(node.right, level+1); 
    } 
} 
//at the end of my main after calling above function i have this: 
    for(int i=0; i<p; i++)//This puts in the final parentheses 
     System.out.print(")"); 

в этом выходы:

tree(root(170),tree(root(70),tree(root(32),tree(root(16),tree(root(8),leaf('x':4),tree(root(4),leaf('l':2),leaf('u':2),leaf('h':8),leaf('n':16)),tree(root(38),tree(root(17),leaf('w':8),leaf('o':9)),tree(root(21),tree(root(10),leaf('v':5),leaf('f':5)),tree(root(11),leaf('y':5),tree(root(6),leaf('g':3),leaf('a':3)))))),tree(root(100),tree(root(47),leaf('t':22),tree(root(25),tree(root(12),tree(root(6),leaf('c':3),tree(root(3),leaf('z':1),leaf('d':2),leaf('r':6),leaf('i':13))),tree(root(53),leaf('e':26),leaf('s':27)))) 

Но, как вы можете видеть, после листа ('u': 2) должно быть 2 круглых скобки, но их нет. Итак, прямо сейчас, если у нас есть правый лист, за которым следует правый лист, мы не печатаем никаких закрывающих круглых скобок. Как это исправить? Спасибо заранее!

Answer 1

Это не так сложно, как вы это делаете.

Сначала вы должны избавиться от своих классов MyNode и MyLeaf. Они вам не нужны, и это делает обновление дерева излишне сложным. Узел - это лист, это дерево. Вам нужно только MyTree следующим образом:

public class MyTree 
{ 
    private MyTree left; 
    private MyTree right; 
    private String value; 
    private int frequency; 
    // ... constructors etc 

    public void print() 
    { 
     System.out.print("tree("); 
     if (left != null || right != null) 
     { 
      System.out.print("root("+frequency); 
      if (left != null) 
      { 
       System.out.print(","); 
       left.print(); 
      } 
      if (right != null) 
      { 
       System.out.print(","); 
       right.print(); 
      } 
      System.out.print(")"); // ends root() 
     } 
     else 
     { 
      System.out.print("leaf('"+value+"':"+frequency+")"); 
     } 
     System.out.print(")"); // ends tree() 
    } 

Если вы действительно должны сохранить дополнительные классы:

public abstract class MyTree 
{ 
    // ... 
    public abstract void print(); 
} 

public class MyNode extends MyTree 
{ 
    // ... 
    public void print() 
    { 
     System.out.print("tree("); 
     System.out.print("root("+this.frequency); 
     if (left != null) 
     { 
      System.out.print(","); 
      left.print(); 
     } 
     if (right != null) 
     { 
      System.out.print(","); 
      right.print(); 
     } 
     System.out.print(")"); // ends root() 
     System.out.print(")"); // ends tree() 
    } 
} 

public class MyLeaf extends MyTree 
{ 
    // ... 

    public void print() 
    { 
     System.out.print("tree("); 
     System.out.print("leaf('"+value+"':"+frequency+")"); 
     System.out.print(")"); // ends tree() 
    } 
} 

Обратите внимание, что вам не нужен счетчик кронштейна, и метод не является статическим.

E & OE

Answer 2

* Я отвечаю на мой собственный вопрос *

Мое решение немного неаккуратно, мягко говоря.

В этой теме есть и другие отличные решения, но поскольку мой случай немного особенный, мне пришлось найти свой собственный способ сделать это. В основном фиксирующие края. Я дам ссылку на мой GitHub для этого проекта, как только он встанет, чтобы другие могли его четко видеть.

Вот рабочая версия:

//These are global vars declared up top 
static int chl = 0;//keeps track of child level 
static int retp = 0;//keeps track of return parent level 
static int rl = 0;//keeps track of right leaves 

//Here is the function to print out tree: 
public static void printStruct(MyTree tree, int level, int right) {//This prints out the data structure of the tree 
    assert tree != null; 
    if (tree instanceof MyLeaf) {//reached the bottom leaf 
     if(right==1 && rl>1){//print parentheses when right leaf is followed by right leaf 
      for(int i=0;i<chl-retp;i++) 
       System.out.print(")"); 
      retp--; 
     } 
     MyLeaf leaf = (MyLeaf)tree; 
     System.out.print(",leaf('" + leaf.value+ "':" + leaf.frequency + ")"); 
     chl=level; 
    } else if (tree instanceof MyNode) {//reached a parent 
     rl=0;//next node is not leaf set back to zero 
     if(chl>level){//print parentheses when right child leaf is reached and level goes back to ancestor parent 
      for(int i=0;i<chl-level;i++) 
       System.out.print(")"); 
      chl=0; 
     } 
     if(level!=0){//if not the first root then add comma 
      System.out.print(","); 
     }   
     MyNode node = (MyNode)tree; 
     System.out.print("tree(root("+node.frequency+")"); 
     // traverse left 
     if(node.left instanceof MyNode){ 
      retp=level; 
     } 
     printStruct(node.left, level+1, 0); 

     // traverse right 
     if(node.right instanceof MyNode){ 
      retp=level; 
     }else rl++;//next node is right leaf 
     printStruct(node.right, level+1, 1); 
    } 
} 

//at the end of my main when calling above function I have this: 
printStruct(tree, 0, 0); 
for(int i=0; i<chl; i++)//This puts in the final parentheses 
    System.out.print(")"); 

Вот правильный выход:

tree(root(170),tree(root(70),tree(root(32),tree(root(16),tree(root(8),leaf('x':4),tree(root(4),leaf('l':2),leaf('u':2))),leaf('h':8)),leaf('n':16)),tree(root(38),tree(root(17),leaf('w':8),leaf('o':9)),tree(root(21),tree(root(10),leaf('v':5),leaf('f':5)),tree(root(11),leaf('y':5),tree(root(6),leaf('g':3),leaf('a':3)))))),tree(root(100),tree(root(47),leaf('t':22),tree(root(25),tree(root(12),tree(root(6),leaf('c':3),tree(root(3),leaf('z':1),leaf('d':2))),leaf('r':6)),leaf('i':13))),tree(root(53),leaf('e':26),leaf('s':27))))