题目：从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。例如输入图 4.5 中的二叉树，则依次打印出 8、6、10、5、7、9、11。二叉树结点的定义如下：typedef struct Node{   int m_nValue;   Node *m_pLeft;   Node *m_pRight;}BTreeNode, *pBTreeNode;

 该题目相当于二叉树的层次遍历，需要队列为我们的辅助容器，用作保存结点。

因为按层打印的顺序决定了先打印根结点。所以先从树的根结点开始分析。

1、为了能够打印值为 8 的结点的两个子结点，我们应该在遍历到该结点时把值为 6 和 10 的两个结点保存到一个容器（队列）中。

2、按照从左往右的顺序，我们先取出值为 6 的结点，打印出值 6 之后，把它的左右孩子结点 5 和 7 放入数据容器中。

3、以此类推，直到把容器中的结点打印完。

具体过程的代码为：

1 // print nodes from top to buttom, from left to right 2 void PrintFromTopToButtom(BinaryTreeNode *pRoot) 3 { 4     if(pRoot == NULL) 5     { 6         printf("This tree is NULL\n"); 7         return; 8     }   9 10     std::queue
     
       queueTreeNode;11     queueTreeNode.push(pRoot);12 13     while(!queueTreeNode.empty())14     {15         BinaryTreeNode *node = queueTreeNode.front();16         printf("%d ", node->m_nValue);17         queueTreeNode.pop();18 19         if(node->m_pLeft)20             queueTreeNode.push(node->m_pLeft);21 22         if(node->m_pRight)23             queueTreeNode.push(node->m_pRight);24     }25 }
     

 

完整代码如下：

