面试题36：二叉搜索树与双向链表（没有思路）

一、题目

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

二、关键

1.把树分成3部分来考察：根节点、左子树、右子树，然后把左子树中最大的节点、根节点、右子树中最小的节点链接起来。

2.递归策略。

三、解释

1.理论分析是否能够将二叉搜索树转换为双向链表？在二叉树中，每个节点都有两个指向子节点的指针。在双向链表中，每个节点有两个指针，分别指向前一个节点和后一个节点。由于这两种节点的结构相似，同时二叉搜索树也是一种排序的数据结构，因此，在理论上有可能实现二叉搜索树和排序双向链表的转换。

2.在搜索二叉树中，左子节点的值总是小于父节点的值，右子节点的值总是大于父节点的值。因此，我们将二叉搜索树准换成排序双向链表式，原先指向左节点的指针调整为链表中指向前一个节点的指针，原先指向右子节点的指针调整为链表中指向后一个节点的指针。

3.如何转换？中序遍历树中的每个节点。当遍历到根节点的时候，我们把树看成3个部分；根节点、左子树、右子树。在把左、右子树转换成排序双向链表之后再和根节点链接起来，整棵二叉搜索树也就转换成了排序双向链表。当我们中序遍历到根节点时，它的左子树已经准换成一个排序的链表了，并且处在链表中的最后一个节点是当前值最大的节点。当我们把左子树形成的双向链表和根节点串起来之后，此时链表中的最后一个节点就是根节点了。接着我们再去遍历转换右子树，并把根节点和右子树中最小的节点链接起来。

4.怎么转换根节点和左子树和右子树，和3中的思路相同，因此推荐函数使用递归解决。

四、代码

#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：二叉搜索树与双向链表（没有思路）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。