Обрабатывать только одно из поддеревьев - PullRequest
Новая
       42

Обрабатывать только одно из поддеревьев

0 голосов
/ 29 января 2020

Итак, вот оно. У меня было упражнение на экзаменах по структурам данных, где они дали нам класс «Студент» только с двумя атрибутами name (String) и grade (int) с сеттерами, геттерами и конструкторами. Также существовал класс TreeNode и класс BinarySearchTree . У нас был факт, что некоторые объекты Стьюдента были случайно помещены в BSTree . Таким образом, мы должны построить метод, который подсчитывает сколько учеников на дереве, которые не являются листьями дерева (у них есть по крайней мере 1 ребенок), они принадлежат только к правильное поддерево под root и иметь оценку, равную или превышающую 5. Как я могу реализовать это в Java? 

public class Student {
    private String onomep;
    private int vathmos;

    Student(String onomep, int vathmos) {
        this.onomep = onomep;
        this.vathmos = vathmos;
    }

    public void setOnomep(String newOnomep) {
        onomep = newOnomep;
    }
    public void setVathmos(int newVathmos) {
        vathmos = newVathmos;
    }

    public String getOnomep() {
        return onomep;
    }
    public int getVathmos() {
        return vathmos;
    }
}


class TreeNode
{
    private TreeNode left;
    private int item;
    private TreeNode right;

    TreeNode(int data)
    {
        item = data;
        left = right = null;
    }

    public int getNodeData()
    {
        return item;
    }

    public TreeNode getLeftNode()
    {
        return left;
    }

    public TreeNode getRightNode()
    {
        return right;
    }

    public boolean isLeaf()
    {
        return right == null && left == null;
    }

    public void setLeftNode(TreeNode node)
    {
        left = node;
    }

    public void setRightNode(TreeNode node)
    {
        right = node;
    }

    public void insert(int d)
    {
        if(d < item)
        {
            if(left == null)
            {
                left = new TreeNode(d);
            }
            else
            {
                left.insert(d);
            }
        }
        else
        {
            if(right == null)
            {
                right = new TreeNode(d);
            }
            else
            {
                right.insert(d);
            }
        }
    }
}


class BSTree
{
    private TreeNode root;
    private int size;

    BSTree()
    {
        root = null;
    }

    public TreeNode getRoot() {
        return root;
    }

    public int size()
    {
        return size;
    }

    public boolean isEmpty()
    {
        return root == null;
    }

    public void insertElement(int data)
    {
        if(isEmpty())
        {
            root = new TreeNode(data);
        }
        else
        {
            insertNode(data, root);
        }

        size++;
    }
}



public class thema_2_1 {
    public static void main(String[] args) {
        BSTree tree = new BSTree();
        Student s1 = new Student("ytytytyt",3);
        Student s2 = new Student("ytytujyng",6);
        Student s3 = new Student("gfdfgdf",7);
        Student s4 = new Student("gfd",9);
        Student s5 = new Student("gfgd",10);
        Student s6 = new Student("fgddg",2);
        Student s7 = new Student("gdgfdgdgdg",2);
        Student s8 = new Student("asdasd",6);
        Student s9 = new Student("dfdfd",4);
        Student s10 = new Student("hghgh",5);

        public int countSucceededStudents() { 
             //..............?????
        }
      }
   }

1 Ответ

0 голосов
/ 29 января 2020

Правильно начать с правого узла root.

Затем вы передаете этот узел методу, который возвращает int.

Например, что-то вроде 

public int countApplicable(Node n) {
  int result = 0;

  // don't want to throw null pointer errors!
  if (n == null) return result;

  // exclude leaves
  if ((n.left == null) && (n.right == null)) return result;

  // increment the counter if we qualify
  if (n.getthestudent.getthegrade >= 5) {
    result ++;
  }

  // repeat for all subnodes  
  result += countApplicable(n.left);
  result += countApplicable(n.right);

  return result;
}

Так вы видите, как это работает? Это в основном рекурсия. Вызывайте один и тот же метод снова и снова с четко определенной конечной точкой (например, если я ноль или я лист).

...