一、题目
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
二、关键
1.把树分成3部分来考察：根节点、左子树、右子树，然后把左子树中最大的节点、根节点、右子树中最小的节点链接起来。
2.递归策略。
三、解释
1.理论分析是否能够将二叉搜索树转换为双向链表？在二叉树中，每个节点都有两个指向子节点的指针。在双向链表中，每个节点有两个指针，分别指向前一个节点和后一个节点。由于这两种节点的结构相似，同时二叉搜索树也是一种排序的数据结构，因此，在理论上有可能实现二叉搜索树和排序双向链表的转换。
2.在搜索二叉树中，左子节点的值总是小于父节点的值，右子节点的值总是大于父节点的值。因此，我们将二叉搜索树准换成排序双向链表式，原先指向左节点的指针调整为链表中指向前一个节点的指针，原先指向右子节点的指针调整为链表中指向后一个节点的指针。
3.如何转换？中序遍历树中的每个节点。当遍历到根节点的时候，我们把树看成3个部分；根节点、左子树、右子树。在把左、右子树转换成排序双向链表之后再和根节点链接起来，整棵二叉搜索树也就转换成了排序双向链表。当我们中序遍历到根节点时，它的左子树已经准换成一个排序的链表了，并且处在链表中的最后一个节点是当前值最大的节点。当我们把左子树形成的双向链表和根节点串起来之后，此时链表中的最后一个节点就是根节点了。接着我们再去遍历转换右子树，并把根节点和右子树中最小的节点链接起来。
4.怎么转换根节点和左子树和右子树，和3中的思路相同，因此推荐函数使用递归解决。
四、代码
复制代码
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#include <cstdio> #include "..UtilitiesBinaryTree.h" void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList); BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree) { BinaryTreeNode *pLastNodeInList = nullptr; ConvertNode(pRootOfTree, &pLastNodeInList); // pLastNodeInList指向双向链表的尾结点， // 我们需要返回头结点 BinaryTreeNode *pHeadOfList = pLastNodeInList; while(pHeadOfList != nullptr && pHeadOfList->m_pLeft != nullptr) pHeadOfList = pHeadOfList->m_pLeft; return pHeadOfList; } void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList) { if(pNode == nullptr) return; BinaryTreeNode *pCurrent = pNode; //从根节点开始遍历 if (pCurrent->m_pLeft != nullptr) //遍历左子树 ConvertNode(pCurrent->m_pLeft, pLastNodeInList); // 下面4行将根节点和左子树串成一串，并将链表的最后一个节点更新为根。 pCurrent->m_pLeft = *pLastNodeInList; //找到当前根的前一个节点 //将左子树中值最大的那个节点的下一个指针和根节点串上。 if(*pLastNodeInList != nullptr) (*pLastNodeInList)->m_pRight = pCurrent; *pLastNodeInList = pCurrent; if (pCurrent->m_pRight != nullptr) ConvertNode(pCurrent->m_pRight, pLastNodeInList); } // ====================测试代码==================== void PrintDoubleLinkedList(BinaryTreeNode* pHeadOfList) { BinaryTreeNode* pNode = pHeadOfList; printf("The nodes from left to right are:n"); while(pNode != nullptr) { printf("%dt", pNode->m_nValue); if(pNode->m_pRight == nullptr) break; pNode = pNode->m_pRight; } printf("nThe nodes from right to left are:n"); while(pNode != nullptr) { printf("%dt", pNode->m_nValue); if(pNode->m_pLeft == nullptr) break; pNode = pNode->m_pLeft; } printf("n"); } void DestroyList(BinaryTreeNode* pHeadOfList) { BinaryTreeNode* pNode = pHeadOfList; while(pNode != nullptr) { BinaryTreeNode* pNext = pNode->m_pRight; delete pNode; pNode = pNext; } } void Test(char* testName, BinaryTreeNode* pRootOfTree) { if(testName != nullptr) printf("%s begins:n", 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, nullptr); ConnectTreeNodes(pNode4, pNode3, nullptr); ConnectTreeNodes(pNode3, pNode2, nullptr); ConnectTreeNodes(pNode2, pNode1, nullptr); 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, nullptr, pNode2); ConnectTreeNodes(pNode2, nullptr, pNode3); ConnectTreeNodes(pNode3, nullptr, pNode4); ConnectTreeNodes(pNode4, nullptr, pNode5); Test("Test3", pNode1); DestroyList(pNode1); } // 树中只有1个结点 void Test4() { BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1); Test("Test4", pNode1); DestroyList(pNode1); } // 树中没有结点 void Test5() { Test("Test5", nullptr); } int main(int argc, char* argv[]) { Test1(); Test2(); Test3(); Test4(); Test5(); return 0; }
最后
以上就是耍酷仙人掌最近收集整理的关于面试题36：二叉搜索树与双向链表（没有思路）的全部内容，更多相关面试题36内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![如何定义一个空的Map[]数组？](/uploads/reation/bcimg8.png)
发表评论 取消回复