树常用的遍历方式哪四种
树是一种数据结构，具有根节点、子节点、叶节点等概念，常用于存储具有层次结构的数据。在树结构中，遍历是其中最基础、最重要的操作之一。遍历是指按照一定的规则访问树中的所有节点，遍历方式有很多种，本文将讨论树常用的遍历方式，包括前序遍历、中序遍历、后序遍历和层次遍历。
一、前序遍历
前序遍历也称为先序遍历，是指从根节点开始访问，先访问根节点，然后递归访问其左子树，最后递归访问其右子树。前序遍历的实现可以采用迭代和递归两种方式。
递归实现前序遍历的代码如下：
```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.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
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
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.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);
}
}
}
```
综上所述，树常用的遍历方式有前序遍历、中序遍历、后序遍历和层次遍历。其中，前序遍历从根节点开始访问，中序遍历先访问左子树，后访问右子树，后序遍历先访问左子树和右子树，最后访问根节点，层次遍历则按层次从上到下、从左到右遍历。对于树结构的操作，我们需要根据实际需要选择不同的遍历方式。
