FreeBasic
Главная
Вход
Регистрация
Четверг, 28.03.2024, 23:30Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Форум » Freebasic » Исходники » AVL дерево
AVL дерево
haavДата: Понедельник, 10.02.2014, 14:02 | Сообщение # 1
Генералиссимус
Группа: Администраторы
Сообщений: 1361
Репутация: 49
Статус: Offline
Данный код адаптировал с С++ ,  взял отсюда: http://ci-plus-plus-snachala.ru/?p=1081

Что такое AVL дерево, читаем тут: ссылка

Не могу сказать насколько верно построен алгоритм, так же нет гарантии , что в коде нет ошибок , по крайней мере одну ошибку в коде С++ я нашел. Может где то и я допустил ошибки при переписывании кода, по крайней мере я пока их не выявил. Может кому пригодится данная реализация.




Код
#Include "crt.bi"

Type node
      As Integer element
      As node Ptr Left
      As node Ptr Right
      As Integer height
End Type

Type bstree extends Object
      Declare Sub insert(As integer,ByRef As node Ptr)
      Declare Sub del(As Integer, ByRef As node Ptr)
      declare Function deletemin(ByRef As node Ptr)As Integer
      Declare Sub find(As Integer,ByRef As node Ptr)
      declare Function findmin(ByRef As node Ptr)As node Ptr
      declare Function findmax(ByRef As node Ptr)As node Ptr
      Declare Sub makeempty(ByRef As node Ptr)
      Declare Sub copy(ByRef As node Ptr,ByRef As node Ptr)
      declare Function nodecopy(ByRef As node Ptr)As node Ptr
      Declare Sub preorder(As node Ptr)
      Declare Sub inorder(As node Ptr)
      Declare Sub postorder(As node Ptr)
      declare Function bsheight(As node Ptr)As Integer
      declare Function srl(ByRef As node Ptr)As node Ptr
      declare Function drl(ByRef As node Ptr)As node Ptr
      declare Function srr(ByRef As node Ptr)As node Ptr
      declare Function drr(ByRef As node Ptr)As node Ptr
      declare Function max(As Integer,As Integer)As Integer
      declare Function nonodes(As node Ptr)As Integer
End Type

' Inserting a node
Sub bstree.insert(x As integer,ByRef p As node Ptr)
      if (p = NULL) Then
          p = new node
          p->element = x
          p->left=NULL
          p->right = NULL
          p->height=0
          if (p=NULL) Then
              printf (!"Out of Space\n")
          EndIf
      Else
          if (x<p->element) Then
              insert(x,p->left)
              if ((bsheight(p->left) - bsheight(p->right))=2) Then
                  if (x < p->left->element) Then
                      p=srl(p)
                  Else
                      p = drl(p)
                  EndIf
              EndIf
          ElseIf (x>p->element) Then
              insert(x,p->right)
              if ((bsheight(p->right) - bsheight(p->left))=2) Then
                  if (x > p->right->element) Then
                      p=srr(p)
                  Else
                      p = drr(p)
                  EndIf
              EndIf
          Else
              printf(!"Элемет существует\n")
          EndIf
      EndIf
      Dim As integer m,n,d
      m=bsheight(p->left)
      n=bsheight(p->right)
      d=max(m,n)
      p->height = d + 1
End Sub

' Finding the Smallest
Function bstree.findmin(ByRef p As node Ptr) As node Ptr
      if (p=NULL) Then
          printf(!"В дереве нет элементов\n")
          return p
      Else
          Dim pp As  node Ptr = p
          While (pp->left<>NULL)
              pp=pp->Left
              'return p;
          Wend
          return pp
      EndIf
End Function

' Finding the Largest node
Function bstree.findmax(ByRef  p As node Ptr) As node Ptr
      if (p=NULL) Then
          printf(!"В дереве нет элементов\n")
          return p
      Else
          Dim pp As  node Ptr = p
          while(pp->right <>NULL)
              pp=pp->Right
              'return p;
          Wend
          return pp
      EndIf
