树遍历的各种写法java

理解与实现编程中的树的遍历

在计算机科学中，树结构是一种重要的数据结构，常被用于组织和管理数据。树的遍历是对树中所有节点的一种有序访问方式，有三种主要的遍历方法：前序遍历、中序遍历和后序遍历。下面将详细介绍这三种遍历方法，并提供每种方法的示例代码。

前序遍历（Preorder Traversal）

在前序遍历中，首先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。

示例代码（Python）：

```python

class TreeNode:

def __init__(self, value):

self.val = value

self.left = None

self.right = None

def preorderTraversal(root):

if root is None:

return

print(root.val, end=' ')

preorderTraversal(root.left)

preorderTraversal(root.right)

示例树

1

/ \

2 3

/ \

4 5

构造示例树

root = TreeNode(1)

root.left = TreeNode(2)

root.right = TreeNode(3)

root.left.left = TreeNode(4)

root.left.right = TreeNode(5)

前序遍历示例树

print("前序遍历结果：")

preorderTraversal(root)

```

输出结果为：`1 2 4 5 3`

中序遍历（Inorder Traversal）

在中序遍历中，先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。

示例代码（Python）：

```python

def inorderTraversal(root):

if root is None:

return

inorderTraversal(root.left)

print(root.val, end=' ')

inorderTraversal(root.right)

中序遍历示例树

print("\n中序遍历结果：")

inorderTraversal(root)

```

输出结果为：`4 2 5 1 3`

后序遍历（Postorder Traversal）

在后序遍历中，先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。

示例代码（Python）：

```python

def postorderTraversal(root):

if root is None:

return

postorderTraversal(root.left)

postorderTraversal(root.right)

print(root.val, end=' ')

后序遍历示例树

print("\n后序遍历结果：")

postorderTraversal(root)

```

输出结果为：`4 5 2 3 1`

以上就是树的三种常见遍历方法的实现代码。无论是前序、中序还是后序遍历，都可以用递归或迭代的方式来实现。在实际应用中，树的遍历常用于搜索、排序、表达式求值等各种算法中。