【面试题027】二叉搜索树与双向链表

【面试题027】二叉搜索树与双向链表

题目：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调用书中结点的指向。

二叉树的结点定义如下：

 C++ Code 

1
2
3
4
5
6

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

ConvertBinarySearchTree.cpp:

 C++ Code 

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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197

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

using namespace std;

void ConvertNode(BinaryTreeNode *pNode, BinaryTreeNode **pLastNodeInList);

BinaryTreeNode *Convert(BinaryTreeNode *pRootOfTree)
{
    BinaryTreeNode *pLastNodeInList = NULL;
    ConvertNode(pRootOfTree, &pLastNodeInList);

    // pLastNodeInList指向双向链表的尾结点，
    // 我们需要返回头结点
    BinaryTreeNode *pHeadOfList = pLastNodeInList;
    while(pHeadOfList != NULL && pHeadOfList->m_pLeft != NULL)
        pHeadOfList = pHeadOfList->m_pLeft;

    return pHeadOfList;
}

void ConvertNode(BinaryTreeNode *pNode, BinaryTreeNode **pLastNodeInList)
{
    if(pNode == NULL)
        return;

    BinaryTreeNode *pCurrent = pNode;

    if (pCurrent->m_pLeft != NULL)
        ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

    pCurrent->m_pLeft = *pLastNodeInList;
    if(*pLastNodeInList != NULL)
        (*pLastNodeInList)->m_pRight = pCurrent;

    *pLastNodeInList = pCurrent;

    if (pCurrent->m_pRight != NULL)
        ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}

// ====================测试代码====================
void PrintDoubleLinkedList(BinaryTreeNode *pHeadOfList)
{
    BinaryTreeNode *pNode = pHeadOfList;

    printf("The nodes from left to right are: ");
    while(pNode != NULL)
    {
        printf("%d ", pNode->m_nValue);

        if(pNode->m_pRight == NULL)
            break;
        pNode = pNode->m_pRight;
    }

    printf(" The nodes from right to left are: ");
    while(pNode != NULL)
    {
        printf("%d ", pNode->m_nValue);

        if(pNode->m_pLeft == NULL)
            break;
        pNode = pNode->m_pLeft;
    }

    printf(" ");
}

void DestroyList(BinaryTreeNode *pHeadOfList)
{
    BinaryTreeNode *pNode = pHeadOfList;
    while(pNode != NULL)
    {
        BinaryTreeNode *pNext = pNode->m_pRight;

        delete pNode;
        pNode = pNext;
    }
}

void Test(char *testName, BinaryTreeNode *pRootOfTree)
{
    if(testName != NULL)
        printf("%s begins: ", testName);

    PrintTree(pRootOfTree);

    BinaryTreeNode *pHeadOfList = Convert(pRootOfTree);

    PrintDoubleLinkedList(pHeadOfList);
}

//            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);

    DestroyList(pNode4);
}

//               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);

    DestroyList(pNode1);
}

// 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);

    DestroyList(pNode1);
}

// 树中只有1个结点
void Test4()
{
    BinaryTreeNode *pNode1 = CreateBinaryTreeNode(1);
    Test("Test4", pNode1);

    DestroyList(pNode1);
}

// 树中没有结点
void Test5()
{
    Test("Test5", NULL);
}

int main()
{
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    return 0;
}

BinaryTree.h:

 C++ Code 

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

#ifndef _Binary_Tree_
#define _Binary_Tree_

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_*/

BinaryTree.cpp:

 C++ Code 

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

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

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);
    }
}

运算结果：

 C++ Code 

Test1 begins:
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 left to right are:
4       6       8       10      12      14      16
The nodes from right to left are:
16      14      12      10      8       6       4
Test2 begins:
value of this node is: 5
value of its left child is: 4.
right child is null.

value of this node is: 4
value of its left child is: 3.
right child is null.

value of this node is: 3
value of its left child is: 2.
right child is null.

value of this node is: 2
value of its left child is: 1.
right child is null.

value of this node is: 1
left child is null.
right child is null.

The nodes from left to right are:
1       2       3       4       5
The nodes from right to left are:
5       4       3       2       1
Test3 begins:
value of this node is: 1
left child is null.
value of its right child is: 2.

value of this node is: 2
left child is null.
value of its right child is: 3.

value of this node is: 3
left child is null.
value of its right child is: 4.

value of this node is: 4
left child is null.
value of its right child is: 5.

value of this node is: 5
left child is null.
right child is null.

The nodes from left to right are:
1       2       3       4       5
The nodes from right to left are:
5       4       3       2       1
Test4 begins:
value of this node is: 1
left child is null.
right child is null.

The nodes from left to right are:
1
The nodes from right to left are:
1
Test5 begins:
this node is null.

The nodes from left to right are:

The nodes from right to left are:

请按任意键继续. . .