Помогите с деревом Опции

[RussoTuristo]

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

Код

unit Laba2;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs;

type
  TForm1 = class(TForm)
  end;
  pNode = ^tNode;
  tNode=record
    w:word;
    Left,right:pNode;
  end;
  opt=object(tree)
  public
  root:pNode;
  private
  function Createnode:pNode;
  function inspath(var t:pNode; L:byte; W:word):boolean;
  function decode:byte; //!!!!
  end;

var
  Form1: TForm1;

implementation

Function opt.inspath(var t:pNode; L:byte; w:word):boolean;
var result:boolean;
begin
  if L>0 then
  begin
    if t^.left=nil then
    begin
      t^.left:=createnode;
      inspath:=inspath(t^.left,L-1,w)
    end
    else
    begin
      result:=inspath(t^.left,L-1,w);
      if not result then
      if t^.right=nil then
      begin
        t6.right:=createnode;
        inspath:=inspath(t^.right,L-1,w)
      end
      else inspath:=inspath(t^.right,L-1,w)
    end
  end
  else if (t^.left=nil) and (t^.right=nil) and (t^.w=0) then
  begin
    t^.w:=w;
    inspath:=true
  end
  else inspath:=false
end;

end.

Сообщение отредактировано: RussoTuristo - 16.10.2008 20:40

[volvo]

Что-то вот такого типа:

function decode(root: pnode): word;
begin
  if (root^.left = nil) and (root^.right = nil) then decode := root^.w
  else begin

    if GetNextBit then decode := decode(root^.right)
    else decode := decode(root^.left);

  end;
end;

, где GetNextBit - функция, получающая следующий бит из кодированного потока данных(Function GetNextBit: Boolean, возвращает True, если очередной бит = 1 и False - если он = 0).

Вызывать как-то так:

while { поток не пуст } do begin
  DecodedValue := decode(RootOfHuffmanTree);

  {
    Ну, и делать то, что тебе надо делать с полученным значением.
    Писать DecodedValue в выходной поток, наверное...
  }
end;

Сообщение отредактировано: volvo - 19.10.2008 13:43

[RussoTuristo]

Были проблемы с институтом, пришлось на время забросить л/р ... Логика задачи в принципе понятна, а как сделать ввод дерева? (чтоб его инерпретировать, его следует сначала задать ...) Работаю в Delphi и подозреваю, что нужно использовать класс TTree, но ничего про него не знаю.

+Эту задачу надо рещить с использованием абстрактного типа данных - АТД(стек или очередь) Я думаю здесь можно использовать стек(записывать туда декодированные[функция decode] данные, а потом из него сразу и вывод данных на экран сделать), надеюсь я правильно понял ...