二叉搜索樹和雙向鏈表

02-26

二叉搜索樹和雙向鏈表

輸入一顆二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。
思路：根節點，左子樹，右子樹。把左子樹、右子樹都轉換成排序的雙向鏈表，之後，再和根節點鏈接起來。整顆二叉搜索樹也就轉換成了排序的雙向鏈表。遞歸思想。

參考代碼：

root@gt:/home/git/Code# ./a.out 4 6 8 10 12 14 16 root@gt:/home/git/Code# cat convert.c #include <stdio.h>#include <stdlib.h>typedef struct BTreeNode{ int value; struct BTreeNode* pleft; struct BTreeNode* pright;}TreeNode;void core(TreeNode* proot,TreeNode** pplast){ if(!proot) return; TreeNode* pcurrent = proot; if(pcurrent->pleft) core(pcurrent->pleft,pplast); pcurrent->pleft = *pplast; if(*pplast) (*pplast)->pright = pcurrent; *pplast = pcurrent; if(pcurrent->pright) core(pcurrent->pright,pplast);}TreeNode* convert(TreeNode* proot){ TreeNode* plast = NULL; core(proot,&plast); TreeNode* phead = plast; while(phead && phead->pleft) phead = phead->pleft; return phead;}TreeNode* concore(int* preStart,int* preEnd,int* inStart,int* inEnd){//前序遍歷的地一個元素就是根節點 int rootValue = preStart[0]; TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->value = rootValue; root->pleft = root->pright = NULL;//在中序遍歷序號中找到根節點的值 int* rootIn = inStart; while(rootIn <= inEnd && *rootIn != rootValue) ++rootIn; int leftLen = rootIn - inStart; int* leftPreEnd = preStart + leftLen; if(leftLen>0) { root->pleft = concore(preStart+1,leftPreEnd,inStart,inStart+leftLen-1); } if(leftLen < preEnd - preStart) { root->pright = concore(leftPreEnd+1,preEnd,rootIn+1,inEnd); } return root;}TreeNode* construct(int* pre,int* in,int len){ if(pre==NULL || in==NULL || len<=0) return 0; return concore(pre,pre+len-1,in,in+len-1);}int main(){ int pre[] = {10,6,4,8,14,12,16}; int in[] = {4,6,8,10,12,14,16}; TreeNode* proot = construct(pre,in,sizeof(pre)/sizeof(int)); TreeNode* phead = convert(proot); TreeNode* pcurrent = phead; while(pcurrent) { printf("%d ",pcurrent->value); pcurrent = pcurrent->pright; } printf(" "); return 0;}