Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】
程序员文章站
2023-12-14 15:56:34
本文实例讲述了java实现的二叉树常用操作。分享给大家供大家参考,具体如下:
import java.util.arraydeque;
import java....
本文实例讲述了java实现的二叉树常用操作。分享给大家供大家参考,具体如下:
import java.util.arraydeque; import java.util.queue; import java.util.stack; //二叉树的建树,前中后 递归非递归遍历 层序遍历 //node节点 class node { int element; node left; node right; public node() { } public node(int element) { this.element = element; } } // binarytree public class tree { // creat tree from array public static node creattree(int[] data, int i) { if (i >= data.length || data[i] == -1) return null; node temp = new node(data[i]); temp.left = creattree(data, i * 2 + 1); temp.right = creattree(data, i * 2 + 2); return temp; } // pre前序遍历递归 public static void pre(node temp) { if (temp == null) return; system.out.print(temp.element + " "); pre(temp.left); pre(temp.right); } // mid中序遍历递归 public static void mid(node temp) { if (temp == null) return; mid(temp.left); system.out.print(temp.element + " "); mid(temp.right); } // last后序遍历递归 public static void last(node temp) { if (temp == null) return; last(temp.left); last(temp.right); system.out.print(temp.element + " "); } // pre1前序遍历非递归 public static void pre1(node temp) { stack<node> stack = new stack<>(); while (temp != null || !stack.isempty()) { while (temp != null) { stack.push(temp); system.out.print(temp.element + " "); temp = temp.left; } if (!stack.isempty()) { temp = stack.pop().right; } } } // mid1中序遍历非递归 public static void mid1(node temp) { stack<node> stack = new stack<>(); while (temp != null || !stack.isempty()) { while (temp != null) { stack.push(temp); temp = temp.left; } if (!stack.isempty()) { temp = stack.pop(); system.out.print(temp.element + " "); temp = temp.right; } } } // last1后序遍历非递归 public static void last1(node temp) { stack<node> stack = new stack<>(); stack<node> stack2 = new stack<>(); while (temp != null || !stack.isempty()) { while (temp != null) { stack.push(temp); stack2.push(temp); temp = temp.right; } if (!stack.isempty()) { temp = stack.pop().left; } } while (!stack2.isempty()) system.out.print(stack2.pop().element + " "); } // ceng层序遍历 public static void ceng(node temp) { if (temp == null) return; queue<node> queue = new arraydeque<>(); queue.offer(temp); while (!queue.isempty()) { temp = queue.poll(); system.out.print(temp.element + " "); if (temp.left != null) queue.offer(temp.left); if (temp.right != null) queue.offer(temp.right); } } // demo public static void main(string[] args) { int[] array = { 1, 2, 3, 4, 5, 6, 7, -1, -1, 10, -1, -1, 13 }; node tree = creattree(array, 0); system.out.println("测试结果:"); pre(tree); system.out.println(); pre1(tree); system.out.println(); mid(tree); system.out.println(); mid1(tree); system.out.println(); last(tree); system.out.println(); last1(tree); system.out.println(); ceng(tree); } }
运行结果:
更多关于java算法相关内容感兴趣的读者可查看本站专题:《java数据结构与算法教程》、《java操作dom节点技巧总结》、《java文件与目录操作技巧汇总》和《java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。