VPF::компилятор виснет на удаление узлов дерева

ArniLand

Дата 29.9.2010, 20:42 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 227
Регистрация: 17.8.2008

Репутация: нет
Всего: нет

При вызове функции удаления узлов согласно условию if (current.course == 3 && (current.month ==6 || current.month == 7 || current.month==8)) компилятор виснет, т.е. отображаются все узлы дерева, отображается обход дерева, а на моменте когда вызвал функцию удалению строка программа зависает. Не могу понять не так в программе. Что может вызывать зависание программы?

Код программы:

Код


package tree_final;
public class BinaryTree {
    private  Node root;
    public BinaryTree()

    {  root = null;  }

     private void PrintRec(Node root) {
        if (root == null)
            return;
        root.Print();
        System.out.println();
        PrintRec(root.left);
        PrintRec(root.right);
    }
    public void Print(){
    PrintRec(root);
    return;
    }
    public void insert(int data, String name, String surname,
            int course, String ticket, int day, int month, int year ){

        Node n = new Node(data, name, surname, course, ticket, day, month, year);
        if (root == null){
            root = n;
        }
        else {
         Node current = root;
         Node parent;
         while(true) {
             parent = current;
             if(data < current.data){
                 current = current.left;
                }
                if (current == null) {
                    parent.left = n;
                    return;
                }
          else {
                current = current.right;
                if(current == null){
                    parent.right = n;
                    return;

                }
              }
           }
       }
    }



       public Node find(int key){
       Node current = root;

       while(current.data != key){
           if(key < current.data){
               current = current.left;
           }
           else {
                current = current.right;
           }

           if(current == null) {
               return null;
           }

       }
       return current;
    }
      public void inorderPrint(Node root) {
          if (root != null) {
              inorderPrint(root.left);
              System.out.println(root.data + "");
              inorderPrint(root.right);


          }
      }
      public void travers(){
          System.out.println("Inorder traversal");
          inorderPrint(root);
      }

      public boolean delete(int key) {
          Node current = root;
          Node parent = root;
          boolean isLeft = true;




        if (current.course == 3 && (current.month ==6 || current.month == 7 || current.month==8)) {
              while(current.data != key) {
                  parent = current;
                  if(key < current.data) {
                      isLeft = true;
                      current = current.left;
                  }
                  else {
                  if(current == null) {
                    return false;
                    }
                  }
              }

              if(current.left == null && current.right == null) {
                  if (current == root)
                      root = null;

                   else if(isLeft)
                     parent.left = null;
                    else
                      parent.right = null;

              }

               else if (current.right == null)
                  if( current == root)
                      root = current.left;
                  else if(isLeft)
                      parent.left = current.left;
                  else
                      parent.right = current.right;

              else if(current.left == null)
                  if(current == root)
                      root = current.right;
                  else if(isLeft)
                      parent.left = current.right;
                  else
                      parent.right = current.right;

              else {
                  Node successor = getSuccessor(current);

                  if(current == root)
                      root = successor;
                  else if(isLeft)
                      parent.left = successor;
                  else
                      parent.right = successor;

                  successor.left = current.left;

              }

          }
          System.out.println(root.data + "");
          return true;




      }

      private Node getSuccessor(Node delNode)
      {
      Node successorParent = delNode;
      Node successor = delNode;
      Node current = delNode.right;
      while(current != null)
         {
         successorParent = successor;
         successor = current;
         current = current.left;
         }

      if(successor != delNode.right)
         {
         successorParent.left = successor.right;
         successor.right = delNode.right;
         }
      return successor;
      }





    public static void main(String[] args ) {
        BinaryTree theTree = new BinaryTree();

        theTree.insert(1, "vasa", "pupkin", 3, "456987", 2, 7 , 1992);
        theTree.insert(2, "igor", "melnik", 2, "121545", 7, 1 , 1992);
        theTree.insert(3, "dima", "ladov", 2, "787999", 9, 3 , 1991);
        theTree.insert(4, "peta", "mishen", 3, "4477", 3, 8 , 1992);
        theTree.insert(5, "sasha", "ivanov", 2, "57878", 1, 5 , 1992);
        theTree.Print();

        theTree.travers();

        theTree.delete(4);
        theTree.Print();


        
        
        


 }
}
class Node {
        Node left;
        Node right;
        int data;
        String name;
        String surname;
        int course;
        String ticket;
        int day;
        int month;
        int year;
        public Node(int data, String name, String surname, int course, String ticket, int day, int month, int year){
            this.data = data;
            this.name = name;
            this.surname = surname;
            this.course = course;
            this.ticket = ticket;
            this.day = day;
            this.month = month;
            this.year = year;
        }
      public void Print(){
System.out.println("data" + data);
System.out.println("Имя" + name);
System.out.println("Фамилия" + surname);
System.out.println("Курс" + course);
System.out.println("День" + day);
System.out.println("месяц" + month);
System.out.println("год" + year);
}
}

