树常用的遍历方式哪四种

树是一种数据结构，具有根节点、子节点、叶节点等概念，常用于存储具有层次结构的数据。在树结构中，遍历是其中最基础、最重要的操作之一。遍历是指按照一定的规则访问树中的所有节点，遍历方式有很多种，本文将讨论树常用的遍历方式，包括前序遍历、中序遍历、后序遍历和层次遍历。

一、前序遍历

前序遍历也称为先序遍历，是指从根节点开始访问，先访问根节点，然后递归访问其左子树，最后递归访问其右子树。前序遍历的实现可以采用迭代和递归两种方式。

递归实现前序遍历的代码如下：

```java

public void preorder(TNode root) {

if (root == null) {

return;

}

System.out.print(root.data + " ");

preorder(root.left);

preorder(root.right);

}

```

迭代实现前序遍历的代码如下：

```java

public void preorder(TNode root) {

Stack stack = new Stack<>();

stack.push(root);

while (!stack.isEmpty()) {

TNode node = stack.pop();

if (node != null) {

System.out.print(node.data + " ");

stack.push(node.right);

stack.push(node.left);

}

}

}

```

二、中序遍历

中序遍历是指从根节点开始访问，先递归访问其左子树，然后访问根节点，最后递归访问其右子树。中序遍历的实现也可以采用迭代和递归两种方式。

递归实现中序遍历的代码如下：

```java

public void inorder(TNode root) {

if (root == null) {

return;

}

inorder(root.left);

System.out.print(root.data + " ");

inorder(root.right);

}

```

迭代实现中序遍历的代码如下：

```java

public void inorder(TNode root) {

Stack stack = new Stack<>();

TNode node = root;

while (node != null || !stack.isEmpty()) {

while (node != null) {

stack.push(node);

node = node.left;

}

node = stack.pop();

System.out.print(node.data + " ");

node = node.right;

}

}

```

三、后序遍历

后序遍历是指从根节点开始访问，先递归访问其左子树，然后递归访问其右子树，最后访问根节点。后序遍历的实现也可以采用迭代和递归两种方式。

递归实现后序遍历的代码如下：

```java

public void postorder(TNode root) {

if (root == null) {

return;

}

postorder(root.left);

postorder(root.right);

System.out.print(root.data + " ");

}

```

迭代实现后序遍历的代码如下：

```java

public void postorder(TNode root) {

Stack stack1 = new Stack<>();

Stack stack2 = new Stack<>();

stack1.push(root);

while (!stack1.isEmpty()) {

TNode node = stack1.pop();

if (node != null) {

stack2.push(node);

stack1.push(node.left);

stack1.push(node.right);

}

}

while (!stack2.isEmpty()) {

System.out.print(stack2.pop().data + " ");

}

}

```

四、层次遍历

层次遍历是指按照从上到下、从左到右的顺序遍历树中的所有节点。层次遍历的实现可以采用队列的方式。

层次遍历的代码如下：

```java

public void levelorder(TNode root) {

if (root == null) {

return;

}

Queue queue = new LinkedList<>();

queue.offer(root);

while (!queue.isEmpty()) {

TNode node = queue.poll();

System.out.print(node.data + " ");

if (node.left != null) {

queue.offer(node.left);

}

if (node.right != null) {

queue.offer(node.right);

}

}

}

```

综上所述，树常用的遍历方式有前序遍历、中序遍历、后序遍历和层次遍历。其中，前序遍历从根节点开始访问，中序遍历先访问左子树，后访问右子树，后序遍历先访问左子树和右子树，最后访问根节点，层次遍历则按层次从上到下、从左到右遍历。对于树结构的操作，我们需要根据实际需要选择不同的遍历方式。