Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.87
VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
#1

Построение дерева Хаффмана - C++

27.02.2012, 23:45. Просмотров 2997. Ответов 0
Метки нет (Все метки)

Привет! Есть проблемка. Здесь на форуме нашел темку про код Хаффмана, сейчас уже не буду искать скину отрезок кода.

Принцип Хаффмана(построение дерева): в левое поддерево помещается символ с самой большой частотой повторения, в правое остальные символы. На следующем шаге опять в левое поддерево помещается самый часто повторяющийся, в правое все остальное. При этом к коду левого поддерева добавляется 0, к коду правого 1.

Я не очень понимаю как здесь должны использоваться рекурсивные функции? кто-то может разобраться?

Вот построение дерева и построение кодов:
построение кодов
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void makeCodes(sym *root)
{
        if(root->left)
        {
                strcpy(root->left->code,root->code);
                strcat(root->left->code,"0");
                makeCodes(root->left);
        }
        if(root->right)
        {
                strcpy(root->right->code,root->code);
                strcat(root->right->code,"1");
                makeCodes(root->right);
        }
}
создание дерева хаффмана:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
sym *makeTree(sym *psym[],int k)
{
        sym *temp;
        temp=(sym*)malloc(sizeof(sym));
        temp->freq=psym[k-1]->freq+psym[k-2]->freq;
        temp->code[0]=0;
        temp->left=psym[k-1];
        temp->right=psym[k-2];
 
        if(k==2)
                return temp;
        else //внесение в массив в нужное место элемента дерева Хофмана
        {
                for(int i=0;i<k;i++)
                        if (temp->freq>psym[i]->freq)
                        {       
                                for(int j=k-1;j>i;j--)
                                        psym[j]=psym[j-1];                                                                      
                                
                                psym[i]=temp;
                                break;
                        }               
        }
return makeTree(psym,k-1);
}
на всякий случай вот еще вывод(его я писал сам, может здесь что-то неправильно, потому криво выводит?

C++
1
2
3
4
5
6
7
8
9
10
    void outTree(sym *root, int step) {
        
        if(root != NULL) {
            outTree(root->left, step+1);
            for(int i = 1; i <= 2*step; i++) 
                cout << "\t";
            printf("%s\n", root->code);
            outTree(root->right, step+1);
        }
    }

Итак... На входе имеем строку символов: ACCCCCBBDACD
По хаффману должно получиться( от руки )
________ABCD
C_________________ABD
______________A________BD
_____________________B____D
А то что имеем
[IMG]http://s018.***********/i521/1202/5c/970787841d0d.png[/IMG]
Вторая ступень, макс. частота пошла не на ту сторону, направо а не налево, потому и код неправильно - например у буквы А должен быть 111, а он 011.

Не подскажете как поправить?

Добавлено через 1 час 42 минуты
Есть идеи?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.02.2012, 23:45     Построение дерева Хаффмана
Посмотрите здесь:

Построение дерева в кодировании Хаффмана - C++
Написал код, который строит дерево Хаффмана, но ветви этого дерева у меня получаются разные(т.е. построение происходит не оптимально). ...

Код Хаффмана реализованный через построение бинарного дерева - C++
Здравствуйте, есть код Хаффмана реализованный через построение бинарного дерева, узлами которого является элемент типа map ,либо символ и...

Обход дерева Хаффмана - C++
Добрый вечер. Имеем кодовое дерево Хаффмана.(в изображении) До каждого узла данного дерева есть путь из 0 и 1 . Для узла 12 ,...

Запись в файл кодового дерева при сжатии по методу Хаффмана - C++
Программа кодирует файл по Хаффману, сохраняет сжатый файл и декодирует его. Но проблема в том, что в закодированный файл не записывается...

Построение В*-дерева - C++
Задание: Построение B* дерева, добавление вершин и балансировка в случае необходимости. подскажите источники где можно взять код, или...

Построение дерева каталогов - C++
Уважаемые форумчане, подскажите пожалуйста, как на с++ реализовать задание: Построение дерева каталогов

Рекурсивное построение дерева - C++
Здравствуйте ! Как построить рекурсивным образом дерево?

Построение бинарного дерева из строки - C++
Доброго времени суток, уважаемые. Хотел бы спросить у вас спросить совета относительно реализации следующей проблемы: Задано...

Сокобан, и построение дерева решений - C++
Добрый вечер, уважаемые форумчане. Нужна помощь с лабой, которую я реально не могу самостоятельно оформить: Задание -...

Построение сильноветвящегося дерева потомков человека - C++
Всех приветствую. Сам текст задания: Нужно построить дерево потомков человека. Дерево является сильноветвящимся. Каждый узел содержит...

Построение бинарного дерева из двумерного массива - C++
Стыдно, если честно, об этом просить, но &quot;возник стопор&quot; и путных идей не приходит. Суть задачи: Есть массив n*n состоящий из целых...

Построение бинарного дерева. Где ошибка? - C++
Насколько понял, tree-&gt;left, tree-&gt;right указывает на NULL. Почему, не могу разобратся. #include &lt;iostream&gt; #include &lt;ctime&gt; using...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru