`

Java 遍历二叉树

    博客分类:
  • Java
阅读更多

Binary.java

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();

}

}

 

Node.java

public class Node {
private char key;
private Node left, right;

public Node(char key) {
   this(key, null, null);
}

public Node(char key, Node left, Node right) {
   this.key = key;
   this.left = left;
   this.right = right;
}

public char getKey() {
   return key;
}

public void setKey(char key) {
   this.key = key;
}

public Node getLeft() {
   return left;
}

public void setLeft(Node left) {
   this.left = left;
}

public Node getRight() {
   return right;
}

public void setRight(Node right) {
   this.right = right;
}
}

分享到:
评论

相关推荐

    递归方式遍历二叉树

    java实现创建二叉树,并且遍历二叉树(此处使用递归方式遍历); 创建二叉树的方式有很多,此处使用线性的链表转化成二叉树,链表节点的顺序就是前序遍历的顺序,链表中的null值,代表二叉树左节点或者右节点为null...

    Java实现二叉树的遍历

    java实现二叉树非递归前序中序后序遍历

    采用欧拉路径遍历二叉树java

    该算法采用欧拉路径遍历二叉树,使用java语言实现的

    java 二叉树遍历

    Java 二叉树遍历 二叉树是一种重要的数据结构,在计算机科学中有广泛的应用。在 Java 语言中,二叉树的遍历是指从根结点开始,按照一定的顺序访问二叉树中的每个结点。下面将详细介绍 Java 二叉树遍历的知识点。 ...

    Java输出中序遍历二叉树代码

    附件是Java输出中序遍历二叉树代码,中序遍历的顺序是:首先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。 reeNode 类定义了二叉树的节点,BinaryTree 类包含一个 root 属性和 ...

    Java二叉树中序遍历

    本课程设计将详细介绍如何使用Java编程语言实现二叉树的中序遍历。 首先,我们先构建二叉树的节点类(Node),它包含一个数据字段(data)以及指向左子节点(left)和右子节点(right)的引用: ```java public ...

    Java输出后序遍历二叉树的代码

    附件是Java输出后序遍历二叉树的代码,后序遍历的顺序是:首先递归地后序遍历左子树,然后递归地后序遍历右子树,最后访问根节点。 TreeNode 类定义了二叉树的节点,BinaryTree 类包含一个 root 属性和 ...

    Java输出中序遍历二叉树的代码

    附件是Java输出中序遍历二叉树的代码,中序遍历的顺序是:首先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。 TreeNode 类定义了二叉树的节点,BinaryTree 类包含一个 root 属性和 ...

    遍历二叉树(java实现)

    二叉树遍历是一种访问二叉树所有节点的方法,通常分为三种主要类型:先序遍历、中序遍历和后序遍历。在Java编程语言中,我们可以使用递归或迭代的方式来实现这些遍历方法。 **先序遍历**(根-左-右)是最常见的遍历...

    Java输出先序遍历二叉树的代码

    附件是Java输出先序遍历二叉树的代码,先序遍历的顺序是:首先访问根节点,然后递归地先序遍历左子树,最后递归地先序遍历右子树。 TreeNode 类定义了二叉树的节点,每个节点包含一个整数值 val 和指向左右子节点...

    Java实现二叉树的层次遍历

    * 层次遍历二叉树 */ public void levelOrderTraversal() { if (root == null) { System.out.println("树为空"); return; } Queue&lt;Node&gt; queue = new LinkedList(); queue.add(root); while (!queue....

    Java实现先序遍历二叉树

    在Java中,实现二叉树的先序遍历可以通过递归来完成。先序遍历的顺序是:首先访问根节点,然后递归地先序遍历左子树,最后递归地先序遍历右子树。 在这段代码中,Node类定义了二叉树的节点,包含数据域和指向左右子...

    遍历二叉树java代码

    在Java编程语言中,遍历二叉树是一种常见的操作,用于访问树结构中的所有节点。二叉树有三种主要的遍历方式:前序遍历、中序遍历和后序遍历。以下是对这些遍历方法的详细解释,以及可能在`Tree.java`、`TestTree....

    二叉树递归中序遍历java

    java编程,二叉树的中序遍历,递归实现

    栈遍历二叉树

    java实现创建二叉树,并且遍历二叉树(此处使用非递归方式遍历); 用出栈入栈的方式遍历二叉树。

    先序遍历二叉树的非递归算法程序

    编写先序遍历二叉树的非递归算法程序,要求: (1)以二叉链表建立二叉树。 (2)输出遍历的结点序列。 (3)有实例验算。

    java二叉树的前序+中序+后序遍历

    java实现 二叉树的遍历 前序遍历用到递归, 中序和后序遍历用到栈, 其实还是有一定难度的

Global site tag (gtag.js) - Google Analytics