【面试题023】从上往下打印二叉树

【面试题023】从上往下打印二叉树

层次遍历二叉树就是队列的应用

树是图的一种特殊退化形式，从上到下按层次遍历二叉树，从本质上来说就是广度优先遍历二叉树。

PrintTree.cpp:

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

#include <iostream>
#include <cstdio>
#include <deque>
#include "BinaryTree.h"

using namespace std;

void PrintFromTopToBottom(BinaryTreeNode *pTreeRoot)
{
    if(!pTreeRoot)
    {
        return;
    }
    deque<BinaryTreeNode *> dequeTreeNode;

    dequeTreeNode.push_back(pTreeRoot);
    while(dequeTreeNode.size())
    {
        BinaryTreeNode *pNode = dequeTreeNode.front();
        dequeTreeNode.pop_front();

        printf("%d ", pNode->m_nValue);

        if(pNode->m_pLeft)
        {
            dequeTreeNode.push_back(pNode->m_pLeft);
        }
        if(pNode->m_pRight)
        {
            dequeTreeNode.push_back(pNode->m_pRight);
        }
    }
}

//            10
//         /
//        6        14
//       /        /
//      4  8     12  16
int main()
{
    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);

    BinaryTreeNode *pRoot = pNode10;
    PrintTree(pRoot);

    printf("The nodes from top to bottom, from left to right are: ");
    PrintFromTopToBottom(pRoot);
    cout << endl;
    DestroyTree(pNode10);

    return 0;
}

BinaryTree.h:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#ifndef _BINARY_TREE_H_
#define _BINARY_TREE_H_

struct BinaryTreeNode
{
    int                    m_nValue;
    BinaryTreeNode        *m_pLeft;
    BinaryTreeNode        *m_pRight;
};

BinaryTreeNode *CreateBinaryTreeNode(int value);
void ConnectTreeNodes(
    BinaryTreeNode *pParent,
    BinaryTreeNode *pLeft, BinaryTreeNode *pRight);
void PrintTreeNode(BinaryTreeNode *pNode);
void PrintTree(BinaryTreeNode *pRoot);
void DestroyTree(BinaryTreeNode *pRoot);

#endif /*_BINARY_TREE_H_*/

BinaryTree.cpp:

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

#include <iostream>
#include <cstdio>
#include "BinaryTree.h"

using namespace std;
BinaryTreeNode *CreateBinaryTreeNode(int value)
{
    BinaryTreeNode *pNode = new BinaryTreeNode();
    pNode->m_nValue = value;
    pNode->m_pLeft = NULL;
    pNode->m_pRight = NULL;

    return pNode;
}

void ConnectTreeNodes(
    BinaryTreeNode *pParent,
    BinaryTreeNode *pLeft,
    BinaryTreeNode *pRight)
{
    if(pParent != NULL)
    {
        pParent->m_pLeft = pLeft;
        pParent->m_pRight = pRight;
    }
}

void PrintTreeNode(BinaryTreeNode *pNode)
{
    if(pNode != NULL)
    {
        printf("value of this node is: %d ", pNode->m_nValue);

        if(pNode->m_pLeft != NULL)
            printf("value of its left child is: %d. ",
                   pNode->m_pLeft->m_nValue);
        else
            printf("left child is null. ");

        if(pNode->m_pRight != NULL)
            printf("value of its right child is: %d. ",
                   pNode->m_pRight->m_nValue);
        else
            printf("right child is null. ");
    }
    else
    {
        printf("this node is null. ");
    }

    printf(" ");
}

void PrintTree(BinaryTreeNode *pRoot)
{
    PrintTreeNode(pRoot);

    if(pRoot != NULL)
    {
        if(pRoot->m_pLeft != NULL)
            PrintTree(pRoot->m_pLeft);

        if(pRoot->m_pRight != NULL)
            PrintTree(pRoot->m_pRight);
    }
}

void DestroyTree(BinaryTreeNode *pRoot)
{
    if(pRoot != NULL)
    {
        BinaryTreeNode *pLeft = pRoot->m_pLeft;
        BinaryTreeNode *pRight = pRoot->m_pRight;

        delete pRoot;
        pRoot = NULL;

        DestroyTree(pLeft);
        DestroyTree(pRight);
    }
}

Makefile:

1
2
3
4
5
6
7
8
9
10
11
12

.PHONY:clean
CPP=g++
CFLAGS=-Wall -g
BIN=test
OBJS=PrintTree.o BinaryTree.o
LIBS=
$(BIN):$(OBJS)
    $(CPP) $(CFLAGS) $^ -o $@ $(LIBS)
%.o:%.cpp
    $(CPP) $(CFLAGS) -c $< -o $@
clean:
    rm -f *.o $(BIN)

运行结果:

value of this node is: 10

value of its left child is: 6.

value of its right child is: 14.

value of this node is: 6

value of its left child is: 4.

value of its right child is: 8.

value of this node is: 4

left child is null.

right child is null.

value of this node is: 8

left child is null.

right child is null.

value of this node is: 14

value of its left child is: 12.

value of its right child is: 16.

value of this node is: 12

left child is null.

right child is null.

value of this node is: 16

left child is null.

right child is null.

The nodes from top to bottom, from left to right are:

10 6 14 4 8 12 16