End Function

' Finding an element
sub bstree.find(x As integer,ByRef p As node Ptr )
      if (p=NULL) Then
          printf(!"Простите, но такого элемента нет\n")
      Else
          if (x < p->element) Then
              find(x,p->left)
          Else
              if (x>p->element) then
                  find(x,p->right)
              else
                  printf(!"Элемент, который вы искали есть в дереве!\n")
              EndIf
          EndIf
      EndIf
End Sub

' Copy a tree
Sub bstree.copy(ByRef p As node Ptr,ByRef p1 As node Ptr)
      makeempty(p1)
      p1 = nodecopy(p)
End Sub

' Make a tree empty
sub bstree.makeempty(ByRef p As node Ptr)
      if (p <> NULL) Then
          makeempty(p->left)
          makeempty(p->right)
          Delete p
          p=NULL
      EndIf
End Sub

' Copy the nodes
Function bstree.nodecopy(ByRef p As node Ptr) As node Ptr
      Dim As node Ptr temp
      if (p=NULL) Then
          return p
      Else
          temp = new node
          temp->element = p->element
          temp->left = nodecopy(p->left)
          temp->right = nodecopy(p->right)
          return temp
      EndIf
End Function

' Deleting a node
sub bstree.del(x As Integer ,ByRef p As node Ptr)
      if (p=NULL) Then
          printf(!"Простите, но такого элемента нет\n")
      elseif ( x < p->element) Then
          del(x,p->left)
      ElseIf (x > p->element) Then
          del(x,p->right)
      elseif ((p->left = NULL) and (p->right = NULL)) Then
          Delete p
          p=NULL
          printf(!"Элемент удален\n")
      ElseIf (p->left = NULL) Then
          p=p->Right
          Delete p
          p=NULL
          printf(!"Элемент удален\n")
      elseif (p->right = NULL) Then
          p=p->Left
          Delete p
          p=NULL
          printf(!"Элемент удален\n")
      Else
          p->element = deletemin(p->right)
      EndIf
End Sub

function bstree.deletemin(ByRef p As node Ptr)As integer
      Dim As Integer c
      printf(!"Выбрано удаление минимального значения\n")
      if (p->left = NULL) Then
          c=p->element
          p=p->Right
          return c
      Else
          c=deletemin(p->left)
          return c
      EndIf
End Function

Sub bstree.preorder(p As node Ptr)
      if (p<>NULL) Then
          Printf(p->element & !"\t")
          preorder(p->left)
          preorder(p->right)
      EndIf
End Sub

' Inorder Printing
Sub bstree.inorder(p As node Ptr)
      if (p<>NULL) Then
          inorder(p->left)
          Printf(p->element & !"\t")
          inorder(p->right)
      EndIf
End Sub

'PostOrder Printing
sub bstree.postorder(p As node Ptr)
      if (p<>NULL) Then
          postorder(p->left)
          postorder(p->right)
          Printf(p->element & !"\t")
      EndIf
End Sub

Function bstree.max(value1 As integer, value2 As Integer) As Integer
      return IIF(value1 > value2 , value1 , value2)
End Function

Function bstree.bsheight(p As node Ptr) As Integer
      Dim As Integer t
      if (p = NULL) Then
          return -1
      Else
          t = p->height
          return t
      EndIf
End Function

Function bstree.srl(ByRef p1 As node Ptr ) As node Ptr
      Dim As node Ptr p2
      p2 = p1->Left
      p1->left = p2->Right
      p2->right = p1
      p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1
      p2->height = max(bsheight(p2->left),p1->height) + 1
      return p2
End Function

Function  bstree.srr(ByRef p1 As node Ptr) As node Ptr
      Dim As node Ptr p2
      p2 = p1->Right
      p1->right = p2->Left
      p2->left = p1
      p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1
      p2->height = max(p1->height,bsheight(p2->right)) + 1
      return p2
