Бинарное дерево

Юлькин · 29.04.2009, 02:06

Добрый вечер!
Задание: составить программу на Си для построения и обработки двоичного дерева, содержащего узлы типа double. После того как дерево создано, его обработка должна производиться в режиме текстового меню со след. действиями:
1)текстовая визуализация
2)добавление нового узла
3)удаление узла(с перестроением)
4*)проверка является ли дерево самоподобным(подобным своему отражению)

Вот мой код. текстовая визуализация работает в любом варианте, и, если без текстового меню, то работает и все остальное, но как только запихиваю в меню, все перестает работать(( помогите, пожалуйста!

Код:

#include <stdio.h>
#include <queue>
//#define NULL 0
 
class TreeNode;
//void print(double ident);
void work();
 
class TreeNode
{
private:
 
        TreeNode* left;
        TreeNode* right;
 
        double value;
 
public:
 
        TreeNode(double a_value)//constructor
        {
                left = NULL;
                right = NULL;
                value = a_value;
        }
 
        ~TreeNode()//distructor
        {
                if (hasLeft())
                        delete left;
 
                if (hasRight())
                        delete right;
        }
 
        void add(double a_value)//adding new element
        {
                if (a_value < value)
                {
                        if (left == NULL)
                        {
                                left = new TreeNode(a_value);
                                return;
                        }
 
                        left->add(a_value);
                        return;
                }
 
                if (right == NULL)
                {
                        right = new TreeNode(a_value);
                        return;
                }
 
                right->add(a_value);
                //work();
        }
 
        void printSorted()//printing
        {
            printf("%d\n ", value);
 
                if (left != NULL)
                {
                        left->printSorted();
                }
 
 
 
                if (right != NULL)
                {
                        right->printSorted();
                }
        }
///////////////////////
        void comparing()
        {
            if(&left == &right)
            {
                printf("Yes");
            }
            else printf("No");
        }
///////////////////////
 
        void print(int ident)//printing with displacement
        {
                for (int i=0; i<ident; i++)
                {
                        printf(" ");
                }
 
                printf("%.2f\n", value);
                if (left != NULL)
                {
                        left->print(ident + 1);
                }
 
                if (right != NULL)
                {
                        right->print(ident + 1);
                }
                //work();
        }
 
        TreeNode* getLeft()
        {
                return left;
        }
 
        bool hasLeft()
        {
                return left != NULL;
        }
 
        TreeNode* getRight()
        {
                return right;
        }
 
        bool hasRight()
        {
                return right != NULL;
        }
 
        int getValue()
        {
                return value;
        }
 
        void remove(double a_value)
        {
                removeInternal(a_value);
                //work();
        }
 
        TreeNode* removeInternal(double a_value)
        {
                if (a_value < value)
                {
                        if (hasLeft())
                                left = left->removeInternal(a_value);
 
                        return this;
                }
 
                if (a_value > value)
                {
                        if (hasRight())
                                right = right->removeInternal(a_value);
 
                        return this;
                }
 
                if (!hasLeft() && !hasRight())
                {
                        return NULL;
                }
 
                if (!hasLeft())
                {
                        return right;
                }
 
                if (!hasRight())
                {
                        return left;
                }
 
                TreeNode* i = right;
                while(i->hasLeft())
                {
                        i = i->left;
                }
 
                i->left = left;
                return right;
                //work();
        }
};
 
 
void work()
{
        //void print(double ident);
        TreeNode* tree = new TreeNode(9.1);
        tree->add(44.88);
        tree->add(0.8);
        tree->add(-7.9);
        tree->add(10.9);
        tree->add(6.0);
        int n;
        while(true)
        {
        //TreeNode* tree = new TreeNode(9.1);
        printf("\n\nprint 1 for showing tree\n");
        printf("print 2 for adding element\n");
        printf("print 3 for removing element\n");
        printf("print 0 for quit\n");
        scanf("%d", &n);
                //printf("\"%c\"\n",n);
                
        if(n==0)
        {
                break;
        }
        
        if(n==1)
                {
                        //printf("Y");
                        //TreeNode* tree;
                tree->print(0);
                        //work();
                        //return;
                }
        
        if(n==2)
        {
                double e;
                printf("print new element\n");
                scanf("%.2f", &e);
                printf("%.2f", &e);
                tree->add(e);
                
        }
        
        if(n==3)
        {
                double e;
                printf("print element for remove\n");
                scanf("%.2f", &e);
                tree->remove(e);
        }
        }
        
}
int main()
{
 
        /*TreeNode* tree = new TreeNode(9.1);
        tree->add(44.88);
        tree->add(0.8);
        tree->add(-7.9);
        tree->add(10.9);
        tree->add(6.0);*/
        //scanf("%.2f", &e);
        //tree->add(&e);
        //tree->add(45.54);
        //tree->add(3);
        //tree->add(30);
        //tree->add(33);
    //comparing();
        //tree->remove(0);
        //tree->printSorted();
        //tree->print(0);
        //tree->comparing();
        work();
        //printf("\n\n");
        return 0;
}

csbwalker · 29.04.2009, 14:56

Цитата:

Сообщение от Юлькин

Добрый вечер!
Вот мой код. текстовая визуализация работает в любом варианте, и, если без текстового меню, то работает и все остальное, но как только запихиваю в меню, все перестает работать(( помогите, пожалуйста!

Тут все кажется просто))

Вот в этой части точно ошибка:

Код:

        if(n==2)
        {
                double e;
                printf("print new element\n");
                scanf("%.2f", &e);
                printf("%.2f", &e);
                tree->add(e);
                
        }
        
        if(n==3)
        {
                double e;
                printf("print element for remove\n");
                scanf("%.2f", &e);
                tree->remove(e);
        }

Заключается она в том, что "e" у тебя типа double, а в scanf и printf ты отправляешь его как float (%.2f).
Нужно отправлять как %lf (%.2lf) (т.е. фактически long float).
Во-вторых, ты печатаешь в printf адрес переменной e, а не её значение.
И, помойму в scanf, в отличие от printf, все равно, введен "%.2f или %f".

Вот при такой замене у меня все работает:

Код:

        if(n==2)
        {
                double e;
                printf("print new element\n");
                scanf("%lf", &e);
                printf("%0.2lf", e);
                tree->add(e);
                
        }
        
        if(n==3)
        {
                double e;
                printf("print element for remove\n");
                scanf("%lf", &e);
                tree->remove(e);
        }

Если ошибки будут повторятся или появится новые - пиши, че-нить сделаем!

Юлькин · 29.04.2009, 22:44

Спасибо огромное!
а не подскажите как сделать 4*) ?

csbwalker · 30.04.2009, 23:26

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

1. Компилятор все время ругался на несоответствие типов. Подправил:

Код:

double getValue()
{
    return value;
}

2. Изменил функцию print, что бы выводились сообщения "NULL" если одной из двух веток не существует. Сделал это что бы было понятно, ветка левая или правая когда она всего одна. Для простоты дальнейшей отладки.

Код:

        void print(int ident)//printing with displacement
        {
                for (int i=0; i < ident; i++)
                        putchar(' ');
 
                printf("%.2f\n", value);

		if ((left == NULL) && (right == NULL))
			return;

                if (left != NULL)
                {
                        left->print(ident + 1);
                } else
		{
			for (int i=0; i<ident + 1; i++)
                	        putchar(' ');

			printf("NULL\n");
		}
 
		if (right != NULL)
		{       
                        right->print(ident + 1);
                } else
		{
			for (int i=0; i<ident + 1; i++)
                	        putchar(' ');

			printf("NULL\n");
		}
        }

Вторую рекомендацию - крайне рекомендую сделать! Хотя бы на период отладки! Очень облегчает жизнь.

Цитата:

Сообщение от Юлькин

Спасибо огромное!
а не подскажите как сделать 4*) ?

