Java实现二叉树先序、中序、后序遍历
一、二叉树数据结构
二叉树节点有:值(val)、左孩子(left)、右孩子(right)
class TreeNode{ //二叉树节点 int val; TreeNode left; TreeNode right; TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } }
二、递归实现先序、中序、后序遍历
-
先序遍历
List<Integer> preList = new ArrayList<Integer>(); public List<Integer> preOrder(TreeNode root) { //先序遍历 递归 if(root == null) { return null; } preList.add(root.val); preOrder(root.left); preOrder(root.right); return preList; }
-
中序遍历
List<Integer> inList = new ArrayList<Integer>(); public List<Integer> inOrder(TreeNode root){ //中序遍历 递归 if(root == null) return null; inOrder(root.left); inList.add(root.val); inOrder(root.right); return inList; }
-
后序遍历
List<Integer> postList = new ArrayList<Integer>(); public List<Integer> postOrder(TreeNode root){ //后序遍历 递归 if(root == null) return null; postOrder(root.left); postOrder(root.right); postList.add(root.val); return postList; }
三、迭代实现先序、中序、后序遍历
-
先序遍历
public List<Integer> preOrderStack(TreeNode root){ //先序遍历 迭代 List<Integer> list = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); //栈 TreeNode node = root; while((node != null) || !stack.empty()) { if(node != null) { //将左孩子压栈 list.add(node.val); //访问 stack.push(node); node = node.left; }else { node = stack.pop(); node = node.right; } } return list; }
-
中序遍历
public List<Integer> inOrderStack(TreeNode root){ //中序遍历 迭代 List<Integer> list = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); //栈 TreeNode node = root; while((node != null) || !stack.empty()) { if(node != null) { //将左孩子压栈 stack.push(node); node = node.left; }else { node = stack.pop(); //出栈并访问 list.add(node.val); node = node.right; } } return list; }
-
后序遍历
public List<Integer> postOrderStack(TreeNode root){ //后序遍历 迭代 List<Integer> list = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); //栈 Stack<TreeNode> output = new Stack<TreeNode>(); //构造一个中间栈,存储逆后序遍历的结果 TreeNode node = root; while((node != null) || !stack.empty()) { if(node != null) { //将左孩子压栈 output.push(node); //保存节点,相当于前序遍历,根-右-左 stack.push(node); node = node.right; }else { node = stack.pop(); node = node.left; } } while(output.size() > 0) { node = output.pop(); list.add(node.val); } return list; }
四、测试
public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.init(); List<Integer> postList = binaryTree.postOrderStack(root); //后序遍历 迭代 System.out.println(postList); //结果:[4, 5, 2, 6, 7, 3, 1] } /** * 1 * 2 3 * 4 5 6 7 */ public TreeNode init() { //测试数据 TreeNode node4 = new TreeNode(4, null, null); TreeNode node5 = new TreeNode(5, null, null); TreeNode node6 = new TreeNode(6, null, null); TreeNode node7 = new TreeNode(7, null, null); TreeNode node2 = new TreeNode(2, node4, node5); TreeNode node3 = new TreeNode(3, node6, node7); TreeNode node1 = new TreeNode(1, node2, node3); return node1; }
更多请阅读