27|27 二叉搜索树与双向链表
#include
#include "BinaryTree.h"BinaryTreeNode* Convert(BinaryTreeNode* pRootOftree)
{
BinaryTreeNode* pLastNodeOfList = NULL;
ConvertNode(pRootOftree, &pLastNodeOfList);
//pLastNodeOfList指向双向链表的尾结点
//我们需要返回头结点
BinaryTreeNode* pHeadOfList = pLastNodeOfList;
while(pLastNodeOfList != NULL && pLastNodeOfList->m_pLeft != NULL)
pHeadOfList = pHeadOfList->m_pLeft;
return pHeadOfList;
}void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeOfList)
{
if(pNode == NULL)
return;
BinaryTreeNode* pCurrent = pNode;
if(pCurrent->m_pLeft != NULL)
ConvertNode(pCurrent->m_pLeft, pLastNodeOfList);
//注意双向
pCurrent->m_pLeft = pCurrent;
if(*pLastNodeOfList != NULL)
(*pLastNodeOfList)->m_pRight = pCurrent;
*pLastNodeOfList = pCurrent;
if(pCurrent->m_pRight != NULL)
ConvertNode(pCurrent->m_pRight, pLastNodeOfList);
}// ====================测试代码====================
void PrintDoubleLinkedList(BinaryTreeNode* pHeadOfList)
{
BinaryTreeNode* pNode = pHeadOfList;
printf("The nodes from left to right are:\n");
while(pNode != NULL)
{
printf("%d\t", pNode->m_nValue);
if(pNode->m_pRight == NULL)
break;
pNode = pNode->m_pRight;
}printf("\nThe nodes from right to left are:\n");
while(pNode != NULL)
{
printf("%d\t", pNode->m_nValue);
if(pNode->m_pLeft == NULL)
break;
pNode = pNode->m_pLeft;
}printf("\n");
}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:===\n", testName);
PrintTree(pRootOfTree);
BinaryTreeNode* pHeadOfList = Convert(pRootOfTree);
PrintDoubleLinkedList(pHeadOfList);
}//10
///\
//614
///\/\
//481216
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(void)
{
Test1();
Test2();
Test3();
Test4();
Test5();
return 0;
}
结果
文章图片
未命名_meitu_0.jpg
推荐阅读
- 【译】20个更有效地使用谷歌搜索的技巧
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- java中如何实现重建二叉树
- 种树郭橐驼传（文言句式+古今异义+词类活用+通假字）
- 白杨树
- 08黑龙江迟淑荣弯柳树网络学院第五期学习赵宗瑞老师主讲的（传统文化与身心健康）教育体系心得体会
- ［原创］能见沂山一棵树，胜读十年无用书！
- 涵养字外功
- 2018.07.07《刺杀骑士团长》村上春树
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）