1.建立一棵二叉树,所有值均为整数(采用二叉链表存储方式) 2.输出该二叉树的前序、中序、后序遍历序列; 3. 把所有结点的值修改为其绝对值。
时间: 2024-12-22 22:29:00 浏览: 7
1. 构建一颗二叉树(所有节点值为整数并使用二叉链表表示),首先需要创建一个二叉链表节点结构,包含整数值`val`,以及指向左子节点`left`和右子节点`right`的指针。创建二叉树的一般步骤是通过递归或迭代的方式,将每个节点插入到正确的位置,根据给定的整数数组或输入流。
```python
class Node:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_binary_tree(values):
if not values:
return None
root = Node(values[0])
queue = [root]
for value in values[1:]:
current_node = queue.pop(0)
if value is not None:
current_node.left = Node(value)
queue.append(current_node.left)
if value is not None and len(values) > 1:
current_node.right = Node(values[queue.index(current_node) + 1])
queue.append(current_node.right)
return root
```
2. 输出二叉树的遍历序列:
- 前序遍历(根-左-右):
```python
def pre_order_traversal(node):
if node is not None:
print(node.val, end=" ")
pre_order_traversal(node.left)
pre_order_traversal(node.right)
# 调用函数
pre_order_traversal(root)
```
- 中序遍历(左-根-右):
```python
def in_order_traversal(node):
if node is not None:
in_order_traversal(node.left)
print(node.val, end=" ")
in_order_traversal(node.right)
# 调用函数
in_order_traversal(root)
```
- 后序遍历(左-右-根):
```python
def post_order_traversal(node):
if node is not None:
post_order_traversal(node.left)
post_order_traversal(node.right)
print(node.val, end=" ")
# 调用函数
post_order_traversal(root)
```
3. 修改所有节点的值为它们的绝对值:
```python
def absolute_values(node):
if node is not None:
node.val = abs(node.val)
absolute_values(node.left)
absolute_values(node.right)
# 调用函数
absolute_values(root)
```
阅读全文