Изучение языка программирования Python

жүктеу/скачать 1,23 Mb.

Pdf көрінісі

бет	13/14
Дата	04.03.2023
өлшемі	1,23 Mb.
	#171016

1 ... 6 7 8 9 10 11 12 13 14

Байланысты:
python
бб, соц лекция, algebra-analitika, Практикалық жұмыс 6-7

Бинарное дерево поиска

3.

Алгоритм быстрой сортировки
def partition(alist, left, right):
#Середина
x = alist[left + (right - left) // 2]
i = left
j = right
while i < j:
print(alist)
while alist[j] > x and not j < left:
j -= 1
while alist[i] right:
i += 1
if i < j:
#Меняем местами переменные
alist[i],alist[j] = alist[j],alist[i]
j -= 1
return j
def quickSort(alist, left, right):
if right > left:
q = partition(alist, left,right)
quickSort(alist,left,q)
quickSort(alist, q+1, right)
4.

Бинарный поиск
def binarySearch(lst, key):
l = 0
#начало
r = len(lst)
#конец
while l < r - 1:
m = l + (r - l) // 2
#Середина списка
if lst[m] > key:
r = m
else:
l = m
if lst[l] == key:
return str(lst[l]) + "\nНайдено"
else:
return("Не найдено")
Бинарное дерево поиска
Сначала определим класс дерева –
TreeItem
, встречаемый ранее и
добавим поле
key
(значение узла).
class TreeItem:
def __init__(self, key = None):
self.right = None

28
self.left = None
self.key = key
Зададим начальные значения узлов.
root = TreeItem(200)
root.left=TreeItem(42)
root.right=TreeItem(420)
Опишем функцию
insertItem
добавления элемента в дерево. Это
сделать можно, только найдя его место. Для этого нам потребуется функция
поиска элемента в дереве. Для удобства добавим комментарий о том, справа
или слева от какого узла помещен новый элемент.
def insertItem(inp):
global root
if root:
curItem = root
#Поиск нужного места и вставка нового элемента
while not curItem == None and not curItem.key == inp:
if curItem.key > inp:
if curItem.left == None or curItem.left.key ==
None:
print("Помещаем слева от
"+str(curItem.key))
curItem.left = TreeItem(inp)
break
else:
#Переход влево
curItem = curItem.left
elif curItem.right == None:
print("Помещаем справа от " + str(curItem.key))
curItem.right = TreeItem(inp)
break
else:
if curItem.right == None or curItem.right.key
== None:
print("Помещаем справа от " +
str(curItem.key))
curItem.right = TreeItem(inp)
break
else:
#Переход вправо
curItem = curItem.right
else:
root = TreeItem(inp)

жүктеу/скачать 1,23 Mb.

Достарыңызбен бөлісу:

1 ... 6 7 8 9 10 11 12 13 14