注意：在非递归遍历中，利用了栈的先进后出特性，维持了父子节点的关系
import java.util.Stack;
public class BinaryTree {
protected Node root;
public BinaryTree(Node root) {
this.root = root;
}
public Node getRoot() {
return root;
}
/** 构造树 */
public static Node init() {
Node a = new Node('A');
Node b = new Node('B', null, a);
Node c = new Node('C');
Node d = new Node('D', b, c);
Node e = new Node('E');
Node f = new Node('F', e, null);
Node g = new Node('G', null, f);
Node h = new Node('H', d, g);
return h;// root
}
/** 访问节点 */
public static void visit(Node p) {
System.out.print(p.getKey() + " ");
}
/** 递归实现前序遍历 */
protected static void preorder(Node p) {
if (p != null) {
visit(p);
preorder(p.getLeft());
preorder(p.getRight());
}
}
/** 递归实现中序遍历 */
protected static void inorder(Node p) {
if (p != null) {
inorder(p.getLeft());
visit(p);
inorder(p.getRight());
}
}
/** 递归实现后序遍历 */
protected static void postorder(Node p) {
if (p != null) {
postorder(p.getLeft());
postorder(p.getRight());
visit(p);
}
}
/** 非递归实现前序遍历 */
protected static void iterativePreorder(Node p) {
Stack<Node> stack = new Stack<Node>();
if (p != null) {
stack.push(p);
while (!stack.empty()) {
p = stack.pop();
visit(p);
if (p.getRight() != null)
stack.push(p.getRight());
if (p.getLeft() != null)
stack.push(p.getLeft());
}
}
}
/** 非递归实现前序遍历2 */
protected static void iterativePreorder2(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p;
while (node != null || stack.size() > 0) {
while (node != null) {//压入所有的左节点，压入前访问它
visit(node);
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {//
node = stack.pop();
node = node.getRight();
}
}
}
/** 非递归实现后序遍历 */
protected static void iterativePostorder(Node p) {
Node q = p;
Stack<Node> stack = new Stack<Node>();
while (p != null) {
// 左子树入栈
for (; p.getLeft() != null; p = p.getLeft())
stack.push(p);
// 当前节点无右子或右子已经输出
while (p != null && (p.getRight() == null || p.getRight() == q)) {
visit(p);
q = p;// 记录上一个已输出节点
if (stack.empty())
return;
p = stack.pop();
}
// 处理右子
stack.push(p);
p = p.getRight();
}
}
/** 非递归实现后序遍历 双栈法 */
protected static void iterativePostorder2(Node p) {
Stack<Node> lstack = new Stack<Node>();
Stack<Node> rstack = new Stack<Node>();
Node node = p, right;
do {
while (node != null) {
right = node.getRight();
lstack.push(node);
rstack.push(right);
node = node.getLeft();
}
node = lstack.pop();
right = rstack.pop();
if (right == null) {
visit(node);
} else {
lstack.push(node);
rstack.push(null);
}
node = right;
} while (lstack.size() > 0 || rstack.size() > 0);
}
/** 非递归实现后序遍历 单栈法*/
protected static void iterativePostorder3(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p, prev = p;
while (node != null || stack.size() > 0) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {
Node temp = stack.peek().getRight();
if (temp == null || temp == prev) {
node = stack.pop();
visit(node);
prev = node;
node = null;
} else {
node = temp;
}
}
}
}
/** 非递归实现后序遍历4 双栈法*/
protected static void iterativePostorder4(Node p) {
Stack<Node> stack = new Stack<Node>();
Stack<Node> temp = new Stack<Node>();
Node node = p;
while (node != null || stack.size() > 0) {
while (node != null) {
temp.push(node);
stack.push(node);
node = node.getRight();
}
if (stack.size() > 0) {
node = stack.pop();
node = node.getLeft();
}
}
while (temp.size() > 0) {
node = temp.pop();
visit(node);
}
}
/** 非递归实现中序遍历 */
protected static void iterativeInorder(Node p) {
Stack<Node> stack = new Stack<Node>();
while (p != null) {
while (p != null) {
if (p.getRight() != null)
stack.push(p.getRight());// 当前节点右子入栈
stack.push(p);// 当前节点入栈
p = p.getLeft();
}
p = stack.pop();
while (!stack.empty() && p.getRight() == null) {
visit(p);
p = stack.pop();
}
visit(p);
if (!stack.empty())
p = stack.pop();
else
p = null;
}
}
/** 非递归实现中序遍历2 */
protected static void iterativeInorder2(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p;
while (node != null || stack.size() > 0) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {
node = stack.pop();
visit(node);
node = node.getRight();
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
BinaryTree tree = new BinaryTree(init());
System.out.print(" Pre-Order:");
preorder(tree.getRoot());
System.out.println();
System.out.print(" In-Order:");
inorder(tree.getRoot());
System.out.println();
System.out.print("Post-Order:");
postorder(tree.getRoot());
System.out.println();
System.out.print(" Pre-Order:");
iterativePreorder(tree.getRoot());
System.out.println();
System.out.print("Pre-Order2:");
iterativePreorder2(tree.getRoot());
System.out.println();
System.out.print(" In-Order:");
iterativeInorder(tree.getRoot());
System.out.println();
System.out.print(" In-Order2:");
iterativeInorder2(tree.getRoot());
System.out.println();
System.out.print(" Post-Order:");
iterativePostorder(tree.getRoot());
System.out.println();
System.out.print("Post-Order2:");
iterativePostorder2(tree.getRoot());
System.out.println();
System.out.print("Post-Order3:");
iterativePostorder3(tree.getRoot());
System.out.println();
System.out.print("Post-Order4:");
iterativePostorder4(tree.getRoot());
System.out.println();
}
}
先序
// 先序遍历 mark
public static void preOrder(Node root) {
Stack<Node> stack = new Stack<Node>();
Node currentNode = root;
while (stack.size() > 0 || currentNode != null) {
if (currentNode == null) {
currentNode = stack.pop();
}
System.out.print(currentNode.getData());
if (currentNode.getRight() != null) {
stack.push(currentNode.getRight());
}
currentNode = currentNode.getLeft();
}
}
相关推荐
在提供的"二叉树的递归和非递归遍历"压缩包文件中，可能包含了Java源代码，演示了如何实现这两种遍历方式。通过阅读和理解这些代码，你可以更好地掌握二叉树遍历的原理和实践，这对于理解和解决涉及二叉树的算法问题...
详细介绍了JAVA中二叉树的非递归遍历方式，三种方式都是采用栈来辅助完成，其中前序遍历采用的是先入右子节点再入左子节点的方法，这样弹出栈时左在前，右在后。中序遍历的话则是要先一直到达最左的子节点，然后才弹...
java实现二叉树非递归前序中序后序遍历
如果你用C或者C++或者其他高级语言写过二叉树或者阅读过相关方面代码，应该知道二叉树的非递归遍历避不开通过栈或者队列实现。是的，python也一样。但是python自带的list功能很强大，即可以当stack
非递归中序遍历是一种在不使用递归方法的情况下遍历二叉树的策略，主要依赖于数据结构栈来实现。在这个Java代码示例中，我们看到的是如何使用栈来执行非递归中序遍历的过程。首先，让我们详细了解二叉树和中序遍历的...
非递归遍历通常使用栈来辅助实现，具体分为以下几种方式： 1. **非递归前序遍历**： - 使用一个栈来保存待访问的节点。 - 如果当前节点不为空，则将其入栈，并将当前节点设置为其左孩子。 - 当栈不为空时，从栈...
本文将详细介绍二叉树的深度优先搜索和广度优先搜索的非递归方法实现。 深度优先搜索的非递归方法实现： 深度优先搜索是一种遍历二叉树的方式，它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点 v 的...
代码中`recursePreOrder()`函数实现了递归的前序遍历，而`stackPreOrder()`则使用了栈来辅助非递归前序遍历。在非递归方法中，首先访问根节点，然后将左子树压入栈中，接着处理左子树的左子节点，直到没有左子节点...
二叉树的非递归遍历运算 建立二叉树的三叉链式存储结构，在此基础上完成下列算法： 1） 从键盘上输入二叉树的各个结点，建立三叉链表 2） 输出该二叉树 3） 非递归的层次遍历算法 4） 非递归的先序遍历、中序遍历、...
java语言实现的二叉树的各种操作(包括递归与非递归遍历二叉树,求二叉树的高度，节点总数，叶子节点等)
编写先序遍历二叉树的非递归算法程序，要求： （1）以二叉链表建立二叉树。 （2）输出遍历的结点序列。 （3）有实例验算。
下面将详细介绍这些遍历方法及其递归和非递归实现。 1. **前序遍历**： - **描述**：前序遍历的顺序是“根-左-右”。首先访问根节点，然后递归地访问左子树，最后访问右子树。 - **递归实现**： ```java void ...
在`MyBinaryTree2.java`和`MyBinaryTree.java`这两个文件中，可能分别实现了递归和非递归的遍历方法。你可以打开这些文件，查看代码并理解其中的逻辑，以加深对二叉树遍历的理解。此外，实践是最好的老师，你可以...
创建二叉树可以通过递归或非递归方式实现。递归方式通常更直观，例如，我们可以创建一个`createTree`方法接收数据和子节点作为参数来构建二叉树。 3. **遍历方法**： - **前序遍历**：先访问根节点，然后遍历左...
在本话题中，我们将重点讨论链式二叉树的中序遍历，包括递归和非递归的方法，以及如何创建和销毁这种数据结构。 一、链式二叉树的中序创建 中序创建链式二叉树通常涉及自底向上的构建过程。首先，我们需要创建一个...
"Java二叉树的遍历" Java二叉树的遍历是指对二叉树的节点进行访问和处理的过程。二叉树的遍历可以分为递归遍历和非递归遍历两种方式，分别对应递归函数...非递归遍历的优点是可以避免栈溢出，但代码实现起来较为复杂。
这里我们将重点讨论如何在已知二叉树的前序和中序遍历的情况下，通过非递归算法实现后序遍历。 **前序遍历**：根节点 -> 左子树 -> 右子树 **中序遍历**：左子树 -> 根节点 -> 右子树 **后序遍历**：左子树 -> 右子...
在提供的压缩包文件“二叉树遍历（非递归）”中，可能包含具体的代码示例，这些示例可能涵盖了上述理论的实现，帮助你更好地理解和应用非递归遍历二叉树的方法。通过阅读和分析这些代码，你可以加深对二叉树遍历的...
本文档介绍了一段Java代码，该代码实现了二叉树的基本操作，包括节点的插入和三种遍历方法（中序、前序和后序）。通过这些操作，我们可以有效地管理和操作二叉树结构，为更复杂的算法和数据处理提供基础。理解这些...
在“BitTree”这个文件中，很可能包含了实现这些功能的Java代码，包括树节点类、可视化类以及非递归遍历的算法。通过对这些代码的学习和实践，你可以深入理解二叉树的操作，并提升在实际项目中的应用能力。记住，...