二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表代碼

1、題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。比如將二元查找樹                                       

2、60;     10                                           /  

3、0;                                           6       14 

4、;                                      /         /      

5、;                               4     8   12 16轉(zhuǎn)換成雙向鏈表4=6=8=10=12=14=16。/*1.二叉樹中序遍歷的結(jié)果與鏈表的順序一致，所以可以采用中序遍歷的方法來修改二叉樹的

6、指針2.該題的關(guān)鍵是，如何將左子樹的最大值與右子樹的最小值通過根root連接起來，比如題目的8和12，這也是細(xì)節(jié)部分3.寫遞歸程序最重要的是弄明白遞歸進(jìn)入的條件、遞歸返回的狀態(tài)，如果遞歸進(jìn)入時(shí)改變了環(huán)境，返回時(shí)應(yīng)當(dāng)恢復(fù)環(huán)境，就像棧的操作一樣4.使用指針變量時(shí)，要記得初始化5.該算法沒有返回鏈表頭，而是返回了root。*/以下圖片為測(cè)試結(jié)果：/*節(jié)點(diǎn)定義*/typedef struct nodechar value;struct node *left;struct node *right;BSTree;/*查找以tr為根最左邊的節(jié)點(diǎn)，即以tr為根的二叉排序樹的最小值*/BSTree *findL

7、eft(BSTree *trBSTree *p = NULL;while(tr->leftp = tr->left;tr = p; return tr;/*查找以tr為根最右邊的節(jié)點(diǎn)，即以tr為根的二叉排序樹的最大值*/BSTree *findRight(BSTree *trBSTree *p = NULL;while(tr->rightp = tr->right;tr = p;return tr;/*實(shí)現(xiàn)將二叉排序樹數(shù)轉(zhuǎn)變?yōu)殡p鏈表*/BSTree *ConvertBSTreeToList(BSTree *rootif(!*rootreturn (BSTree *NUL

8、L;BSTree *lt=NULL,*rt=NULL;if(*root->right/*先處理右子樹，其實(shí)先處理左子樹也行*/rt = ConvertBSTreeToList(&(*root->right;/*遞歸進(jìn)入*/if(*root->right/*遞歸返回處理，如果該根節(jié)點(diǎn)的右子樹有最小值，則將該最小值的節(jié)點(diǎn)與root連起來，否則直接處理*/lt = findLeft(*root->right;if(ltrt = lt;if(rtrt->left = *root;(*root->right = rt;if(*root->leftlt =

9、 ConvertBSTreeToList(&(*root->left;/*遞歸進(jìn)入*/if(*root->left/*遞歸返回處理，如果該根節(jié)點(diǎn)的左子樹有最大值，則將該最大值的節(jié)點(diǎn)與root連起來，否則直接處理*/rt = findRight(*root->left;if(rtlt = rt;if(ltlt->right = *root;(*root->left = lt;return *root;/*遞歸創(chuàng)建二叉排序樹，以','結(jié)束*/void CreateBSTree(BSTree *trBSTree *p = (BSTree *mal

10、loc(sizeof(node;scanf_s("%c",&p->value;p->left = NULL;p->right = NULL;if(p->value != ','if(!(*tr*tr = p;(*tr->left = NULL;(*tr->right = NULL;else return;CreateBSTree(&(*tr->left;CreateBSTree(&(*tr->right;int _tmain(int argc, _TCHAR* argvBSTree *binaryTree = NULL,*list = NULL;CreateBSTree(&binaryTree;list = ConvertBS