haav | Дата: Понедельник, 10.02.2014, 14:02 | Сообщение # 1 |
Генералиссимус
Группа: Администраторы
Сообщений: 1363
Статус: 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)
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
|
| |