1 // PrintFromTopToButtom.cpp  2 #include "stdio.h"  3 #include 
      
         4   5 using namespace std;  6   7 typedef struct Node  8 {  9    int m_nValue; 10    struct Node *m_pLeft; 11    struct Node *m_pRight; 12 }BinaryTreeNode; 13  14 BinaryTreeNode *CreateBinaryTreeNode(int val); 15 void ConnectTreeNodes(BinaryTreeNode *pRoot, BinaryTreeNode *pLeftNode, BinaryTreeNode *pRightNode); 16 void PreOrderBinaryTree(BinaryTreeNode *pRoot); 17 void DestroyTree(BinaryTreeNode *pRoot); 18 void PrintFromTopToButtom(BinaryTreeNode *pRoot); 19  20  21 BinaryTreeNode *CreateBinaryTreeNode(int val) 22 { 23     BinaryTreeNode *pNewNode = new BinaryTreeNode; 24     pNewNode->m_nValue = val; 25     pNewNode->m_pLeft = NULL; 26     pNewNode->m_pRight = NULL; 27  28     return pNewNode; 29 } 30  31 void ConnectTreeNodes(BinaryTreeNode *pRoot, BinaryTreeNode *pLeftNode, BinaryTreeNode *pRightNode) 32 { 33     pRoot->m_pLeft = pLeftNode; 34     pRoot->m_pRight = pRightNode; 35 } 36  37 void PreOrderBinaryTree(BinaryTreeNode *pRoot) 38 { 39     if(pRoot) 40     { 41         printf("%d ", pRoot->m_nValue); 42         if(pRoot->m_pLeft) 43             PreOrderBinaryTree(pRoot->m_pLeft); 44  45         if(pRoot->m_pRight) 46             PreOrderBinaryTree(pRoot->m_pRight); 47     } 48 } 49  50 void DestroyTree(BinaryTreeNode *pRoot) 51 { 52     if(pRoot) 53     { 54         if(pRoot->m_pLeft) 55             DestroyTree(pRoot->m_pLeft); 56         if(pRoot->m_pRight) 57             DestroyTree(pRoot->m_pRight); 58  59         delete pRoot; 60         pRoot = NULL; 61     } 62 } 63  64 // print nodes from top to buttom, from left to right 65 void PrintFromTopToButtom(BinaryTreeNode *pRoot) 66 { 67     if(pRoot == NULL) 68     { 69         printf("This tree is NULL\n"); 70         return; 71     } 72         73  74     std::queue
       
         queueTreeNode; 75     queueTreeNode.push(pRoot); 76  77     while(!queueTreeNode.empty()) 78     { 79         BinaryTreeNode *node = queueTreeNode.front(); 80         printf("%d ", node->m_nValue); 81         queueTreeNode.pop(); 82  83         if(node->m_pLeft) 84             queueTreeNode.push(node->m_pLeft); 85  86         if(node->m_pRight) 87             queueTreeNode.push(node->m_pRight); 88     } 89 } 90  91 // ====================测试代码==================== 92 void Test(char *testName, BinaryTreeNode *pRoot) 93 { 94     if(testName) 95         printf("%s begins: \n", testName); 96  97     printf("PreOrderBinaryTree: "); 98     PreOrderBinaryTree(pRoot); 99     printf("\n");100 101     printf("The nodes from top to buttom, from left to right are:\n");102     PrintFromTopToButtom(pRoot);103     printf("\n");104 }105 106 //       8107 //    /     \108 //   6      10109 //  / \    /   \110 // 5   7  9    11111 void test1()112 {113     BinaryTreeNode *pNode8 = CreateBinaryTreeNode(8);114     BinaryTreeNode *pNode6 = CreateBinaryTreeNode(6);115     BinaryTreeNode *pNode10 = CreateBinaryTreeNode(10);116     BinaryTreeNode *pNode5 = CreateBinaryTreeNode(5);117     BinaryTreeNode *pNode7 = CreateBinaryTreeNode(7);118     BinaryTreeNode *pNode9 = CreateBinaryTreeNode(9);119     BinaryTreeNode *pNode11= CreateBinaryTreeNode(11);120 121     ConnectTreeNodes(pNode8, pNode6, pNode10);122     ConnectTreeNodes(pNode6, pNode5, pNode7);123     ConnectTreeNodes(pNode10, pNode9, pNode11);124 125     char str1[] = "test1";126     Test(str1, pNode8);127     DestroyTree(pNode8);    128 }129 130 131 //          5132 //         /133 //        4134 //       /135 //      3136 //     /137 //    2138 void test2()139 {140     BinaryTreeNode *pNode5 = CreateBinaryTreeNode(5);141     BinaryTreeNode *pNode4 = CreateBinaryTreeNode(4);142     BinaryTreeNode *pNode3 = CreateBinaryTreeNode(3);143     BinaryTreeNode *pNode2 = CreateBinaryTreeNode(2);144 145     ConnectTreeNodes(pNode5, pNode4, NULL);146     ConnectTreeNodes(pNode4, pNode3, NULL);147     ConnectTreeNodes(pNode3, pNode2, NULL);148 149     char str2[] = "test2";150     Test(str2, pNode5);151     DestroyTree(pNode5);    152 }153 154 155 //      1156 //       \157 //        2     158 //         \159 //          3160 //           \161 //            4162 void test3()163 {164     BinaryTreeNode *pNode1 = CreateBinaryTreeNode(1);165     BinaryTreeNode *pNode2 = CreateBinaryTreeNode(2);166     BinaryTreeNode *pNode3 = CreateBinaryTreeNode(3);167     BinaryTreeNode *pNode4 = CreateBinaryTreeNode(4);168 169     ConnectTreeNodes(pNode1, NULL, pNode2);170     ConnectTreeNodes(pNode2, NULL, pNode3);171     ConnectTreeNodes(pNode3, NULL, pNode4);172 173     char str3[] = "test3";174     Test(str3, pNode1);175     DestroyTree(pNode1);    176 }177 178 // NULL179 void test4()180 {181     char str4[] = "test4";182     Test(str4, NULL);183 }184 185 int main(int argc, char const *argv[])186 {187     test1();188     test2();189     test3();190     test4();191 192     return 0;193 }
       
      

 

本文完。