Собственно по делу.
Насколько я понимаю, подобие дерева - это когда его структура идентична структуре его отражения (а отражение - это когда везде все левые и правые ветки меняются местами).
Исходя из этого не вижу другого выхода, кроме как из корня запрашивать всю информацию о структуре дерева и как-то её изучать.
Информацию можно строить по-разному. Я предпочел так:

0. Берем массив (в коде я взял вместо него контейнер типа list, т.к. он поддерживает симметричное отражение и еще пару полезностей).
1. Записываем в массив 0 если нет левой ветки, 1 если есть
2. Если левая ветка есть то запрашиваем у нее такую же информацию, записываем её в тот же массив
3. Если правая ветка есть то запрашиваем у нее такую же информацию, записываем её в тот же массив
4. Записываем в массив 0 если нет правой ветки, 1 если есть

Таким образом, вызвав эту функцию для какой-либо ветки, получим однозначную информацию о её структуре.

На всякий случай приведу пример (NULL - значит этого листа нет), нумерация операций таже что выше:

Код:

Корень
  Узел 1
    Узел 2
      Узел 3
      Узел 4
    Узел 5
  Узел 6
    NULL
    Узел 7

Для него последовательность будет такой:

Код:

1. Существует левая ветвь, так что дописываем 1 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "1"
2. Добавляем информацию о левой ветви
1. Существует левая ветвь, поэтому дописываем 1 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "11"
2. Добавляем информацию о левой ветви
1. Существует левая ветвь, поэтому дописываем 1 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "11"
2. Добавляем информацию о левой ветви
1. Левой ветви не существует, дописываем 0 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "110"
2. Левой ветви не существует, информацию о ней не дописываем
3. Правой ветви не существует, информацию о ней не дописываем
4. Правой ветви не существует, дописываем 0 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "1100"
3. Добавляем информацию о правой ветви
1. Левой ветви не существует, дописываем 0 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "11000"
2. Левой ветви не существует, информацию о ней не дописываем
3. Правой ветви не существует, информацию о ней не дописываем
4. Правой ветви не существует, дописываем 0 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "110000"
4. Существует правая ветвь, поэтому дописываем 1 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "1100001"
3. Добавляем информацию о правой ветви
1. Левой ветви не существует, дописываем 0 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "11000010"
2. Левой ветви не существует, информацию о ней не дописываем
3. Правой ветви не существует, информацию о ней не дописываем
4. Правой ветви не существует, дописываем 0 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "110000100"
4. Существует правая ветвь, поэтому дописываем 1 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "1100001001"
3. Добавляем информацию о правой ветви
1. Левой ветви не существует, дописываем 0 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "11000010010"
2. Левой ветви не существует, информацию о ней не дописываем
3. Добавляем информацию о правой ветви
1. Левой ветви не существует, дописываем 0 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "110000100100"
2. Левой ветви не существует, информацию о ней не дописываем
3. Правой ветви не существует, информацию о ней не дописываем
4. Правой ветви не существует, дописываем 0 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "1100001001000"
4. Существует правая ветвь, поэтому дописываем 1 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "11000010010001"
4. Существует правая ветвь, поэтому дописываем 1 в массив
СОДЕРЖИМОЕ МАССИВА ПОСЛЕ КОМАНДЫ: "110000100100011"

