在二叉树中,每个结点都有两个指向子结点的指针. 在双向链表中, 每个结点也有两个指针,它们分别指向前一个结点和后一个结点.由于这两种结构的相似性, 同时二叉搜索树也是一种排过序的数据结构, 因此在理论上有可能实现二叉搜索树和排序的双向链表之间的转换.

下面的文件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:
");while(pNode != NULL){printf("%d	", pNode->value);if(pNode->pRight == NULL)break;pNode = pNode->pRight;}printf("
The nodes from right to left are:
");while(pNode != NULL){printf("%d	", pNode->value);if(pNode->pLeft == NULL)break;pNode = pNode->pLeft;}printf("
");
}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: 
", testName);PrintTree(pRoot);BinaryTreeNode* pHeadOfList = Convert(pRoot);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(int argc, char** argv){Test1();Test2();Test3();Test4();Test5();return 0;
}