Структуры данных бинарное упорядоченное несбалансированное дерево

    Дисциплина: Программирование
    Тип работы: Курсовая
    Тема: Структуры данных бинарное упорядоченное несбалансированное дерево

    Казанский Государственный Технический Университет
    им. А. Н. Туполева
    Курсовая работа
    по программированию
    на тему
    Структуры данных:
    бинарное упорядоченное несбалансированное дерево
    Выполнил: Зверев И. М.
    Проверил: Рахматуллин А. И.
    Казань
    2003
    План работы:
    Pascal и С++
    Требуется написать программу, реализующую основные операции работы с деревом. Причём, обязательным условием является использование структуры данных класс для описания дерева и
    методов работы с ним.
    Описание ведётся для кода на
    Pascalе, отличия для С++ будут указаны ниже.
    В программе основным элементом является класс
    TTree
    . Его методы – это основные процедуры работы с деревом:
    reate – конструктор класса – процедура, создающая дерево,
    Add – метод добавления элемента в дерево,
    Del – метод удаления элемента из дерева,
    View – метод вывода элементов дерева на экран,
    Exist – метод проверки существования элемента с некоторым ключом, по сути поиск элемента,
    Destroy – деструктор класса – процедура, удаляющая дерево.
    Рассмотрим алгоритмы работы процедур.
    Create – создание дерева. Присваивает полю
    Root (корень) значение
    nil – указателя, который никуда не указывает.
    Add – добавление элемента в дерево. Для построения дерева используем следующий алгоритм. Первый элемент помещаем в корень (инициализируем дерево). Далее поступаем следующим
    образом. Если добавляемый в дерево элемент имеет ключ больший, чем ключ узла, то, если узел не лист, обходим его справа. Если добавляемый элемент имеет ключ не больший чем ключ узла,
    то, если узел не лист, обходим его слева. Если дошли до листа, то добавляем элемент соответственно справа или слева.
    Del – удаление элемента из дерева.
    Удаление узла довольно просто если он является листом или имеет одного потомка. Например, если требуется удалить узел с ключом М надо просто заменить правую ссылку узла К на
    указатель на L. Трудность заключается в удалении узла с двумя потомками, поскольку мы не можем указать одним указателем на два направления.
    Узла с
    ключем, равным
    х, нет.
    Узел с
    ключем, равным
    х, имеет не более одного потомка.
    Узел с
    ключем, равным
    х, имеет двух потомков
    Вспомогательная рекурсивная процедура
    del вызывается только в случае, когда удаляемый узел имеет двух потомков. Она “спускается вдоль” самой правой ветви левого поддерева удаляемого узла
    q^ (при вызове процедуры ей передается в качестве параметра указатель на левое поддерево) и, затем, заменяет существенную информацию (в нашем случае ключ
    data) в
    q^ соответствующим значением самого правого узла
    r^ этого левого поддерева, после чего от
    r^ можно освободиться.
    View - печать дерева, обходя его справа налево. Чем дальше элемент от корня, тем больше ему будет предшествовать пробелов, т. о. путём несложного алгоритма получается
    вполне удобно читаемое дерево.
    Exist – проверка существования элемента с заданным ключом. Ищем элемент, двигаясь от корня и переходя на левое или правое поддерево каждого узла в зависимости от его
    ключа.
    Destroy – удаление дерева. Обходя дерево слева направо, удаляет элементы. Сначала удаляются потомки узла, затем сам узел.
    Различия между описаниями кодов программах на разных языках относятся в основном к конструкторам и деструкторам. В .
    pas программах они определяются директивами и вызываются явно как методы класса из программы, а в .
    конструктор вызывается при создании элемента класса и деструктор автоматически при выходе из программы (для чего объект класса размещается в памяти динамически).
    program
    PTree;
    {$APPTYPE CONSOLE}
    type
    TInfo = Byte;
    PItem = ^Item;
    Item = record
    Key:
    TInfo;
    Left, Right:
    PItem;
    TTree = class
    private
    Root:
    PItem;
    public
    procedure Add(Key:
    TInfo);
    procedure Del(Key:
    TInfo);
    procedure Exist(Key:
    TInfo);
    //-------------------------------------------------------------
    constructor
    TTree.Create;
    begin
    end;
    //-------------------------------------------------------------
    procedure
    TTree.Add(Key:
    TInfo);
    procedure
    IniTree(
    var P:
    PItem; X:
    TInfo); //
    создание
    корня
    дерева
    begin
    P^.Key :=X;
    P^.Left := nil;
    P^.Right := nil;
    procedure
    InLeft (
    var P:
    PItem; X :
    TInfo); //
    добавление
    узла
    слева
    var R :
    PItem;
    begin
    R^.Key := X;
    R^.Left := nil;
    R^.Right := nil;
    P^.Left := R;
    procedure
    InRight (
    var P:
    PItem; X :
    TInfo); //
    добавить
    узел
    справа
    var R :
    PItem;
    begin
    R^.Key := X;
    R^.Left := nil;
    R^.Right := nil;
    P^.Right := R;
    procedure
    Tree_Add (P:
    PItem; X :
    TInfo);
    var OK: Boolean;
    begin
    while not OK do begin
    P^.Key
    then //посмотреть направо
    P^.Right
    nil //правый узел не
    then P :=
    P^.Right //обход справа
    else
    begin //правый узел - лист и надо добавить к нему элемент
    InRight (P, X); //и конец
    OK :=
    true;
    else //посмотреть налево
    P^.Left
    nil //левый узел не
    then P :=
    P^.Left //обход слева
    else
    begin //левый узел -лист и надо добавить к нему элемент
    InLeft(P, X); //и конец
    OK := true
    цикла
    while
    begin
    if Root = nil
    then
    IniTree(Root, Key)
    else
    Tree_Add(Root, Key);
    end;
    //-------------------------------------------------------------
    procedure
    TTree.Del(Key:
    TInfo);
    procedure Delete (
    var P:
    PItem; X:
    TInfo);
    var Q:
    PItem;
    procedure Del(
    var R:
    PItem);
    //процедура удаляет узел имеющий двух потомков, заменяя его на самый правый
    //узел левого поддерева
    begin
    R^.Right
    then //обойти дерево справа
    R^.Right)
    else begin
    //дошли до самого правого узла
    //заменить этим узлом удаляемый
    Q^.Key :=
    R^.Key;
    Q := R;
    R :=
    R^.Left;
    //Del
    begin //Delete
    nil then //
    искать
    удаляемый
    узел
    P^.Key then
    Delete(
    P^.Left, X)
    else
    P^.Key then
    Delete
    P^.Right, X) //искать в правом поддереве
    else
    begin
    //узел найден, надо его удалить
    //сохранить ссылку на удаленный узел
    Q := P;
    Q^.Right = nil then
    //справа
    //и ссылку на узел надо заменить ссылкой на этого потомка
    P :=
    Q^.Left
    else
    Q^.Left = nil then
    //слева
    //и ссылку на узел надо заменить ссылкой на этого потомка
    P :=
    P^.Right
    else //узел имеет двух потомков
    Q^.Left);
    else
    WriteLn(\'Такого элемента в дереве нет\');
    end;
    begin
    end;
    //-------------------------------------------------------------
    procedure
    TTree.View;
    procedure
    PrintTree(R:
    PItem; L: Byte);
    i: Byte;
    begin
    nil then begin
    PrintTree(
    R^.Right, L + 3);
    i := 1 to L do
    Write(\'
    WriteLn(
    R^.Key);
    PrintTree(
    R^.Left, L + 3);
    begin
    PrintTree (Root, 1);
    end;
    //-------------------------------------------------------------
    procedure
    TTree.Exist(Key:
    TInfo);
    procedure Search(
    var P:
    PItem; X:
    TInfo);
    begin
    if P = nil then begin
    WriteLn
    (\'Такого элемента нет\');
    else
    if X P^.
    then //ищется в правом поддереве
    Search (P^. Right, X)
    else
    P^. Key then
    Search (P^. Left, X)
    else
    WriteLn
    (\'Есть такой элемент\');
    end;
    begin
    end;
    //-------------------------------------------------------------
    destructor
    TTree.Destroy;
    procedure
    Node_Dispose(P:
    PItem);
    //Удаление узла и всех его потомков в дереве
    begin
    nil then begin
    P^.Left nil then
    Node_Dispose (
    P^.L...

    Забрать файл

    Похожие материалы:


ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены