while (now<>0) do
begin
now = (now - 1) div 2;
{теперь lists[now] - очередная вершина на пути к корню}
end;
(Паскаль) Дерево Хаффмана
Здравствуйте!
У меня есть бинарное дерево, в нём мне нужно найти лист. Это дерево - НЕ дерево поиска, то есть значение левого поддерева не обязательно меньше корня, а правого - больше.
Помогите пожалуйста
У меня есть бинарное дерево, в нём мне нужно найти лист. Это дерево - НЕ дерево поиска, то есть значение левого поддерева не обязательно меньше корня, а правого - больше.
Помогите пожалуйста
Цитата: P*t*
А можно подробнее?
Какие параметры листа даны?
Какие параметры листа даны?
У листа два поля info - символ, и count - кол-во этого символа(ну не считая left, right и тд). Вот.
Нужно искать лист по символу.
Так заведи себе таблицу (массив) указательей на листься дерева, где индекс массива будет код символа. А вообще в инете полно исходников про код Хаффмана, смотрел?
Цитата: Archie
Так заведи себе таблицу (массив) указательей на листься дерева, где индекс массива будет код символа. А вообще в инете полно исходников про код Хаффмана, смотрел?
Да, я глядел, но нашел только по теории. Буду благодарен за хорошую ссылочку:).Я делал в помощью списка.
С массивом не подойдет, так мне от найденного листа потом нужно будет подниматься вверх до корня, чтобы узнать код символа
Цитата: Rifler
Я делал в помощью списка.
С массивом не подойдет, так мне от найденного листа потом нужно будет подниматься вверх до корня, чтобы узнать код символа
С массивом не подойдет, так мне от найденного листа потом нужно будет подниматься вверх до корня, чтобы узнать код символа
Можно использовать массив указателей на листья. Перейдя по указателю оказываемся в листе и далее можно подниматься вверх, используя указатель parent на родителя (он ведь есть?). Также можно организовать и список.
При добалении нового элемента в дерево нужно всего лишь добавить указатель на этот элемент, а не копию этого элемента.
На мой взгляд в этом случае самая удобная организация дерева - в виде одного массива:
lists[0] - корень
lists[a*2+1] - левый потомок А
lists[a*2+2] - правый потомок А
Подниматься вверх до корня элементарно:
lists[0] - корень
lists[a*2+1] - левый потомок А
lists[a*2+2] - правый потомок А
Подниматься вверх до корня элементарно:
Код: