python实现先根遍历
时间: 2024-07-09 14:00:28 浏览: 33
在Python中,先根遍历(Preorder Traversal)是一种用于访问树或二叉树节点的算法,它的顺序是根节点 -> 左子树 -> 右子树。下面是使用递归方法实现先根遍历的一种常见方式:
```python
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def preorder_traversal(node):
if node is not None:
# 输出当前节点
print(node.value, end=" -> ")
# 递归遍历左子树
preorder_traversal(node.left)
# 递归遍历右子树
preorder_traversal(node.right)
# 创建一个简单的二叉树示例
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
# 先根遍历
preorder_traversal(root)
```
运行这段代码,你会看到输出类似于 `1 -> 2 -> 4 -> 5 -> 3 ->` 的结果。
相关问题
用Python实现二叉树的遍历
可以回答这个问题。二叉树的遍历有三种方式:前序遍历、中序遍历和后序遍历。以下是Python实现二叉树前序遍历的代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
```
这段代码使用了栈来实现前序遍历,先将根节点入栈,然后弹出栈顶元素,将其值加入结果列表中,再将右子节点和左子节点依次入栈。重复这个过程直到栈为空。
python实现bst中序遍历
BST(二叉搜索树)的中序遍历是将左子树、根节点、右子树按照从小到大的顺序遍历输出。可以使用递归或者迭代的方式实现。
递归实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.helper(root, res)
return res
def helper(self, root, res):
if root:
self.helper(root.left, res)
res.append(root.val)
self.helper(root.right, res)
```
迭代实现:
```python
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
res.append(root.val)
root = root.right
return res
```
其中,使用了一个栈来模拟递归调用的过程。先将左子树全部入栈,然后弹出最底层的左子树,记录值,并将右子树入栈,重复该过程直到栈为空。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)