二叉树的非递归java
时间: 2023-11-14 13:05:20 浏览: 53
引用提到了树和二叉树是两种不同的数据结构,而二叉树的各种方法实现起来比较简单。对于非递归遍历二叉树的问题,我们可以使用栈来实现。以下是二叉树的非递归遍历的Java代码示例:
```java
public class TestBinaryTree {
// 前序遍历(非递归)
public void preOrderTraversalNor(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.empty()) {
while (cur != null) {
stack.push(cur);
System.out.println(cur.val + " ");
cur = cur.left;
}
TreeNode top = stack.pop();
cur = top.right;
}
}
// 中序遍历(非递归)
public void inOrderTraversalNor(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.empty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.pop();
System.out.print(top.val + " ");
cur = top.right;
}
System.out.println();
}
// 后序遍历(非递归)
public void postOrderTraversalNor(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode prev = null; // 用于记录上一次访问的结点
while (cur != null || !stack.empty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.peek();
if (top.right == null || top.right == prev) {
System.out.print(top.val + " "); stack.pop();
prev = top;
} else {
cur = top.right;
}
}
System.out.println();
}
}
```
以上代码示例中的`TreeNode`类表示二叉树的结点,包含了结点的值以及左右子结点的引用。`preOrderTraversalNor`方法实现了二叉树的前序遍历,`inOrderTraversalNor`方法实现了二叉树的中序遍历,`postOrderTraversalNor`方法实现了二叉树的后序遍历。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)