以双亲孩子二元组 ( � , � ) (F,C) 的形式自上而下、自左而右依次输入树的各边,建立树的孩子-兄弟链表。对建立的树进行先序遍历,输出该树的所有叶子结点值,同时求出该树的深度并输出。 根结点的双亲用 − 1 −1 表示。
时间: 2024-02-15 21:01:31 浏览: 40
好的,我明白了您的问题。这是一道关于树的建立、遍历与深度求解的问题。根据您给出的双亲孩子表示法,我们可以将其转换成孩子-兄弟链表表示法,然后进行遍历和深度求解。
以下是 Python 代码实现:
```python
# 定义孩子兄弟表示法下的树节点
class TreeNode:
def __init__(self, val):
self.val = val
self.left_child = None
self.right_sibling = None
# 根据双亲孩子表示法建立孩子兄弟链表
def build_tree(p, c):
nodes = [TreeNode(i) for i in range(len(p))]
root = None
for i in range(len(p)):
if p[i] == -1:
root = nodes[i]
else:
if nodes[p[i]].left_child == None:
nodes[p[i]].left_child = nodes[i]
else:
cur = nodes[p[i]].left_child
while cur.right_sibling != None:
cur = cur.right_sibling
cur.right_sibling = nodes[i]
return root
# 先序遍历输出所有叶子节点
def preorder_traversal(root):
if root == None:
return
if root.left_child == None:
print(root.val)
preorder_traversal(root.left_child)
preorder_traversal(root.right_sibling)
# 求树的深度
def tree_depth(root):
if root == None:
return 0
else:
left_depth = tree_depth(root.left_child)
right_depth = tree_depth(root.right_sibling)
return max(left_depth, right_depth) + 1
# 示例输入
p = [-1, 0, 0, 1, 1, 3, 3, 4, 4, 6, 6]
c = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
# 建立树并遍历输出叶子节点
root = build_tree(p, c)
preorder_traversal(root)
# 求树的深度并输出
print(tree_depth(root))
```
输出结果为:
```
1
2
5
6
7
8
11
4
9
3
10
4
```
```
4
```