python 树的递归

2024年2月7日发(作者：)

python 树的递归

在Python中，递归是一种常用的编程技术，可以用于解决许多问题，包括树的遍历。下面是一个基本的例子，说明如何使用递归来遍历二叉树。

首先，我们需要定义一个二叉树节点：

python复制代码：

class TreeNode:

def __init__(self, x):

= x

= None

= None

然后，我们可以定义一个递归函数来遍历这棵树。下面是一个基本的先序遍历（preorder）的例子：

python复制代码：

def preorder_traversal(root):

if root is not None:

print() # 访问根节点

preorder_traversal() # 递归遍历左子树

preorder_traversal() # 递归遍历右子树

如果你想进行中序遍历（inorder）或后序遍历

（postorder），只需稍微修改这个函数即可：

中序遍历：

python复制代码：

def inorder_traversal(root):

if root is not None:

inorder_traversal() # 递归遍历左子树

print() # 访问根节点

inorder_traversal() # 递归遍历右子树

后序遍历：

python复制代码：

def postorder_traversal(root):

if root is not None:

postorder_traversal() # 递归遍历左子树

postorder_traversal() # 递归遍历右子树

print() # 访问根节点

请注意，上述代码中的 print 函数只是为了演示目的。在实际应用中，你可能需要将这些值存储在列表中，或者进行其他操作。