实现链式存储二叉树构建,完成查找、求树高度、中序遍历、先遍历、后序遍历和层序遍历的程序,并用相关数据进行测试。给出算法的时间和空间复杂度。
时间: 2023-06-05 14:48:03 浏览: 61
链式存储二叉树的构建可以使用链表来实现,每个节点包含左右子节点的指针。以下是实现查找、求树高度、中序遍历、先遍历、后序遍历和层序遍历的程序:
```python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, data):
node = Node(data)
if self.root is None:
self.root = node
else:
queue = [self.root]
while queue:
curr = queue.pop(0)
if curr.left is None:
curr.left = node
break
elif curr.right is None:
curr.right = node
break
else:
queue.append(curr.left)
queue.append(curr.right)
def search(self, data):
if self.root is None:
return False
else:
queue = [self.root]
while queue:
curr = queue.pop(0)
if curr.data == data:
return True
if curr.left is not None:
queue.append(curr.left)
if curr.right is not None:
queue.append(curr.right)
return False
def height(self):
if self.root is None:
return 0
else:
queue = [self.root]
height = 0
while True:
level_size = len(queue)
if level_size == 0:
return height
height += 1
while level_size > 0:
curr = queue.pop(0)
if curr.left is not None:
queue.append(curr.left)
if curr.right is not None:
queue.append(curr.right)
level_size -= 1
def inorder(self, node):
if node is not None:
self.inorder(node.left)
print(node.data, end=' ')
self.inorder(node.right)
def preorder(self, node):
if node is not None:
print(node.data, end=' ')
self.preorder(node.left)
self.preorder(node.right)
def postorder(self, node):
if node is not None:
self.postorder(node.left)
self.postorder(node.right)
print(node.data, end=' ')
def levelorder(self):
if self.root is None:
return
queue = [self.root]
while queue:
curr = queue.pop(0)
print(curr.data, end=' ')
if curr.left is not None:
queue.append(curr.left)
if curr.right is not None:
queue.append(curr.right)
# 测试代码
tree = BinaryTree()
tree.insert(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
tree.insert(5)
tree.insert(6)
tree.insert(7)
print(tree.search(5)) # True
print(tree.search(8)) # False
print(tree.height()) # 3
tree.inorder(tree.root) # 4 2 5 1 6 3 7
print()
tree.preorder(tree.root) # 1 2 4 5 3 6 7
print()
tree.postorder(tree.root) # 4 5 2 6 7 3 1
print()
tree.levelorder() # 1 2 3 4 5 6 7
print()
```
时间复杂度:
- 插入节点:O(n),其中 n 为节点数,最坏情况下需要遍历所有节点。
- 查找节点:O(n),最坏情况下需要遍历所有节点。
- 求树高度:O(n),最坏情况下需要遍历所有节点。
- 中序遍历、先序遍历、后序遍历:O(n),需要遍历所有节点。
- 层序遍历:O(n),需要遍历所有节点。
空间复杂度:
- 插入节点、查找节点、求树高度、中序遍历、先序遍历、后序遍历、层序遍历:O(n),需要存储所有节点。