Это сообщение отредактировал(а) ArniLand - 29.9.2010, 20:43

jk1

Дата 29.9.2010, 20:56 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 1168
Регистрация: 17.10.2008
Где: Санкт-Петербург

Репутация: 40
Всего: 75

Давайте разберемся по порядку.

Во-первых, на компилятор Вы грешите зря, он только делает из исходного кода .class-файлы, а вот выполняет их JVM. Если разница между JVM и компилятором для Вас неочевидна, обратитесь к любому учебнику по Java, там это очень подробно освещается.

Во-вторых, JVM не "зависает", Вы сами написали для нее бесконечный цикл и она послушно его выполняет. Обратите внимание вот на эту часть метода удаления:

Код


while (current.data != key) {
                parent = current;
                if (key < current.data) {
                    isLeft = true;
                    current = current.left;
                } else {
                    if (current == null) {
                        return false;
                    }
                }
            }

Когда управление попадает сюда в первый раз, key = 4 и current.data = 1. Прослеживаем выполнение: цикл за циклом выполняется else-ветка, которая не делает ничего. В итоге цикл никогда не завершается.

Логику вашего кода проследить не так просто, но раз уж дерево названо бинарным, вероятно стоит добавить

Код


current = current.right;

в else-ветку.

В-третьих, советую вам использовать дебаггер и отслеживать выполнение программы по шагам - очень помогает.

--------------------

Opinions are like assholes — everybody has one

ArniLand

Дата 29.9.2010, 21:02 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 227
Регистрация: 17.8.2008

Репутация: нет
Всего: нет

1. Добавил в else ветку то, что вы указали. Но всеравно работает бесконечный цикл.
2. Как именно с помощью дебаггера прослеживать программу пошагово?
3. Вам как я понял тоже не понятно, что нужно исправить?

jk1

Дата 29.9.2010, 21:37 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 1168
Регистрация: 17.10.2008
Где: Санкт-Петербург

Репутация: 40
Всего: 75

Цитата

Вам как я понял тоже не понятно, что нужно исправить?

Мне понятно. Почему я сразу этого не сказал? Посмотрите на постановку вопроса:

Цитата

Что может вызывать зависание программы?

именно на этот вопрос я Вам и ответил. Но раз Вас на самом деле интересует не причина, а методы её исправления, давайте копать в эту сторону.

Цитата

Добавил в else ветку то, что вы указали. Но всеравно работает бесконечный цикл.

У меня заработало. Я правда еще пару условий удалил, которые всегда истины или всегда ложны. Вот что работает у меня:

Код


    public boolean delete(int key) {
        Node current = root;
        Node parent = root;
        while (current.data != key) {
            parent = current;
            if (key < current.data) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        if (current.left == null && current.right == null) {
            if (current == root)
                root = null;
            else
                parent.right = null;
        } else if (current.right == null)
            if (current == root)
                root = current.left;
            else
                parent.right = current.right;
        else if (current.left == null)
            if (current == root)
                root = current.right;
            else
                parent.right = current.right;
        else {
            Node successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else
                parent.right = successor;
            successor.left = current.left;
        }
        return true;
    }

Постановку задачи Вы все равно не провели, так что сложно оценить насколько правильно получилось. Смотрите, это то что ожидалось?

Цитата

Как именно с помощью дебаггера прослеживать программу пошагово?

Берите любую популярную IDE: NetBeans, Eclipse, Intelij Idea. В них есть особый режим запуска кода - Debug. В этом режиме исполнение кода будет останавливаться на специально выбранных Вами точках - BreakPoint. После этого можно смотреть значения интересующих переменных, выполнять программы по шагам (trace), обычно клавишей F8 и делать много других интересных вещей.

Это сообщение отредактировал(а) jk1 - 29.9.2010, 21:38

--------------------

Opinions are like assholes — everybody has one

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »