Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > Удаления узлов из дерева

Автор: ArniLand 22.9.2010, 20:35

По заданию нужно реализовать удаление узлов ( студенты которые служат в армии) из дерева. Не могу разобраться с ним, не могли бы привести пример пожалуйста и объяснить принцип удаления.

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

Код


/*На операторе return выдается ошибка - несовместимые типы. Не могу понять, что с чем не совместимо получается в программе. Разъясните пожалуйста, что я не так сделал.*/
package btree;
import java.io.*;
public class BinaryTree {
    public Node root;
    public BinaryTree()

    {  root = null;  }

    public void insert(int data, String name, String surname,
            String course, String ticket, String army){

        Node n = new Node(data, name, surname, course, ticket, army);
        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 BinaryTree 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; //ошибку выдает на этой строке
    }

}
 
class bTreeApp {
    public static void main(String[] args ) {
        BinaryTree theTree = new BinaryTree();
        theTree.insert(1, "vasa", "pupkin", "3", "456987", "Yes");
        theTree.insert(2, "ivan", "ivanov", "2", "789898", "No");
        theTree.insert(4, "dima", "vengel", "3", "7896546", "No");
    }
}

class Node {
        Node left;
        Node right;
        int data;
        String name;
        String surname;
        String course;
        String ticket;
        String army;
        public Node(int data, String name, String surname, String course, String ticket, String army){
            this.data = data;
            this.name = name;
            this.surname = surname;
            this.course = course;
            this.ticket = ticket;
            this.army = army;
        }
    }

Автор: world 22.9.2010, 20:48

Я смотрю Вы реализуете бинарное дерево, поэтому будем рассматривать удаление элемента в нём

Случай 1. У удаляемого узла нет потомков
Просто удалили узел и всё.

Случай 2. У удаляемого узла 1 потомок
Ставим потомка на место удаляемого элемента и удаляем необходимый узел.

Случай 3. У удаляемого узла 2 потомка
Находим либо самый правый элемент левого поддерева (в левом элементе идём всегда по правой ветки пока ещё будут элементы в право.)
либо самый левый элемент правого поддерева(уж это как сами решите) и ставим его на место удаляемого. После этого удаляем необходимый узел.

Если интересует могу привести код класса на C#, увы Java класс написанный для этих же целей удалил..

Автор: ArniLand 22.9.2010, 21:47

а как реализовать это условием того, что нужно удалять студентов которые служат в армии, то есть удалять узлы при условие?

Код


army = "Yes"

Автор: mstalker26 23.9.2010, 00:40

Расскажите лучше, чего попробовали и какие мысли есть (пусть самые бредовые). А то уже третья тема в стиле "как там, напишите". Мы, конечно, напишем, но в голове-то Вашей знаний от этого не прибавится.

P.S. Все вышеизложенное является только моим "имхом" smile

Автор: world 23.9.2010, 00:57

Цитата

Есть такая мысль делаем обход дерева и удаляем все узлы, где

Код


Army == "Yes"

Пример обхода дерева (прямой кажется называется)
-проверяем узел
-проверяем левый потомок
-проверяем правый потомок

Цитата

Расскажите лучше, чего попробовали и какие мысли есть (пусть самые бредовые)

Вот это правильно конечно.

ЗЫ Обход дерева у меня то же есть только на C#

Автор: ArniLand 23.9.2010, 08:04

Не могли бы выложить пример на C#, если тут нельзя, можете в ЛС отправить

Автор: ArniLand 23.9.2010, 12:28

world, нужно реализовывать все три случая? Мне нужен обход в ширину -
я так  реализовал. Правильно?
public void preorderPrint(Node root) {
          if (root == null) {
              System.out.println(root.data + "");
              preorderPrint(root.left);
              preorderPrint(root.right);

          }

Автор: world 23.9.2010, 16:08

Цитата

Мне нужен обход в ширину -
я так реализовал. Правильно?

Реализовали правильно.

Теперь, что касается удаления. Кидаю код прям здесь. Только сразу извиняюсь перепутал, что дерево у меня на С++

Код


void Remove(Node now)
    {
        Node* parent = now->Parent;
//Если нет потомков
        if(now->Left == NULL && now->Right == NULL)
        {
            if(parent != NULL && parent->Left == now)
            {
                parent->Left = NULL;
            }
            if(parent != NULL && parent->Right == now)
            {
                parent->Right = NULL;
            }
            delete now;
                    printf("Key is deleted!\n");
            return;
        }
//Если есть только правый потомок
        if(now->Left == NULL)
        {
            if(parent != NULL && parent->Left == now)
            {
                parent->Left = now->Right;
            }
            if(parent != NULL && parent->Right == now)
            {
                parent->Right = now->Right;
            }
            Node* next = now->Right;
            next->Parent = parent;
            delete now;
            printf("Key is deleted!\n");
            return;
        }
//Если есть только левый потомок
        if(now->Right == NULL)
        {
            if(parent != NULL && parent->Left == now)
            {
                parent->Left = now->Left;
            }
            if(parent != NULL && parent->Right == now)
            {
                parent->Right = now->Left;
            }
            Node* next = now->Left;
            next->Parent = parent;
            delete now;
            printf("Key is deleted!\n");
            return;
        }
//Если оба потомка
        tmp = now->Right;
//Ищем самый левый элемент правого поддерева
        while(tmp->Left != NULL)
        {
            tmp = tmp->Left;
        }
        Node* t = tmp->Parent;
        if(t->Right != tmp)
        {
            t->Left = tmp->Right;
        }
        if(parent != NULL && parent->Left == now)
        {
            parent->Left = tmp;
        }
        if(parent != NULL && parent->Right == now)
        {
            parent->Right = tmp;
        }
        tmp->Left = now->Left;
        t = tmp->Left;
        t->Parent = tmp;
        if(now->Right == tmp)
        {
            tmp->Right = NULL;
        }
        else
        {
            tmp->Right = now->Right;
        }
        if(root == now)
        {
            root = tmp;
            tmp->Parent = NULL;
        }
        delete now;
        printf("Key is deleted!\n");
    }