实现有序表的查找。用二叉链表作为存储结构,输入键值序列建立一棵二叉排序树,然后中序遍历这棵二叉树。分别用堆排序及快速排序算法,对待排序记录进行排序并输出排序结果代码
时间: 2024-05-14 07:18:35 浏览: 20
二叉排序树查找代码:
```python
class BSTNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, key):
if not self.root:
self.root = BSTNode(key)
return
node = self.root
while True:
if node.key == key:
return
elif node.key > key:
if node.left:
node = node.left
else:
node.left = BSTNode(key)
return
else:
if node.right:
node = node.right
else:
node.right = BSTNode(key)
return
def inorder_traversal(self, node, result):
if not node:
return
self.inorder_traversal(node.left, result)
result.append(node.key)
self.inorder_traversal(node.right, result)
def search(self, key):
node = self.root
while node:
if node.key == key:
return True
elif node.key > key:
node = node.left
else:
node = node.right
return False
```
堆排序算法代码:
```python
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
```
快速排序算法代码:
```python
def partition(arr, low, high):
i = low - 1
pivot = arr[high]
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi-1)
quick_sort(arr, pi+1, high)
return arr
```
完整代码如下:
```python
class BSTNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, key):
if not self.root:
self.root = BSTNode(key)
return
node = self.root
while True:
if node.key == key:
return
elif node.key > key:
if node.left:
node = node.left
else:
node.left = BSTNode(key)
return
else:
if node.right:
node = node.right
else:
node.right = BSTNode(key)
return
def inorder_traversal(self, node, result):
if not node:
return
self.inorder_traversal(node.left, result)
result.append(node.key)
self.inorder_traversal(node.right, result)
def search(self, key):
node = self.root
while node:
if node.key == key:
return True
elif node.key > key:
node = node.left
else:
node = node.right
return False
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
def partition(arr, low, high):
i = low - 1
pivot = arr[high]
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi-1)
quick_sort(arr, pi+1, high)
return arr
if __name__ == '__main__':
bst = BST()
arr = [5, 2, 8, 1, 3, 9, 4, 7, 6]
for key in arr:
bst.insert(key)
result = []
bst.inorder_traversal(bst.root, result)
print('BST中序遍历结果:', result)
sorted_arr_heap = heap_sort(arr.copy())
print('堆排序结果:', sorted_arr_heap)
sorted_arr_quick = quick_sort(arr.copy(), 0, len(arr) - 1)
print('快速排序结果:', sorted_arr_quick)
```
输出结果如下:
```
BST中序遍历结果: [1, 2, 3, 4, 5, 6, 7, 8, 9]
堆排序结果: [1, 2, 3, 4, 5, 6, 7, 8, 9]
快速排序结果: [1, 2, 3, 4, 5, 6, 7, 8, 9]
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)