1)初始化一个结点。 (2)以(1)中结点作为根结点,使用递归算法创建一棵树。 (3)对树执行先序遍历,并将先序序列输出。 (4)对树执行后序遍历,并将后序序列输出。 B C (5)对树执行层次遍历,并将所得序列输出。 E (6)计算树的深度并输出。
时间: 2023-06-27 14:03:51 浏览: 59
很高兴回答你的问题。
以下是一个简单的Tree Node类的Python实现:
```
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
```
1) 初始化一个结点。
```
root = TreeNode("A")
```
2) 以(1)中结点作为根结点,使用递归算法创建一棵树。
```
root.left = TreeNode("B")
root.right = TreeNode("C")
root.left.left = TreeNode("D")
root.left.right = TreeNode("E")
root.right.right = TreeNode("F")
```
3) 对树执行先序遍历,并将先序序列输出。
```
def preorderTraversal(root):
if not root:
return []
res = []
res.append(root.val)
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
print(preorderTraversal(root)) # output: ['A', 'B', 'D', 'E', 'C', 'F']
```
4) 对树执行后序遍历,并将后序序列输出。
```
def postorderTraversal(root):
if not root:
return []
res = []
res += postorderTraversal(root.left)
res += postorderTraversal(root.right)
res.append(root.val)
return res
print(postorderTraversal(root)) # output: ['D', 'E', 'B', 'F', 'C', 'A']
```
5) 对树执行层次遍历,并将所得序列输出。
```
def levelOrderTraversal(root):
if not root:
return []
res = []
queue = [root]
while queue:
level = []
for i in range(len(queue)):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
print(levelOrderTraversal(root)) # output: [['A'], ['B', 'C'], ['D', 'E', 'F']]
```
6) 计算树的深度并输出。
```
def maxDepth(root):
if not root:
return 0
left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)
return max(left_depth, right_depth) + 1
print(maxDepth(root)) # output: 3
```
希望这能帮到你!
阅读全文