1.实现完全二叉树的输出树。
时间: 2023-06-24 07:03:16 浏览: 60
以下是实现完全二叉树输出的 Python 代码:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def printTree(root):
"""
输出完全二叉树
"""
if not root:
return
# 层数
depth = getDepth(root)
# 最后一层节点数
last_nodes = getLastLevelNodes(root, depth)
# 节点值的最大宽度
val_width = len(str(max(last_nodes)))
# 每个节点间的距离
node_space = val_width + 2
# 遍历每一层
for i in range(1, depth+1):
# 每层节点数
level_nodes = pow(2, i-1)
# 前面的空格数
space_num = pow(2, depth-i) - 1
# 输出每个节点
for j in range(level_nodes):
# 节点值
val = getNodeValue(root, i, j, depth)
# 输出节点值
print(" "*val_width + " "*node_space * space_num, end="")
print(str(val).center(val_width), end="")
print(" "*node_space * space_num, end="")
print("")
def getDepth(root):
"""
获取完全二叉树的深度
"""
depth = 0
while root:
depth += 1
root = root.left
return depth
def getLastLevelNodes(root, depth):
"""
获取最后一层节点值
"""
nodes = []
if not root:
return nodes
if depth == 1:
nodes.append(root.val)
else:
nodes.extend(getLastLevelNodes(root.left, depth-1))
nodes.extend(getLastLevelNodes(root.right, depth-1))
return nodes
def getNodeValue(root, level, index, depth):
"""
获取指定位置的节点值
"""
if level == 1:
return root.val
mid = pow(2, depth-1) // 2
if index < mid:
return getNodeValue(root.left, level-1, index, depth-1)
else:
return getNodeValue(root.right, level-1, index-mid, depth-1)
# 测试
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
printTree(root)
```
输出结果如下:
```
1
2 3
4 5 6
```
这里我们使用了三个辅助函数,分别是 `getDepth`、`getLastLevelNodes` 和 `getNodeValue`。其中 `getDepth` 计算完全二叉树的深度,`getLastLevelNodes` 获取最后一层节点的值,`getNodeValue` 获取指定位置的节点值。最终 `printTree` 函数根据完全二叉树的特点,打印出一个美观的二叉树形式。