数据结构 - 把二元查找树转变成排序的双向链表（C++）-蒲公英云

数据结构 - 把二元查找树转变成排序的双向链表（C++）

迷南。 2022-04-22 05:06 156阅读 0赞

分享一下我老师大神的人工智能教程！零基础，通俗易懂！http://blog.csdn.net/jiangjunshow

也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！

//****************************************************************************************************////  把二元查找树转变成排序的双向链表 - C++ - by Chimomo//// 【思路】: 按照二叉树的中序遍历正好按从小到大地顺序遍历全部节点。在遍历的过程中，更改它的逻辑结构。////****************************************************************************************************#include <iostream>using namespace std;// The binary search tree node.struct BSTreeNode{
      int m_nValue; // The value of node. BSTreeNode *m_pLeft; // The left child of node. BSTreeNode *m_pRight; // The right child of node.};typedef BSTreeNode DoubleLinkedList;DoubleLinkedList *pHead = NULL;DoubleLinkedList *pDoubleLinkedList = NULL;// Construct binary search tree recursively.void ConstructBSTree(BSTreeNode *& pCurrent, int value) // Use & here since pCurrent will be changed in the function body.{ if(pCurrent == NULL) {  BSTreeNode * pTree = new BSTreeNode();  pTree->m_pLeft = NULL;  pTree->m_pRight = NULL;  pTree->m_nValue = value;  pCurrent = pTree; } else {  if(value > pCurrent->m_nValue)  {   ConstructBSTree(pCurrent->m_pRight,value);  }  else if(value < pCurrent->m_nValue)  {   ConstructBSTree(pCurrent->m_pLeft,value);  }  else  {   cout<<"Invalid input, there already have the value!"<<endl;  } }}// Convert binary search tree node to double linked list node.void ConvertBSTreeNodeToDoubleLinkedListNode(BSTreeNode * pCurrent){ pCurrent->m_pLeft = pDoubleLinkedList; if (pDoubleLinkedList == NULL) {  pHead = pCurrent; } else {  pDoubleLinkedList->m_pRight = pCurrent; } pDoubleLinkedList = pCurrent;}// Traverse binary search tree (inorder) to convert binary tree to double linked list.void TraverseBSTreeInorder(BSTreeNode * pCurrent){ if(pCurrent == NULL) {  return; } else {  if(pCurrent->m_pLeft != NULL)  {   TraverseBSTreeInorder(pCurrent->m_pLeft);  }  ConvertBSTreeNodeToDoubleLinkedListNode(pCurrent);  if(pCurrent->m_pRight != NULL)  {   TraverseBSTreeInorder(pCurrent->m_pRight);  } }}int main(int argc, char* argv[]){ int value; BSTreeNode *pBSTree = NULL; cout << "Please input integers, -1 to end: "; cin >> value; while(-1 != value) {  ConstructBSTree(pBSTree, value);  cin >> value; } TraverseBSTreeInorder(pBSTree); while(pHead) {  cout << pHead->m_nValue << endl;  pHead = pHead->m_pRight; } return 0;}// Output:/*Please input integers, -1 to end: 6 7 8 5 4 3 9 2 1 0 10 -1012345678910*/