本文主要是介绍【九度】题目1523:从上往下打印二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目地址:http://ac.jobdu.com/problem.php?pid=1523
题目描述:
从上往下打印出二叉树的每个节点,同层节点从左至右打印。
输入:
输入可能包含多个测试样例,输入以EOF结束。
对于每个测试案例,输入的第一行一个整数n(1<=n<=1000, :n代表将要输入的二叉树元素的个数(节点从1开始编号)。接下来一行有n个数字,代表第i个二叉树节点的元素的值。接下来有n行,每行有一个字母Ci。
Ci=’d’表示第i个节点有两子孩子,紧接着是左孩子编号和右孩子编号。
Ci=’l’表示第i个节点有一个左孩子,紧接着是左孩子的编号。
Ci=’r’表示第i个节点有一个右孩子,紧接着是右孩子的编号。
Ci=’z’表示第i个节点没有子孩子。
输出:
对应每个测试案例,
按照从上之下,从左至右打印出二叉树节点的值。
样例输入:
7
8 6 5 7 10 9 11
d 2 5
d 3 4
z
z
d 6 7
z
z
样例输出:
8 6 10 5 7 9 11
二叉树建树和BFS
Java AC
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.LinkedList;
import java.util.Queue;public class Main {/** 1523*/public static void main(String[] args) throws Exception {StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));while (st.nextToken() != StreamTokenizer.TT_EOF) {int n = (int) st.nval;BinaSortTree[] biTrees = new BinaSortTree[n+1];for (int i = 1; i < n+1; i++) {st.nextToken();biTrees[i] = new BinaSortTree((int)st.nval);}for (int i = 1; i < n+1; i++) {st.nextToken();String operate = st.sval;if (operate.equals("d")) {st.nextToken();biTrees[i].lchild = biTrees[(int) st.nval];st.nextToken();biTrees[i].rchild = biTrees[(int) st.nval];}else if (operate.equals("l")) {st.nextToken();biTrees[i].lchild = biTrees[(int) st.nval];}else if (operate.equals("r")) {st.nextToken();biTrees[i].rchild = biTrees[(int) st.nval];}}printByLevel(biTrees[1]);}} private static void printByLevel(BinaSortTree binaSortTree) {StringBuilder sb = new StringBuilder();Queue<BinaSortTree> queue = new LinkedList<BinaSortTree>(); queue.offer(binaSortTree); while(!queue.isEmpty()){ int size = queue.size(); for(int i = 0; i < size; i++){ BinaSortTree biTree = queue.peek(); queue.poll();sb.append(biTree.value + " ");if(biTree.lchild != null){ queue.offer(biTree.lchild); } if(biTree.rchild != null){ queue.offer(biTree.rchild); } } } System.out.println(sb.toString().trim());}private static class BinaSortTree {private BinaSortTree lchild;private BinaSortTree rchild;private int value ;public BinaSortTree(int value) {super();this.value = value;}}
}
/**************************************************************Problem: 1523User: wangzhenqingLanguage: JavaResult: AcceptedTime:350 msMemory:14792 kb
****************************************************************/
这篇关于【九度】题目1523:从上往下打印二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!