P137、面试题23:从上往下打印二叉树

题目:从上往下打印出二叉树的每个结点,同一层的结点按照从左到右的顺序打印。例如输入如图的二叉树,则依次打印出8,6,10,5,7,9,11.(其实是按层遍历)
二叉树结点的定义如下:
struct BinaryTreeNode{
       int     m_nValue;
       BinaryTreeNode*     m_pLeft;
       BinaryTreeNode*     m_pRight;
}

代码实现:

package com.yyq;

import java.util.LinkedList;
import java.util.Queue; /**
* Created by Administrator on 2015/9/16.
*/
public class PrintFromTopToBottom {
public static void printFromTopToBottom(BinaryTreeNode pTreeRoot){
if (pTreeRoot == null)
return;
Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
queue.offer(pTreeRoot);
while (queue.size() > 0){
BinaryTreeNode pNode = queue.poll();
System.out.print(pNode.getM_nValue() + "\t");
if (pNode.getM_pLeft() != null){
queue.offer(pNode.getM_pLeft());
}
if (pNode.getM_pRight() != null){
queue.offer(pNode.getM_pRight());
}
}
}
// ====================测试代码====================
public static void Test(String testName, BinaryTreeNode pRoot){
if (testName != null)
System.out.println(testName + " Begin:");
printFromTopToBottom(pRoot);
System.out.println();
}
// 测试完全二叉树:除了叶子节点,其他节点都有两个子节点
// 8
// 6 10
// 5 7 9 11
public static void Test1() {
System.out.println("\n=====Test1 starts:=====");
BinaryTreeNode pNode8 = new BinaryTreeNode(8);
BinaryTreeNode pNode6 = new BinaryTreeNode(6);
BinaryTreeNode pNode10 = new BinaryTreeNode(10);
BinaryTreeNode pNode5 = new BinaryTreeNode(5);
BinaryTreeNode pNode7 = new BinaryTreeNode(7);
BinaryTreeNode pNode9 = new BinaryTreeNode(9);
BinaryTreeNode pNode11 = new BinaryTreeNode(11); pNode8.connectTreeNodes(pNode6, pNode10);
pNode6.connectTreeNodes(pNode5, pNode7);
pNode10.connectTreeNodes(pNode9, pNode11); Test("Test1",pNode8);
pNode8 = null;
} // 测试二叉树:出叶子结点之外,左右的结点都有且只有一个左子结点
// 8
// 7
// 6
// 5
//
public static void Test2() {
System.out.println("\n=====Test2 starts:=====");
BinaryTreeNode pNode8 = new BinaryTreeNode(8);
BinaryTreeNode pNode7 = new BinaryTreeNode(7);
BinaryTreeNode pNode6 = new BinaryTreeNode(6);
BinaryTreeNode pNode5 = new BinaryTreeNode(5);
BinaryTreeNode pNode4 = new BinaryTreeNode(4); pNode8.connectTreeNodes(pNode7, null);
pNode7.connectTreeNodes(pNode6, null);
pNode6.connectTreeNodes(pNode5, null);
pNode5.connectTreeNodes(pNode4, null); Test("Test2",pNode8);
pNode8 = null;
} // 测试二叉树:出叶子结点之外,左右的结点都有且只有一个右子结点
// 8
// 7
// 6
// 5
// 4
public static void Test3() {
System.out.println("\n=====Test3 starts:=====");
BinaryTreeNode pNode8 = new BinaryTreeNode(8);
BinaryTreeNode pNode7 = new BinaryTreeNode(7);
BinaryTreeNode pNode6 = new BinaryTreeNode(6);
BinaryTreeNode pNode5 = new BinaryTreeNode(5);
BinaryTreeNode pNode4 = new BinaryTreeNode(4); pNode8.connectTreeNodes(null, pNode7);
pNode7.connectTreeNodes(null, pNode6);
pNode6.connectTreeNodes(null, pNode5);
pNode5.connectTreeNodes(null, pNode4); Test("Test3",pNode8);
pNode8 = null;
} // 测试空二叉树:根结点为空指针
public static void Test4() {
System.out.println("\n=====Test4 starts:=====");
BinaryTreeNode pNode = null; Test("Test4",pNode);
} // 测试只有一个结点的二叉树
public static void Test5() {
System.out.println("=====Test5 starts:=====");
BinaryTreeNode pNode8 = new BinaryTreeNode(8); Test("Test5",pNode8);
pNode8 = null;
} public static void main(String[] args) {
Test1();
Test2();
Test3();
Test4();
Test5();
}
}
 
结果输出:
=====Test1 starts:=====
Test1 Begin:
8 6 10 5 7 9 11
 
=====Test2 starts:=====
Test2 Begin:
8 7 6 5 4
 
=====Test3 starts:=====
Test3 Begin:
8 7 6 5 4
 
=====Test4 starts:=====
Test4 Begin:
 
=====Test5 starts:=====
Test5 Begin:
8
上一篇:HDU 1671 Phone List(POJ 3630)


下一篇:[转]读取assets目录下的数据库文件