java怎么拦截某个对象
253
2023-01-25
java栈实现二叉树的非递归遍历的示例代码
一般来说遍历二叉树用到递归,但是用Stack进行遍历也是一个不错的方法。
二叉树设置
class Node{
public int val;
public Node left;
public Node right;
public Node(int v) {
val=v;
left=null;
right=null;
}
}
public class Main {
public static void main(String[] args) {
Node head =new Node(0);
Node node1=new Node(1);
Node node2=new Node(2);
Node node3=new Node(3);
Node node4=new Node(4);
Node node5=new Node(5);
Node node6=new Node(6);
head.left=node1;
head.right=node2;
node1.left=node3;
node1.right=node4;
node2.left=node5;
node2.right=node6;
pos2(head);
pos1(head);
in(head);
}
前序遍历
思想和流程
弹出就打印
如果有右子树,就压入
如果有左子树,就压入
public static void pos1(Node h) {
System.out.print("先序遍历 ");
if(h!=null) {
Stack
stack.push(h);
while(!stack.isEmpty()) {
h=stack.pop();
System.out.print(h.val+" ");
if(h.right!=null) {
stack.push(h.right);
}
if(h.left!=null) {
stack.push(h.left);
}
}
}
System.out.println();
}
后序遍历
前序遍历的顺序是父节点,左,右,而后序遍历的顺序是左,右,父节点,也就是说前序遍历左右替换之后就是后序遍历的倒过来。所以只要把前序遍历时候左右子节点压栈的顺序调换一下,再用另一个栈储存,然后再弹出就是后序遍历了。在此代码就不多写了。
中序遍历
思路和流程
弹出就打印
整条左边界依次入栈
上一条件无法继续,弹出打印,开始右子树
public static void in(Node h) {
System.out.print("中序遍历 ");
if(h!=null) {
Stack
while(!stack.isEmpty()||h!=null) {
if(h!=null) {
stack.push(h);
h=h.left;
}else {
h=stack.pop();
System.out.print(h.val+" ");
h=h.right;
}
}
}
System.out.println();
}
后序遍历变体
用一个Stack实现
思路是左节点没处理就处理左节点,左节点mUXnWJe处理过了就处理右节点,右节点处理完了就返回。
public static void pos2(Node h) {
if(h!=null) {
Stack
stack.push(h);
Node c=null;//用c记录上一次被打印的节点
while(!stack.isEmpty()) {
c=stack.peek();
if(c.left!=null&&h!=c.left&&h!=c.right) {
stack.push(c.left);
}else if(c.right!=null&http://amp;&h!=c.right) {
stack.push(c.right);
}else {
System.out.print(stack.pop().val+" ");
h=c;//记录本次被打印的节点
}
}
}
}
打印结果
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~