Выполняется последовательно, как написано.
Увеличение отступа - значит спуск на один уровень ниже.
Написал сложно, но на самом деле все намного легче )))

Так вот, если ты применишь этот алгоритм для любого самоподобного дерева, то заметишь что информационные массивы, рассчитанные отдельно для левой и правой ветки, будут являться зеркальными копиями друг друга, например для

Код:

Корень
  Узел 1
    Узел 2
    NULL
  Узел 3
    NULL
    Узел 4

Информация о левой ветке будет 1000, а для правой - 0001.
Так что нам останется только "отразить" один из массивов и посмотреть равны ли они.

Следующим постом, что бы этот не получился слишком длинным, прилагаю свой вариант реализации этого дела.

csbwalker · 30.04.2009, 23:33

Итак, во-первых, добавляем в начало файла инструкции:

Код:

#include <list>

using namespace std;

Первая говорит сама за себя, вторая избавляет от необходимости писать std::list<bool> вместо более простой записи list<bool>

ПРИМЕЧАНИЕ: если пользуешься старой досовской версией борланда то директиву using namespace std писать нельзя, он её не понимает! Просто опусти её, он по факту действует так, как будто она всегда есть.

Дальше, добавляем два метода в класс, один метод - получение информации как описано выше, второй - служит для инициации проверки в корневом узле.
Попробывал откомментить по максимуму, т.к. по себе знаю каково оно разбираться в чужом коде)

