1 /*  2 1.把二元查找树转变成排序的双向链表（树）  3 题目：  4 输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。  5 要求不能创建任何新的结点，只调整指针的指向。  6      10  7     /   8    6   14  9   / \  /  10   4 8 12 16 11 转换成双向链表 12 4=6=8=10=12=14=16。 13 首先我们定义的二元查找树  节点的数据结构如下： 14 struct BSTreeNode 15 { 16 int m_nValue; // value of node 17 BSTreeNode *m_pLeft; // left child of node 18 BSTreeNode *m_pRight; // right child of node 19 }; 20 start time = 14:31 21 end time = 16:04 22 */ 23 #include <iostream> 24 #include <stdlib.h> 25 using namespace std; 26  27 typedef struct BSTreeNode 28 { 29 int m_nValue; // value of node 30 BSTreeNode *m_pLeft; // left child of node 31 BSTreeNode *m_pRight; // right child of node 32 }BSTreeNode; 33  34 int addBSTreeNode(BSTreeNode * &T, int data)  //把data加入的以T为根的树中 35 { 36     if(T == NULL) //根节点单独处理 37     { 38         T = (BSTreeNode *)malloc(sizeof(BSTreeNode)); 39         T->m_nValue =http://www.mamicode.com/ data; 40         T->m_pLeft = NULL; 41         T->m_pRight = NULL; 42     } 43     else 44     { 45         BSTreeNode * x = T; 46         BSTreeNode * px = NULL; 47         while(x != NULL) 48         { 49             if(data >= x->m_nValue) 50             { 51                 px = x; 52                 x = x->m_pRight; 53             } 54             else 55             { 56                 px = x; 57                 x = x->m_pLeft; 58             } 59         } 60  61         if(data >= px->m_nValue) 62         { 63             px->m_pRight = (BSTreeNode *)malloc(sizeof(BSTreeNode)); 64             px->m_pRight->m_nValue =http://www.mamicode.com/ data; 65             px->m_pRight->m_pLeft = NULL; 66             px->m_pRight->m_pRight = NULL; 67         } 68         else 69         { 70             px->m_pLeft = (BSTreeNode *)malloc(sizeof(BSTreeNode)); 71             px->m_pLeft->m_nValue =http://www.mamicode.com/ data; 72             px->m_pLeft->m_pLeft = NULL; 73             px->m_pLeft->m_pRight = NULL; 74         } 75     } 76     return 1; 77 } 78  79 BSTreeNode * findMin(BSTreeNode * z) 80 { 81     BSTreeNode * x = z; 82     while(x->m_pLeft != NULL) 83     { 84         x = x->m_pLeft; 85     } 86     return x; 87 } 88  89 BSTreeNode * findMax(BSTreeNode * z) 90 { 91     BSTreeNode * x = z; 92     while(x->m_pRight != NULL) 93     { 94         x = x->m_pRight; 95     } 96     return x; 97 } 98  99 BSTreeNode * findparent(BSTreeNode * T,BSTreeNode * z)100 {101     BSTreeNode * x = T;102     BSTreeNode * px = NULL;103     while(x != NULL)104     {105         if(z->m_nValue > x->m_nValue)106         {107             px = x;108             x = x->m_pRight;109         }110         else if(z->m_nValue < x->m_nValue)111         {112             px = x;113             x = x->m_pLeft;114         }115         else116         {117             if(z == x) //对数值相同的情况做判断 118             {119                 return px;120             }121             else122             {123                 px = x;124                 x = x->m_pRight;125             }126         }127     }128     return NULL;129 }130 131 BSTreeNode * BSTreefindSuccessor(BSTreeNode * T, BSTreeNode * z) //找二元查找树某个节点的后继132 {133     if(z->m_pRight != NULL)134     {135         return  findMin(z->m_pRight);136     }137     else138     {139         BSTreeNode * y = findparent(T, z);140         while(y != NULL && z == y->m_pRight)141         {142             z = y;143             y = findparent(T, z);144         }145         return y;146     }147 }148 149 BSTreeNode * BSTree2OrderedList(BSTreeNode * T) //把二元查找树转换为排序的双向链表150 {151     BSTreeNode * start = findMin(T);152     BSTreeNode * end = findMax(T);153     BSTreeNode * x = start;154     BSTreeNode * root = T;155     while(x != NULL)156     {157         BSTreeNode * xs = BSTreefindSuccessor(root, x);158         if(xs == root && root != NULL) //当root 左右子树的指向改变的时候 要更新找后继的树根 否则根的右子树变化了 用找后继会出错159         {160             root = root->m_pRight;161         }162         if(xs != NULL)163         {164             x->m_pRight = xs;  //向右指向下一个比它大的值165             xs->m_pLeft = x;   //向左指向下一个比它小的值166         }167         x = xs;168     }169     return start;170 }171 172 173 int main()174 {175     BSTreeNode * T = NULL;176     addBSTreeNode(T, 10);177     addBSTreeNode(T, 6);178     addBSTreeNode(T, 6);179     addBSTreeNode(T, 4);180     addBSTreeNode(T, 8);181     addBSTreeNode(T, 12);182     addBSTreeNode(T, 16);183 184     BSTreeNode * ans = BSTree2OrderedList(T);185 186     return 0;187 188 }

 1 template<typename T> 2 struct TreeNode 3 { 4     T data; 5     TreeNode* pLChild; 6     TreeNode* pRChild; 7 }; 8  9 // 要求两个输出参数要初始化为NULL10 template<typename T>11 void ConvertBSTree2List(TreeNode<T>* pTreeRoot/*树的根节点*/, TreeNode<T>*& pListHead/*双向链表的头指针*/, TreeNode<T>*& pListLast/*双向链表的尾指针*/)12 {13     if(pTreeRoot == NULL)14     {15         return;16     }17 18     // 中序遍历左子树19     ConvertBSTree2List(pTreeRoot->pLChild, pListHead, pListLast);20 21     // 处理当前节点，把节点链到双向链表尾部22 23     // 修改当前节点左指针，指向双向链表尾部24     pTreeRoot->pLChild = pListLast;25     if(pListLast)        // 非第一个节点26     {27         pListLast->pRChild = pTreeRoot;28     }29     else                // 第一个节点30     {31         pListHead = pTreeRoot;    32     }33 34     pListLast = pTreeRoot;35 36     // 中序遍历右子树37     ConvertBSTree2List(pTreeRoot->pRChild, pListHead, pListLast);38 }