二叉树非递归遍历

xiaoxiao2021-02-28  16

参考http://blog.csdn.net/sgbfblog/article/details/7773103 感谢

package com.yuzhiyun; import java.util.Stack; import javax.xml.soap.Node; import com.yuzhiyun.FindPathInBinaryTree.BinaryTreeNode; public class PreOrder { /** * 二叉树的树结点 */ public static class BinaryTreeNode { public BinaryTreeNode(int value, BinaryTreeNode left, BinaryTreeNode right) { this.value = value; this.left = left; this.right = right; } int value; BinaryTreeNode left; BinaryTreeNode right; } /** * 非递归先序遍历,回溯思想 * @param root */ public static void preOrderNotRecursion(BinaryTreeNode root){ Stack<BinaryTreeNode> stack=new Stack<>(); while (root!=null || !stack.empty()) { if(root!=null) { System.out.print(root.value+" "); stack.push(root); root=root.left; } else { root=stack.pop(); root=root.right; } } } /** * 非递归中序遍历 * 与非递归先序遍历 代码逻辑几乎一致 * @param root */ public static void midOrderNotRecursion(BinaryTreeNode root){ Stack<BinaryTreeNode> stack=new Stack<>(); while (root!=null || !stack.empty()) { if(root!=null) { stack.push(root); root=root.left; } else { root=stack.pop(); System.out.print(root.value+" "); root=root.right; } } } /** * 非递归后序遍历 * 用两个栈实现,我希望把最终结果存储在第二个栈stackResult中,然后stackResult 一直pop就可以打印出结果, * 后序是左、右、根,于是在对stackResult入栈的时候顺序就得是 根、右、左, * 由于我们是不断地把第一个栈stack的top节点 压入stackResult的, * 并且在while()循环外面已经把root push进去了,进入while循环之后,首先就把stack顶部push了,所以之后是先push左孩子,再push右孩子 * @param root */ public static void postOrderNotRecursion(BinaryTreeNode root){ if(null==root) return; Stack<BinaryTreeNode> stack=new Stack<>(); Stack<BinaryTreeNode> stackResult=new Stack<>(); stack.push(root); while (!stack.empty()) { BinaryTreeNode node=stack.pop(); stackResult.push(node); if(node.left!=null) stack.push(node.left); if(node.right!=null) stack.push(node.right); } while (!stackResult.isEmpty()) { System.out.print(stackResult.pop().value+" "); } } public static void main(String[] args) { /** * 二叉树结构 * 10 * | | * 5 12 * | | | * 3 4 6 */ BinaryTreeNode left=new BinaryTreeNode(5, new BinaryTreeNode(3, null, null), new BinaryTreeNode(4, null, null)); BinaryTreeNode right=new BinaryTreeNode(12, new BinaryTreeNode(6, null, null), null); BinaryTreeNode root=new BinaryTreeNode(10,left,right); System.out.print("非递归先序: "); preOrderNotRecursion(root); System.out.println(); System.out.print("非递归中序: "); midOrderNotRecursion(root); System.out.println(); System.out.print("非递归后序: "); postOrderNotRecursion(root); } }
转载请注明原文地址: https://www.6miu.com/read-1250152.html

最新回复(0)