本文共 4368 字，大约阅读时间需要 14 分钟。
在二叉树中,每个结点都有两个指向子结点的指针. 在双向链表中, 每个结点也有两个指针,它们分别指向前一个结点和后一个结点.由于这两种结构的相似性, 同时二叉搜索树也是一种排过序的数据结构, 因此在理论上有可能实现二叉搜索树和排序的双向链表之间的转换.
下面的文件BST_to_DL.cpp将BST转换为排序过的双向链表,请参加代码:
#include "binary_tree.h"void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList){ if(pNode == NULL) return; BinaryTreeNode* pCurrent = pNode; //首先处理左子树 if(pCurrent->pLeft) ConvertNode(pNode->pLeft, pLastNodeInList); //完成pCurrent与pLastNodeInList的拼接和更替 pCurrent->pLeft = *pLastNodeInList; if(*pLastNodeInList != NULL) (*pLastNodeInList)->pRight = pCurrent; *pLastNodeInList = pCurrent; //遍历到右子树 if(pCurrent->pRight) ConvertNode(pCurrent->pRight,pLastNodeInList);}BinaryTreeNode* Convert(BinaryTreeNode* pRoot){ BinaryTreeNode* pLastNodeInList = NULL; ConvertNode(pRoot, &pLastNodeInList); //pLastNodeInList指向双向链表的尾结点，我们逆序返回它的头结点 BinaryTreeNode* pHeadOfList = pLastNodeInList; while(pHeadOfList != NULL && pHeadOfList->pLeft != NULL) pHeadOfList = pHeadOfList->pLeft; return pHeadOfList;}//========================测试代码 =============================void PrintDoubleLinkedList(BinaryTreeNode* pHeadOfList){ BinaryTreeNode* pNode = pHeadOfList; printf("The nodes from left to right are:\n"); while(pNode != NULL){ printf("%d\t", pNode->value); if(pNode->pRight == NULL) break; pNode = pNode->pRight; } printf("\nThe nodes from right to left are:\n"); while(pNode != NULL){ printf("%d\t", pNode->value); if(pNode->pLeft == NULL) break; pNode = pNode->pLeft; } printf("\n");}void DestroyList(BinaryTreeNode* pHeadOfList){ BinaryTreeNode* pNode = pHeadOfList; while(pNode != NULL){ BinaryTreeNode* pNext = pNode->pRight; delete pNode; pNode = pNext; }}void Test(const char* testName, BinaryTreeNode* pRoot){ if(testName != NULL) printf("%s begins: \n", testName); PrintTree(pRoot); BinaryTreeNode* pHeadOfList = Convert(pRoot); PrintDoubleLinkedList(pHeadOfList);}// 10// / \// 6 14// /\ /\// 4 8 12 16void 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// /// 1void 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// \// 5void 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(int argc, char** argv){ Test1(); Test2(); Test3(); Test4(); Test5(); return 0;} 转载地址：http://lzcoi.baihongyu.com/