Код:

	// Функция получения "карты" ветки, которая содержит однозначную информацию
	// о структуре этой ветки
	void info(list<bool> &lst)
	{
		// Вписываем данные о существовании левой ветки
		lst.push_back(left == NULL);

		// Вписываем информацию о левой ветке, если существует		
		if(left != NULL)
			left->info(lst);

		// Вписываем информацию о правой ветке, если существует
		if(right != NULL)
			right->info(lst);

		// Вписываем данные о существовании правой ветки
		lst.push_back(right == NULL);

	}

	// Функция проверки самоподобия, вызывается ТОЛЬКО для корня
	void similarity()
	{
	list<bool> linfo, rinfo;

		// 1. Проверяем особые ситуации - когда не хватает одной или двух веток

		// 1.1. Если нет не левой ветки, ни правой - то дерево точно самоподобно
	        if((right == NULL) && (left == NULL)) 
		{
			printf("YES\n"); 
			return;
		}

		// 1.2. Усли одной из веток нет (но только одной, т.к. две уже проверили выше), то оно явно не самоподобно
		if((right == NULL) || (left== NULL)) 
		{
			printf("NO\n");
			return;
		}


		// 2. Проверяем обычную ситуацию - когда есть обе ветки
		// Для этого строим карты левой и правой ветки,
		// если дерево самоподобно - то они должны быть зеркальными копиями друг друга
	
		// Получаем информацию о левой ветке
		left->info(linfo);

		// Получаем информацию о правой ветке
		right->info(rinfo);

		// Проверяем, равны ли их длины, если нет - сразу говорим что дерево не самоподобно
		// В принципе, можно и не проверять - дальше проверки все равно не пройдут и выведется тот же результат,
		// но зачем зазря расходовать ресурсы, если и так понятно?
		if (linfo.size() != rinfo.size())
		{
			printf("NO\n");
			return;
		}

		// Зеркально отражаем информацию о правой ветке
		// можно отражать и информацию о левой, это не важно
		// главное - проверить что отражение одной равно прямой другой
		rinfo.reverse();

		// Собственно главная проверка - к чему все шло
		if(linfo == rinfo)
			printf("YES\n");
		else
			printf("NO\n");
		
	}

ну, и наконец, очевидно, в функцию work добавляем:

Код:

if(n==4)
        {
                tree->similarity();
        }

Ну это одна из, я думаю, множества возможных реализаций. Из тех что в данный момент пришли на ум эта мне показалась наиболее разумной, но сама понимаешь за оптимальность не ручаюсь))

P.S. Надеюсь помог и не запутал)

Юлькин · 03.05.2009, 14:27

Спасибо огромное!! буду разбираться)

29.04.2009, 02:06
Helpmaster Member Регистрация: 08.03.2016 Сообщений: 0	Возможно вы не обращали внимания, но на нашем форуме так же есть аналогичные темы Перевод картинки с бумаги на металл, дерево Нужно построить бинарное дерево

29.04.2009, 22:44	#3 (permalink)
Юлькин Новичок Регистрация: 12.04.2009 Сообщений: 7 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	Спасибо огромное! а не подскажите как сделать 4*) ?

Ads
Яндекс Member Регистрация: 31.10.2006 Сообщений: 40200 Записей в дневнике: 0 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 55070

03.05.2009, 14:27	#6 (permalink)
Юлькин Новичок Регистрация: 12.04.2009 Сообщений: 7 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	Спасибо огромное!! буду разбираться)