Java实现二叉树的前序、中序、后序以及层次遍历

迈不过友情╰ 2022-06-08 03:57 70阅读 0赞

**建立一颗二叉排序树，并输出它的前序、中序、后序以及层次遍历结**  
输入：

5
    6 9 1 5 8
    输出：
    6 1 5 9 8 //前序
    1 5 6 8 9 //中序
    5 1 8 9 6 //后序
    6 1 9 5 8 //层次

`//Main函数 public static void main(String[] args){ Scanner scanner = new Scanner(System.in); while(scanner.hasNextInt()){ int num = scanner.nextInt(); int[] array = new int[num]; for(int i = 0; i < num; i++){ array[i] = scanner.nextInt(); } TreeNode root = new TreeNode(array[0]); for(int i = 1; i < num; i++){ buildBST(root,array[i]); } DLR(root);//前序遍历 System.out.println(); LDR(root);//中序遍历 System.out.println(); LRD(root);//后序遍历 System.out.println(); levelOrder(root);//层次遍历 System.out.println(); } } //前序遍历非递归 public static void DLR(TreeNode node){ if(node!=null){ Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(node); while(!stack.isEmpty()){ node = stack.pop(); System.out.print(node.val+" "); if(node.right!=null)stack.push(node.right); if(node.left!=null)stack.push(node.left); } } } //中序遍历非递归 public static void LDR(TreeNode node){ Stack<TreeNode> stack = new Stack<TreeNode>(); while(node!=null || !stack.isEmpty()){ if(node!=null){ stack.push(node); node = node.left; }else{ node = stack.pop(); System.out.print(node.val+" "); node = node.right; } } } //后序遍历非递归 public static void LRD(TreeNode node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode pre = node; while(node!=null){ while(node.left!=null){ stack.push(node); node = node.left; } while(node!=null && (node.right==null || node.right==pre)){ System.out.print(node.val+" "); pre = node; if(stack.isEmpty()) return; node = stack.pop(); } stack.push(node); node = node.right; } } //层次遍历非递归 public static void levelOrder(TreeNode node){ Queue<TreeNode> queue = new LinkedBlockingQueue<TreeNode>(); queue.offer(node); while(!queue.isEmpty()){ node = queue.poll(); System.out.print(node.val+" "); if(node.left!=null)queue.add(node.left); if(node.right!=null)queue.add(node.right); } } //构建二叉排序树 public static void buildBST(TreeNode node,int val){ if(node.val == val) return ; if(val < node.val){ if(node.left==null) node.left = new TreeNode(val); else buildBST(node.left,val); }else{ if(node.right==null) node.right = new TreeNode(val); else buildBST(node.right,val); } }`

````//二叉树节点结构 class TreeNode{ int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val){ this.val = val; } }``` ````