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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.87
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
27.02.2012, 23:45     Построение дерева Хаффмана #1
Привет! Есть проблемка. Здесь на форуме нашел темку про код Хаффмана, сейчас уже не буду искать скину отрезок кода.

Принцип Хаффмана(построение дерева): в левое поддерево помещается символ с самой большой частотой повторения, в правое остальные символы. На следующем шаге опять в левое поддерево помещается самый часто повторяющийся, в правое все остальное. При этом к коду левого поддерева добавляется 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++
Построение бинарного дерева C++
C++ Обход дерева Хаффмана
C++ Код Хаффмана реализованный через построение бинарного дерева
Построение В*-дерева C++
Рекурсивное построение дерева C++
Построение дерева в кодировании Хаффмана C++

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

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

Текущее время: 06:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru