编写算法先序遍历二叉树
时间: 2023-10-12 11:15:19 浏览: 45
先序遍历二叉树的算法如下:
1. 如果二叉树为空,则返回。
2. 访问根节点。
3. 递归遍历左子树。
4. 递归遍历右子树。
以下是使用 Python 实现的代码:
```python
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def preorder_traversal(root):
if root:
print(root.data)
preorder_traversal(root.left)
preorder_traversal(root.right)
```
其中,Node 类表示二叉树的节点,包含左右子节点和数据。preorder_traversal 函数接收二叉树的根节点作为参数,按照先序遍历的顺序遍历整棵树,并打印出每个节点的数据。
相关问题
编写先序遍历算法
先序遍历是二叉树遍历的一种方式,遍历顺序为:根节点 -> 左子树 -> 右子树。以下是先序遍历的算法实现:
1. 如果当前节点为空,则返回。
2. 对于当前节点,先输出当前节点的值。
3. 递归遍历当前节点的左子树。
4. 递归遍历当前节点的右子树。
以下是先序遍历的算法实现示例(假设二叉树使用链表存储):
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_traversal(root: TreeNode):
if not root:
return
print(root.val)
preorder_traversal(root.left)
preorder_traversal(root.right)
```
代码中的 `TreeNode` 类定义了二叉树的节点结构。函数 `preorder_traversal` 实现了先序遍历,它首先输出当前节点的值,然后递归遍历左子树和右子树。如果当前节点为空,则函数直接返回。
编写求二叉树先序遍历的算法程序
以下是求二叉树先序遍历的算法程序(使用递归实现):
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
res = [root.val]
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
```
其中,`TreeNode` 是二叉树的节点类,包含值 `val`、左子树 `left`、右子树 `right`。`preorderTraversal` 函数接受根节点 `root`,返回一个列表,表示先序遍历结果。具体实现思路为:先访问根节点,再递归访问左子树和右子树。如果根节点为 `None`,直接返回空列表。