按先序遍历顺序输入二叉树的各个结点值,采用二叉链表的存储结构存储该二叉树,然后交换所建立二叉树的所有结点的左右子树,最后将交换左右子树的二叉树按中序遍历顺序输出,并在遍历时求出叶子结点的个数与树的深度,并将其输出。 输入格式 输入数据仅有一行字符串 � S( � S 的长度不超过 40 40),表示二叉树的各个结点值,按先序遍历顺序输入,其中 # 表示空节点。 输出格式 第一行按照中序遍历的顺序输出每个结点的值。 第二行输出叶子结点的个数。 第三行输出树的深度。
时间: 2024-03-10 22:50:20 浏览: 117
好的,我会尽力回答你的问题。根据你的要求,我将利用Python语言来实现该二叉树的操作。以下是代码实现:
```python
class Node:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
def build_tree(s):
if s[0] == '#':
s.pop(0)
return None
root = Node(s[0])
s.pop(0)
root.left = build_tree(s)
root.right = build_tree(s)
return root
def swap_tree(root):
if not root:
return
root.left, root.right = root.right, root.left
swap_tree(root.left)
swap_tree(root.right)
def inorder_traversal(root, res):
if not root:
return
inorder_traversal(root.left, res)
res.append(root.val)
inorder_traversal(root.right, res)
def count_leaf_node(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaf_node(root.left) + count_leaf_node(root.right)
def get_depth(root):
if not root:
return 0
left_depth = get_depth(root.left)
right_depth = get_depth(root.right)
return max(left_depth, right_depth) + 1
s = input().strip()
s_list = list(s)
root = build_tree(s_list)
swap_tree(root)
inorder_res = []
inorder_traversal(root, inorder_res)
print(' '.join(inorder_res))
leaf_node_num = count_leaf_node(root)
print(leaf_node_num)
depth = get_depth(root)
print(depth)
```
运行该代码,输入二叉树的先序遍历序列,即可输出中序遍历序列、叶子节点个数和树的深度。
阅读全文