2023年6月22日发(作者：)

java非递归遍历二叉树

Java非递归遍历二叉树

二叉树是一种重要的数据结构，它广泛应用于各种领域。二叉树的遍历方式有三种，分别是前序遍历、中序遍历和后序遍历。在Java中，我们可以使用递归方式来实现二叉树的遍历，但递归实现有时会造成栈溢出等问题。因此，本篇文章将介绍如何使用非递归方式来遍历二叉树。

1. 前序遍历

前序遍历的顺序是：根节点->左子树->右子树。使用非递归方式前序遍历二叉树，需要借助栈的数据结构。具体步骤如下：

1. 将二叉树的根节点压入栈中。

2. 当栈非空时，循环执行以下操作：

a. 弹出栈顶元素并输出。

b. 将栈顶元素的右子树（如果有）压入栈中。

c. 将栈顶元素的左子树（如果有）压入栈中。

具体代码实现如下： ```

public void nonRecursivePreorderTraversal(TreeNode root) {

if (root == null) {

return;

}

Stack stack = new Stack<>();

(root);

while (!y()) {

TreeNode node = ();

( + " ");

if ( != null) {

();

}

if ( != null) {

();

}

}

}

```

2. 中序遍历

中序遍历的顺序是：左子树->根节点->右子树。同样地，使用非递归方式中序遍历二叉树需要借助栈结构。具体步骤如下：

1. 将二叉树的根节点压入栈中，并将当前节点指向左子树的最左边的节点。

2. 当栈非空时，循环执行以下操作：

a. 将当前节点入栈，并将当前节点指向它的左孩子。

b. 当节点没有左子树时，弹出栈顶元素并进行输出，并将当前节点指向栈顶元素的右孩子。

具体代码实现如下：

```

public void nonRecursiveInorderTraversal(TreeNode root) {

if (root == null) {

return;

}

Stack stack = new Stack<>();

TreeNode node = root;

while (node != null || !y()) {

if (node != null) {

(node);

node = ; } else {

node = ();

( + " ");

node = ;

}

}

}

```

3. 后序遍历

后序遍历的顺序是：左子树->右子树->根节点。使用非递归方式后序遍历二叉树时，需要借助栈结构以及一个指向上一次弹出节点的指针。具体步骤如下：

1. 将根节点压入栈中，将当前节点指向根节点。

2. 当栈非空时，循环执行以下操作：

a. 将栈顶元素弹出并压入辅助栈中。

b. 如果栈顶元素有左孩子，将左孩子压入栈中。

c. 如果栈顶元素有右孩子，将右孩子压入栈中。

3. 当栈为空时，依次弹出辅助栈中的元素并进行输出。

具体代码实现如下： ```

public void nonRecursivePostorderTraversal(TreeNode root) {

if (root == null) {

return;

}

Stack stack = new Stack<>();

Stack helperStack = new Stack<>();

(root);

while (!y()) {

TreeNode node = ();

(node);

if ( != null) {

();

}

if ( != null) {

();

}

}

while (!y()) {

(().val + " ");

}

} ```

总结

通过以上的示例代码，我们可以看到使用非递归方式遍历二叉树也是非常简单的。非递归方式相比递归方式，可以减少函数调用和系统栈的使用，从而减少内存的消耗。因此，在实际开发中，我们应该尽可能地采用非递归方式遍历二叉树。