首页 > 代码库 > 16.输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印
16.输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印
转载请注明出处：http://www.cnblogs.com/wuzetiandaren/p/4261605.html
声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，本文的思想也许有所借鉴，但源码均为本人实现，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。
题目：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
题目分析：可以用一个LinkedList的数据结构模拟队列来完成此操作。传入树的根节点root。
1.如果root为空则结束交换，否则root 入队。
2.当队列不为空时进行如下操作：
a.队首元素出队，交换队首元素节点的左右孩子。
b.如果队首元素的左孩子不为空，左孩子节点入队；如果队首元素的右孩子不为空，右孩子节点进栈。
算法实现：
1 //层序遍历,使用LinkedList数据结构来模拟队列 2 private void levelOrder(Node root){ 3 if(root==null){ 4 System.out.println("\n二叉树为空！"); 5 return; 6 } 7 System.out.println("\n这是二叉排序树的层序遍历结果:"); 8 LinkedList<Node> queue = new LinkedList<Node>(); 9 queue.add(root); //根节点先入队10 while(queue.size()!=0){11 Node node = queue.removeFirst(); //得到并删除队列的第一个节点12 System.out.print(node.data+" ");13 if(node.left!=null){ //该节点的左孩子入队14 queue.add(node.left);15 }16 if(node.right!=null){ //该节点的右孩子入队17 queue.add(node.right);18 }19 }20 System.out.println();21 }
java实现完整源码：
1 package com.interview; 2 3 import java.util.LinkedList; 4 5 /** 6 * 题目:输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。 7 * @author wjh 8 * 9 */10 public class _16LeverOrder {11 12 /**13 * @param args14 */15 public static void main(String[] args) {16 _16LeverOrder builder= new _16LeverOrder();17 int[] a = {20,5,22,4,7,25,13,36,42,11,24};18 Node root = null;19 root = builder.buildTree(root, a); //1)创建二叉排序树20 builder.levelOrder(root);21 }22 23 //层序遍历,使用LinkedList数据结构来模拟队列24 private void levelOrder(Node root){25 if(root==null){26 System.out.println("\n二叉树为空！");27 return;28 }29 System.out.println("\n这是二叉排序树的层序遍历结果:");30 LinkedList<Node> queue = new LinkedList<Node>();31 queue.add(root); //根节点先入队32 while(queue.size()!=0){33 Node node = queue.removeFirst(); //得到并删除队列的第一个节点34 System.out.print(node.data+" ");35 if(node.left!=null){ //该节点的左孩子入队36 queue.add(node.left);37 }38 if(node.right!=null){ //该节点的右孩子入队39 queue.add(node.right);40 }41 }42 System.out.println();43 }44 45 46 //建二叉排序树47 private Node buildTree(Node root, int[] data) {48 int n = data.length;49 System.out.println("建树过程(a<--b表示在a左边插入b;a-->b表示在a右边插入b):");50 for (int i = 0; i < n; i++) {51 root=insert(root, data[i]);52 }53 return root;54 }55 56 //一次插入节点57 private Node insert(Node node, int data) {58 if (node == null) {59 node = new Node(data,null,null);60 System.out.println(node.data);61 }else{ 62 if(data <= node.data) {63 System.out.print(node.data+"<--");//在root左边插入64 node.left = insert(node.left, data);65 } else {66 System.out.print(node.data+"-->"); //在root右边插入67 node.right = insert(node.right, data);68 }69 }70 return node;71 }72 73 //创建一个树节点类74 class Node {75 public int data;76 public Node left; //指向左孩子的指针 77 public Node right; //指向右孩子的指针 78 public Node() {79 super();80 }81 public Node(int data, Node left, Node right) {82 super();83 this.data =http://www.mamicode.com/ data;84 this.left = left;85 this.right = right;86 }87 }88 }
运行结果：
建树过程(a<--b表示在a左边插入b;a-->b表示在a右边插入b):
20
20<--5
20-->22
20<--5<--4
20<--5-->7
20-->22-->25
20<--5-->7-->13
20-->22-->25-->36
20-->22-->25-->36-->42
20<--5-->7-->13<--11
20-->22-->25<--24
这是二叉排序树的层序遍历结果:
20 5 22 4 7 25 13 24 36 11 42
16.输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。