-
Notifications
You must be signed in to change notification settings - Fork 8
/
PyBintree.py
142 lines (128 loc) · 4.15 KB
/
PyBintree.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
class binaryTree:
def __init__(self, nodeData, left=None, right=None):
self.nodeData = nodeData
self.left = left
self.right = right
def __str__(self):
return str(self.nodeData)
def traverse(tree):
if tree.left != None:
traverse(tree.left)
if tree.right != None:
traverse(tree.right)
print(tree.nodeData)
tree = binaryTree("Root")
BranchA = binaryTree("Branch A")
BranchB = binaryTree("Branch B")
tree.left = BranchA
tree.right = BranchB
LeafC = binaryTree("Leaf C")
LeafD = binaryTree("Leaf D")
LeafE = binaryTree("Leaf E")
LeafF = binaryTree("Leaf F")
BranchA.left = LeafC
BranchA.right = LeafD
BranchB.left = LeafE
BranchB.right = LeafF
graph = {'A': ['B', 'F'],
'B': ['A', 'C'],
'C': ['B', 'D'],
'D': ['C', 'E'],
'E': ['D', 'F'],
'F': ['E', 'A']}
def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
print("Ending")
return path
for node in graph[start]:
print("Checking Node ", node)
if node not in path:
print("Path so far ", path)
newp = find_path(graph, node, end, path)
if newp:
return newp
def snort(data):
for sindex in range(0, len(data)):
minindex = sindex
for neindex in range(sindex+1, len(data)):
if data[neindex] < data[minindex]:
minindex = neindex
if minindex != sindex:
data[sindex], data[minindex] = data[minindex], data[sindex]
print(data)
def inort(data):
for scanIndex in range(1, len(data)):
temp = data[scanIndex]
minIndex = scanIndex
while minIndex > 0 and temp < data[minIndex - 1]:
data[minIndex] = data[minIndex - 1]
minIndex -= 1
data[minIndex] = temp
print(data)
def mergeSort(list):
# Determine whether the list is broken into individual pieces.
if len(list) < 2:
return list
# Find the middle of the list.
middle = len(list)//2
# Break the list into two pieces.
left = mergeSort(list[:middle])
right = mergeSort(list[middle:])
# Merge the two sorted pieces into a larger piece.
print("Left side: ", left)
print("Right side: ", right)
merged = merge(left, right)
print("Merged ", merged)
return merged
def merge(left, right):
# When the left side or the right side is empty,
# it means that this is an individual item and is already sorted.
if not len(left):
return left
if not len(right):
return right
# Define variables used to merge the two pieces.
result = []
leftIndex = 0
rightIndex = 0
totalLen = len(left) + len(right)
# Keep working until all of the items are merged.
while (len(result) < totalLen):
# Perform the required comparisons and merge the pieces according to value.
if left[leftIndex] < right[rightIndex]:
result.append(left[leftIndex])
leftIndex += 1
else:
result.append(right[rightIndex])
rightIndex += 1
# When the left side or the right side is longer,
# add the remaining elements to the result.
if leftIndex == len(left) or rightIndex == len(right):
result.extend(left[leftIndex:] or right[rightIndex:])
break
return result
def partition(data, left, right):
pivot = data[left]
lIndex = left + 1
rIndex = right
while True:
while lIndex <= rIndex and data[lIndex] <= pivot:
lIndex += 1
while rIndex >= lIndex and data[rIndex] >= pivot:
rIndex -= 1
if rIndex <= lIndex:
break
data[lIndex], data[rIndex] = data[rIndex], data[lIndex]
print(data)
data[left], data[rIndex] = data[rIndex], data[left]
print(data)
return rIndex
def quickSort(data, left, right):
if right <= left:
return
else:
pivot = partition(data, left, right)
quickSort(data, left, pivot-1)
quickSort(data, pivot+1, right)
return data