【面试题018】树的子结构

【面试题018】树的子结构

输入两个二叉树A,B，判断B是不是A的子结构，

SubTree.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
83

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

using namespace std;

bool HasSubtreeCore(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2);
bool DoesTree1HaveTree2(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2);

bool HasSubtree(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2)
{
    bool result = false;

    if(pRoot1 != NULL && pRoot2 != NULL)
    {
        if(pRoot1->m_nValue == pRoot2->m_nValue)
            result = DoesTree1HaveTree2(pRoot1, pRoot2);
        if(!result)
            result = HasSubtree(pRoot1->m_pLeft, pRoot2);
        if(!result)
            result = HasSubtree(pRoot1->m_pRight, pRoot2);
    }

    return result;
}

bool DoesTree1HaveTree2(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2)
{
    if(pRoot2 == NULL)
        return true;

    if(pRoot1 == NULL)
        return false;

    if(pRoot1->m_nValue != pRoot2->m_nValue)
        return false;

    return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) &&
           DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
}

// 树中结点含有分叉，树B是树A的子结构
//                  8                8
//              /                  /
//             8         7         9   2
//           /
//          9     2
//               /
//              4   7
int main()
{
    BinaryTreeNode *pNodeA1 = CreateBinaryTreeNode(8);
    BinaryTreeNode *pNodeA2 = CreateBinaryTreeNode(8);
    BinaryTreeNode *pNodeA3 = CreateBinaryTreeNode(7);
    BinaryTreeNode *pNodeA4 = CreateBinaryTreeNode(9);
    BinaryTreeNode *pNodeA5 = CreateBinaryTreeNode(2);
    BinaryTreeNode *pNodeA6 = CreateBinaryTreeNode(4);
    BinaryTreeNode *pNodeA7 = CreateBinaryTreeNode(7);

    ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3);
    ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5);
    ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7);

    BinaryTreeNode *pNodeB1 = CreateBinaryTreeNode(8);
    BinaryTreeNode *pNodeB2 = CreateBinaryTreeNode(9);
    BinaryTreeNode *pNodeB3 = CreateBinaryTreeNode(2);

    ConnectTreeNodes(pNodeB1, pNodeB2, pNodeB3);

    BinaryTreeNode *pRoot1 = pNodeA1;
    BinaryTreeNode *pRoot2 = pNodeB1;

    if(HasSubtree(pRoot1, pRoot2) == true)
        printf("passed. ");
    else
        printf("failed. ");

    DestroyTree(pNodeA1);
    DestroyTree(pNodeB1);
    return 0;
}

运行结果：

passed.

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:

#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
13

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