二叉树遍历的总结(JAVA版)
程序员文章站
2022-05-19 19:54:05
...
二叉树节点
public class BinaryTreeNode {
private int data;
private BinaryTreeNode left;
private BinaryTreeNode right;
public BinaryTreeNode() {}
public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right) {
super();
this.data = data;
this.left = left;
this.right = right;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public BinaryTreeNode getLeft() {
return left;
}
public void setLeft(BinaryTreeNode left) {
this.left = left;
}
public BinaryTreeNode getRight() {
return right;
}
public void setRight(BinaryTreeNode right) {
this.right = right;
}
}
二叉树遍历:前序、中序、后序(递归和非递归)、层序。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BinaryTree {
//前序遍历递归的方式
public void preOrder(BinaryTreeNode root){
if(null!=root){
System.out.print(root.getData()+"\t");
preOrder(root.getLeft());
preOrder(root.getRight());
}
}
//前序遍历非递归的方式
public void preOrderNonRecursive(BinaryTreeNode root){
Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
while(true){
while(root!=null){
System.out.print(root.getData()+"\t");
stack.push(root);
root=root.getLeft();
}
if(stack.isEmpty()) break;
root=stack.pop();
root=root.getRight();
}
}
//中序遍历采用递归的方式
public void inOrder(BinaryTreeNode root){
if(null!=root){
inOrder(root.getLeft());
System.out.print(root.getData()+"\t");
inOrder(root.getRight());
}
}
//中序遍历采用非递归的方式
public void inOrderNonRecursive(BinaryTreeNode root){
Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
while(true){
while(root!=null){
stack.push(root);
root=root.getLeft();
}
if(stack.isEmpty())break;
root=stack.pop();
System.out.print(root.getData()+"\t");
root=root.getRight();
}
}
//后序遍历采用递归的方式
public void postOrder(BinaryTreeNode root){
if(root!=null){
postOrder(root.getLeft());
postOrder(root.getRight());
System.out.print(root.getData()+"\t");
}
}
//后序遍历采用非递归的方式
public void postOrderNonRecursive(BinaryTreeNode root){
Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
while(true){
if(root!=null){
stack.push(root);
root=root.getLeft();
}else{
if(stack.isEmpty()) return;
if(null==stack.lastElement().getRight()){
root=stack.pop();
System.out.print(root.getData()+"\t");
while(root==stack.lastElement().getRight()){
System.out.print(stack.lastElement().getData()+"\t");
root=stack.pop();
if(stack.isEmpty()){
break;
}
}
}
if(!stack.isEmpty())
root=stack.lastElement().getRight();
else
root=null;
}
}
}
//层序遍历
public void levelOrder(BinaryTreeNode root) {
BinaryTreeNode temp;
Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
temp = queue.poll();
System.out.print(temp.getData() + "\t");
if (null != temp.getLeft())
queue.offer(temp.getLeft());
if (null != temp.getRight()) {
queue.offer(temp.getRight());
}
}
}
public static void main(String[] args) {
BinaryTreeNode node10=new BinaryTreeNode(10,null,null);
BinaryTreeNode node8=new BinaryTreeNode(8,null,null);
BinaryTreeNode node9=new BinaryTreeNode(9,null,node10);
BinaryTreeNode node4=new BinaryTreeNode(4,null,null);
BinaryTreeNode node5=new BinaryTreeNode(5,node8,node9);
BinaryTreeNode node6=new BinaryTreeNode(6,null,null);
BinaryTreeNode node7=new BinaryTreeNode(7,null,null);
BinaryTreeNode node2=new BinaryTreeNode(2,node4,node5);
BinaryTreeNode node3=new BinaryTreeNode(3,node6,node7);
BinaryTreeNode node1=new BinaryTreeNode(1,node2,node3);
BinaryTree tree=new BinaryTree();
//采用递归的方式进行遍历
System.out.println("-----前序遍历------");
tree.preOrder(node1);
System.out.println();
//采用非递归的方式遍历
tree.preOrderNonRecursive(node1);
System.out.println();
//采用递归的方式进行遍历
System.out.println("-----中序遍历------");
tree.inOrder(node1);
System.out.println();
//采用非递归的方式遍历
tree.inOrderNonRecursive(node1);
System.out.println();
//采用递归的方式进行遍历
System.out.println("-----后序遍历------");
tree.postOrder(node1);
System.out.println();
//采用非递归的方式遍历
tree.postOrderNonRecursive(node1);
System.out.println();
//采用递归的方式进行遍历
System.out.println("-----层序遍历------");
tree.levelOrder(node1);
System.out.println();
}
}
下一篇: 深度优先遍历(邻接矩阵)
推荐阅读
-
java学习有用吗有意义吗(总结学习Java的好处)
-
Java读取Properties文件的七种方法的总结
-
干货分享:ASP.NET CORE(C#)与Spring Boot MVC(JAVA)异曲同工的编程方式总结
-
PHP数组遍历的几种常见方式总结
-
1086 Tree Traversals Again (25 分)(二叉树的遍历)
-
Python利用前序和中序遍历结果重建二叉树的方法
-
java中的Io(input与output)操作总结(一)
-
java中的Io(input与output)操作总结(三)
-
java中的Io(input与output)操作总结(二)
-
Java HashMap 如何正确遍历并删除元素的方法小结