End Function

Function bstree.drl(ByRef p1 As node Ptr) As node Ptr
      p1->left=srr(p1->left)
      return srl(p1)
End Function

Function bstree.drr(ByRef p1 As node Ptr)As node Ptr
      p1->right = srl(p1->right)
      return srr(p1)
End Function

Function bstree.nonodes(p As node Ptr) As Integer
      Dim As integer count
      if (p<>NULL) Then
          nonodes(p->left)
          nonodes(p->right)
          count+=1
      EndIf
      return count
End Function

'clrscr();
Dim As node Ptr root,root1,min,max ',flag;
Dim As Integer a,choice,findele,delele_
Dim As bstree bst
'system("clear");
root = NULL
root1=NULL
Printf(!"\n\t\t\t\tАВЛ Дерево\n")
Printf(!"\t\t\t\t:::::::::::::::::::\n")

Do
      Printf(!"\t\t::::::::::::::::::::::::::::::::::::::::::::::::\n")
      Printf(!"\t\t::::1 Вставить новый узел::::::::::::::::\n")
      Printf(!"\t\t::::2 Найти минимальный элемент:::::::::::\n")
      Printf(!"\t\t::::3 Найти максимальный элемент:::::::::::::::\n")
      Printf(!"\t\t::::4 Поиск по значению:::::::::::::::::::\n")
      Printf(!"\t\t::::5 Удалить элемент:::::::::::::::::::\n")
      Printf(!"\t\t::::6 Вариант обхода1:::::::::::::::::\n")
      Printf(!"\t\t::::7 Вариант обхода2::::::::::::::::::\n")
      Printf(!"\t\t::::8 Вариант обхода3::::::::::::::::\n")
      Printf(!"\t\t::::9 Показать высоту дерева:::\n")
      Printf(!"\t\t::::10 Выход:::::::::::::::::::::::::::::\n")
      Printf(!"\t\t::::::::::::::::::::::::::::::::::::::::::::::::\n")

      Printf(!"\nВыберите нужное действие и нажмите Enter: ")
      Input "",choice

      Select Case choice
          case 1
              Printf(!"\n\t\tДобавление нового узла")
              Printf(!"\t\t:::::::::::::\n")
              Printf(!"Введите элемент: ")
              Input "" ,a
              bst.insert(a,root)
              Printf(!"\nНовый элемент добавлен успешно\n")
          case 2
              if (root <>NULL) then
                  min=bst.findmin(root)
                  Printf(!"\nМинимальный элемент в дереве: " & min->element)
              EndIf
          case 3
              if (root <>NULL) then
                  max=bst.findmax(root)
                  Printf(!"\nМаксимальный элемент в дереве: " & max->element)
              EndIf
          case 4
              Printf(!"\nВведите искомый элемент: ")
              Input "",findele
              if (root <> NULL) Then
                  bst.find(findele,root)
              EndIf
          case 5
              Printf(!"\nКакой узел удалять? : ")
              Input "", delele_
              bst.del(delele_,root)
              bst.inorder(root)
              Print
          case 6
              Printf(!"\n\t\tВариант обхода1\n")
              bst.preorder(root)
              Print
          case 7
              Printf(!"\n\t\tВариант обхода2\n")
              bst.inorder(root)
              Print
          case 8
              Printf(!"\n\t\tВарант обхода3\n")
              bst.postorder(root)
              Print
          case 9
              Printf(!"\n\t\tВЫСОТА\n")
              Printf(!"Дерево имеет высоту: " & bst.bsheight(root))
          case 10
              Printf(!"\n\tБлагодарим вас за использование програмы\n")
          Case Else
              Printf(!"Sorry! wrong input\n")
      End Select
      Sleep
      cls
Loop While(choice <> 10)
Прикрепления: 4350583.png (29.4 Kb)


Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
 
Форум » Freebasic » Исходники » AVL дерево
  • Страница 1 из 1
  • 1
Поиск: