#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)
