实现二叉树的先序、 中序、 后序遍历, 包括递归方式和非递归方式
程序员文章站
2022-03-03 09:34:29
...
实现二叉树的先序、 中序、 后序遍历, 包括递归方式和非递归方式
package BinaryTree;
import java.util.Stack;
public class PreInPosTraverasl {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int data){ this.value=data; }
}
public static void preOrderRecur(Node root){
if (root == null){
return;
}
System.out.print(root.value+" ");
preOrderRecur(root.left);
preOrderRecur(root.right);
}
public static void inOrderRecur(Node root){
if (root == null){
return;
}
inOrderRecur(root.left);
System.out.print(root.value+" ");
inOrderRecur(root.right);
}
public static void posOrderRecur(Node root){
if (root == null){
return;
}
posOrderRecur(root.left);
posOrderRecur(root.right);
System.out.print(root.value+" ");
}
public static void preOrderUnRecur(Node root){
System.out.print("pre-order: ");
if (root != null){
Stack<Node> stack=new Stack<>();
stack.add(root);
Node temp=null;
while (!stack.isEmpty()){
temp=stack.pop();
System.out.print(temp.value+" ");
if (temp.right!=null){
stack.push(temp.right);
}
if (temp.left!=null){
stack.push(temp.left);
}
}
}
System.out.println();
}
public static void inOrderUnRecur(Node root){
System.out.print("in-order: ");
if (root != null){
Stack<Node> stack=new Stack<>();
Node cur=root;
while (!stack.isEmpty() || cur!= null){
if (cur!=null){
stack.push(cur);
cur=cur.left;
}else {
cur=stack.pop();
System.out.print(cur.value+" ");
cur=cur.right;
}
}
}
System.out.println();
}
public static void posOrderUnRecur(Node root){
System.out.print("pos-order: ");
if (root != null){
Stack<Node> stack=new Stack<>();
Stack<Node> stack1=new Stack<>();
stack.add(root);
Node cur=null;
while (!stack.isEmpty()){
cur=stack.pop();
stack1.push(cur);
if (cur.left!=null){
stack.push(cur.left);
}
if (cur.right!=null){
stack.push(cur.right);
}
}
while (!stack1.isEmpty()){
System.out.print(stack1.pop().value+" ");
}
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(5);
head.left = new Node(3);
head.right = new Node(8);
head.left.left = new Node(2);
head.left.right = new Node(4);
head.left.left.left = new Node(1);
head.right.left = new Node(7);
head.right.left.left = new Node(6);
head.right.right = new Node(10);
head.right.right.left = new Node(9);
head.right.right.right = new Node(11);
// recursive
System.out.println("==============recursive==============");
System.out.print("pre-order: ");
preOrderRecur(head);
System.out.println();
System.out.print("in-order: ");
inOrderRecur(head);
System.out.println();
System.out.print("pos-order: ");
posOrderRecur(head);
System.out.println();
// unrecursive
System.out.println("============unrecursive=============");
preOrderUnRecur(head);
inOrderUnRecur(head);
posOrderUnRecur(head);
}
}
上一篇: vue使用节流函数的踩坑实例指南
下一篇: java简介以及了解java(三十)
推荐阅读
-
Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
左神算法:分别用递归和非递归方式实现二叉树先序、中序和后序遍历(Java版)
-
二分搜索树 BST 前序\中序\后序(递归和非递归实现)和层序遍历
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
Java实现二叉树先序、中序、后序遍历(递归与非递归)及层次遍历
-
JAVA 实现二叉树建立和先序,中序和后序遍历(递归与非递归)
-
非递归实现二叉树先序、中序、后序遍历(栈实现)
-
java实现二叉树的前序、中序、后序、层次遍历,递归与非递归