如何设计出上述搜索树效率比较的全代码
时间: 2023-06-17 09:04:04 浏览: 35
以下是一个简单的搜索树实现,包含了生成随机数列、插入节点、中序遍历节点等基本操作,并提供了两个不同的搜索算法(深度优先搜索和广度优先搜索)供比较:
```python
import random
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class SearchTree:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
else:
self._insert(self.root, val)
def _insert(self, node, val):
if val < node.val:
if not node.left:
node.left = TreeNode(val)
else:
self._insert(node.left, val)
else:
if not node.right:
node.right = TreeNode(val)
else:
self._insert(node.right, val)
def inorder(self):
if not self.root:
return []
else:
return self._inorder(self.root)
def _inorder(self, node):
res = []
if node.left:
res += self._inorder(node.left)
res.append(node.val)
if node.right:
res += self._inorder(node.right)
return res
def dfs(self, val):
if not self.root:
return False
else:
return self._dfs(self.root, val)
def _dfs(self, node, val):
if node.val == val:
return True
elif val < node.val and node.left:
return self._dfs(node.left, val)
elif val > node.val and node.right:
return self._dfs(node.right, val)
else:
return False
def bfs(self, val):
if not self.root:
return False
else:
q = [self.root]
while q:
node = q.pop(0)
if node.val == val:
return True
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return False
# 测试代码
s = SearchTree()
nums = [random.randint(0, 100) for _ in range(10)]
for num in nums:
s.insert(num)
print("生成的随机数列为:", nums)
print("中序遍历节点为:", s.inorder())
print("深度优先搜索结果为:", s.dfs(nums[0]))
print("广度优先搜索结果为:", s.bfs(nums[0]))
```
你可以使用该代码来比较深度优先搜索和广度优先搜索两种搜索算法的效率。