JZ-C-23

剑指offer第二十三题:从上往下打印二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
//============================================================================
// Name        : JZ-C-23.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description : 从上往下打印二叉树
//============================================================================
 
#include <iostream>
#include <stdio.h>
#include <deque>
#include "BinaryTree.h"
using namespace std;
/**
 *层次遍历二叉树,相当于广度优先遍历,都需要利用队列
 */
void PrintFromTopToBottom(BinaryTreeNode* pTreeRoot){
    if(pTreeRoot == NULL){
        return;
    }
    std::deque<BinaryTreeNode*> dequeTreeNode;//这是一个两端都可以进出的队列★
    dequeTreeNode.push_back(pTreeRoot);//从后进队列
    while(!dequeTreeNode.empty()){
        BinaryTreeNode* Node = dequeTreeNode.front();//从前出队列
        dequeTreeNode.pop_front();
        cout<<Node->m_nValue<<endl;//打印
        if(Node->m_pLeft){
            dequeTreeNode.push_back(Node->m_pLeft);
        }
        if(Node->m_pRight){
            dequeTreeNode.push_back(Node->m_pRight);
        }
    }
}
 
// ====================测试代码====================
void Test(char* testName, BinaryTreeNode* pRoot)
{
    if(testName != NULL)
        printf("%s begins: \n", testName);
 
    PrintTree(pRoot);
 
    printf("The nodes from top to bottom, from left to right are: \n");
    PrintFromTopToBottom(pRoot);
 
    printf("\n\n");
}
 
//            10
//         /      \
//        6        14
//       /\        /\
//      4  8     12  16
void Test1()
{
    BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
    BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
    BinaryTreeNode* pNode14 = CreateBinaryTreeNode(14);
    BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
    BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);
    BinaryTreeNode* pNode12 = CreateBinaryTreeNode(12);
    BinaryTreeNode* pNode16 = CreateBinaryTreeNode(16);
 
    ConnectTreeNodes(pNode10, pNode6, pNode14);
    ConnectTreeNodes(pNode6, pNode4, pNode8);
    ConnectTreeNodes(pNode14, pNode12, pNode16);
 
    Test("Test1", pNode10);
 
    DestroyTree(pNode10);
}
 
//               5
//              /
//             4
//            /
//           3
//          /
//         2
//        /
//       1
void Test2()
{
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
    BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
    BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
    BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
 
    ConnectTreeNodes(pNode5, pNode4, NULL);
    ConnectTreeNodes(pNode4, pNode3, NULL);
    ConnectTreeNodes(pNode3, pNode2, NULL);
    ConnectTreeNodes(pNode2, pNode1, NULL);
 
    Test("Test2", pNode5);
 
    DestroyTree(pNode5);
}
 
// 1
//  \
//   2
//    \
//     3
//      \
//       4
//        \
//         5
void Test3()
{
    BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
    BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
    BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
    BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
 
    ConnectTreeNodes(pNode1, NULL, pNode2);
    ConnectTreeNodes(pNode2, NULL, pNode3);
    ConnectTreeNodes(pNode3, NULL, pNode4);
    ConnectTreeNodes(pNode4, NULL, pNode5);
 
    Test("Test3", pNode1);
 
    DestroyTree(pNode1);
}
 
// 树中只有1个结点
void Test4()
{
    BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
    Test("Test4", pNode1);
 
    DestroyTree(pNode1);
}
 
// 树中没有结点
void Test5()
{
    Test("Test5", NULL);
}
 
int main(int argc, char** argv)
{
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
 
   return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注