Блог

Кажется, у меня возникла проблема с добавлением правых узлов к левым узлам. У меня есть входной файл (.txt), который указан в предварительном заказе

 Fred    1900
2
John    1925
3
Mary    1950
2
Jason   1972
0
Heather 1975
2
Sydney  2002
0
Hailey  2005
0
John    1951
1
Amy 1983
0
Fred    1953
3
Mark    1977
0
Sarah   1979
1
Michael 2005
0
Adam    1982
0
Joan    1927
2
Susan   1949
0
David   1952
1
Fred    1980
0
  

Вот мой класс Node:

 public class Node {
    public String name;
    public int year;
    //this will help with determining the parent in the insertion process
    public int children;    
    public Node parent;
    public Node left;
    public Node right;


    public Node(String name, int year, int children){
        this.name = name;
        this.year = year;
        this.children = children;
    }
}
  

Предполагая, что мои узлы созданы успешно, у меня, похоже, возникла проблема с созданием фактического дерева.

 public class FamilyTree {    

    public Node familyTree;

    private Node pivotalNode;
    private Node parent;
    private int children = 0;
    //This method adds a family member to the family tree    
    public void add(Node newNode){
        familyTree = add(familyTree,newNode);
    }
    private Node add(Node familyTree, Node newNode){        
        if(familyTree == null){
            children = newNode.children;
            newNode.parent = parent;
            familyTree = newNode;

        }
        else if(children > 0){
            parent = familyTree;
            familyTree.left = add(familyTree.left, newNode);
            pivotalNode = familyTree.left;
        }
        else if(children == 0){          

            familyTree.right = add(familyTree.right, newNode);
            return pivotalNode;
        }        
        return familyTree;
    }  
} 
  

Результаты должны отображать дерево следующим образом:

Вот мой основной метод:

 public class Operations {

    //Not necessary but it helps me to get more organized. Just want to extract information first.
    public static ArrayList<String> information = new ArrayList<String>();  

    public static void main(String args[]){
        //extract information from file
        getFileContents();

        //Object initialization
        FamilyTree family = new FamilyTree();

        //some useful variables for loop below
        int children =0;
        String[] splitted = null;
        Node member = null;        

        for(int i=0; i<information.size(); i  ){
            //Every other line in the text file perform a different operation
            if(i % 2 == 1){
                try{
                    children = Integer.parseInt(information.get(i));
                    member = new Node(splitted[0], Integer.parseInt(splitted[1]), children);
                    family.add(member);
                }
                catch(Exception e){
                    //this determines if the pattern is broken
                    break;
                }
            }
            if(i % 2 == 0){                               
                splitted = information.get(i).split("\s ");
                //this determines a pattern difference                
                if(splitted.length < 2){
                    break;
                }
            }
        }
        System.out.print("hi");
    }
    //Pretty self explanatory. Read each line of the file and store it into an array. 
    //Not necessary as everything could technically be done at once (insertion), but this keeps me 
    //more organized to put everything together later on 
    public static void getFileContents(){
        try{
            BufferedReader br = new BufferedReader(new FileReader("includes\assn2in.txt"));            

            String line;
            String info;

            while ((line = br.readLine()) != null) {
                info = line.replaceAll("\s ", " ");
                information.add(info);               
            }            
            br.close();


        }
        catch(IOException e){
            System.out.println("Error: " e);
        }
    } 
}
  

Любая помощь была бы оценена с благодарностью.

Одна из ваших больших проблем заключается в том, что ваш Node класс моделирует двоичную древовидную структуру — то есть он содержит элементы left и right для представления дочерних элементов — но сами данные не соответствуют этой структуре. Если вы посмотрите на диаграмму, вы можете увидеть, что некоторые узлы имеют целых три дочерних узла (например, John 1925 и Fred 1953). Вам нужно использовать ArrayList вместо left и right , чтобы ваш Node мог обрабатывать произвольное количество дочерних элементов:

 public class Node {
    public String name;
    public int year;
    //this will help with determining the parent in the insertion process
    public int expectedNumberOfChildren;    
    public Node parent;
    public ArrayList<Node> children;

    public Node(String name, int year, int expectedNumberOfChildren){
        this.name = name;
        this.year = year;
        this.expectedNumberOfChildren = expectedNumberOfChildren;
        this.children = new ArrayList<Node>(expectedNumberOfChildren);
    }
}
  

Что касается построения дерева из файла данных, я бы использовал Stack структуру со следующим алгоритмом (псевдокод):

• Создайте пустой стек.
• Инициализируйте переменную узла с именем «root» равным null.
• Откройте файл данных для чтения.
• Пока не в конце файла:
  • Прочитайте следующее имя, год и ожидаемое количество дочерних элементов из файла.
  • Создайте новый узел из имени, года и ожидаемого количества дочерних элементов.
  • Если корневой узел равен null:
    • Установите корневой узел на новый узел.
    • Поместите новый узел в стек.
  • В противном случае:
    • Извлеките последний узел из стека (назовите это «родительским»).
    • Установите для родительского узла нового узла родительский элемент, только что извлеченный из стека.
    • Добавьте новый узел в родительский список дочерних элементов.
    • Если фактический размер родительского списка дочерних элементов меньше, чем ожидаемое родительское количество дочерних элементов, первоначально считанных из файла, вставьте родительский элемент обратно в стек.
    • Если ожидаемое количество дочерних элементов нового узла больше нуля, поместите его в стек.
• Закройте файл.

И это все. Когда цикл завершится, «корневой» узел укажет на полностью построенное дерево, предполагая, что входной файл правильно сформирован. (После этого стек больше не нужен.)