#includestruct BSTNode { int m_nval; //數據域 BSTNode *m_pleft; // 左孩子節點 BSTNode *m_pright; //右孩子節點 }; /************************************************************************ 功能:在二叉排序樹中 查找key值,如果找到,返回true,且plast指向該節點。 plastfahter指向該雙雙親節點。如果沒找到,返回false,且plast指向最後遍歷 的最後一個節點(也就是如果 要插入的節點話,直接new一個節點,和plast節點鏈接,完成插入) 輸入:T:BST樹 根,key:要查找的值,pfather:T的父節點, 輸出:plast:保存找到的節點,或者待插入節點的父節點位置。plastfather:找到節點的父節點 返回:true or false. /************************************************************************/ bool SearchBST(BSTNode * &T,int key,BSTNode * pTfather,BSTNode * &plast,BSTNode * &plastfather) { if(NULL == T) //該樹為空 或 到底了 { plast = pTfather ; //pfather指向 plast的父節點 以NULL初始化 return false; } if(key == T->m_nval) { plast = T; //如果找到 plast 指向該節點 plastfather = pTfather; // plastfather 指向 該節點父節點 return true; } else { if( key > T->m_nval ) //往右子樹查找 return SearchBST(T->m_pright,key,T,plast,plastfather); else { if( key < T->m_nval)//往左子樹查找 return SearchBST(T->m_pleft,key,T,plast,plastfather); } } } bool InsertBST(BSTNode* &T,int key) { BSTNode *pToBeInsert,*pNew,*plastfather; if(!SearchBST(T,key,NULL,pToBeInsert,plastfather))//如果找到 就不插入 { pNew = new BSTNode(); pNew->m_nval = key; pNew->m_pleft = pNew->m_pright = NULL; if(!pToBeInsert) T = pNew ; //如果 ptobeinsert 為NULL 則該樹為空 else { if( key > pToBeInsert->m_nval) pToBeInsert ->m_pright = pNew; else pToBeInsert ->m_pleft = pNew ; return true; } }else return false; } BSTNode* CreateBST(int a[],int len) { BSTNode *T = NULL; for(int i=0 ; i m_pleft == NULL) //只有右子樹 或 葉子節點 {//直接 將其右子樹 鏈入BST中 if(pKeyNodeFather->m_pleft == pKeyNode) pKeyNodeFather->m_pleft = pKeyNode->m_pright; else pKeyNodeFather->m_pright = pKeyNode->m_pright; delete pKeyNode; //釋放 節點內存 } else { if(pKeyNode->m_pright == NULL) //只有左子樹 { if(pKeyNodeFather->m_pleft == pKeyNode) pKeyNodeFather->m_pleft = pKeyNode->m_pleft; else pKeyNodeFather->m_pright = pKeyNode->m_pleft; delete pKeyNode; //釋放 節點內存 } else // 既不是葉子節點和單孩子樹。查找 前驅節點(左子樹的最右節點) { BSTNode *pre=pKeyNode,*pcur=pKeyNode->m_pleft; //記錄 前驅指針,和當前指針 while(pcur -> m_pright) { pre = pcur; pcur = pcur->m_pright; } // 此時 pcur 指向 替代的節點 pKeyNode ->m_nval = pcur ->m_nval ; //覆蓋了 pkeyNode 間接刪除 //下面 就要刪除pcur,之前 需要完成鏈接 if(pre != pKeyNode) // now pcur並不是pkeyNodepleft. pre->m_pright = pcur->m_pleft ; // 將pcur左子樹 鏈入 其父節點的右節點 else //pre == pkeyNode pcur為 葉子節點 pre->m_pleft = pcur->m_pleft ; delete pcur; } } return true; } else return false; } void InOrderTravseBST(BSTNode *T) { if(T) { InOrderTravseBST(T->m_pleft); printf("%d ",T->m_nval); InOrderTravseBST(T->m_pright); } } /*********************測試代碼********************************/ void Test() { // 測試1 創建 /* 10 / \ 2 13 \ / \ 7 11 78 / / \ 6 9 23 / / / 4 8 12 */ int a[]={10,13,11,2,7,9,8,6,4,78,23,12,8}; int len = sizeof(a)/sizeof(int); BSTNode *T = CreateBST(a,len); printf("中序遍歷創建的BST:\n"); InOrderTravseBST(T); printf("\n"); //測試2 查找 BSTNode *pfind=NULL,*pfindfather=NULL; printf("查找 key == 4:\n"); int key = 4; if(SearchBST(T,key,NULL,pfind,pfindfather)) { printf("查找成功,pfind->m_nval=%d,pfindfater->m_nval=%d\n",pfind->m_nval,pfindfather->m_nval); }else printf("查找key = %d 失敗\n",key); //測試3 插入 key = 15; if(InsertBST(T,key)) printf("插入key = %d成功\n中序遍歷為:\n",key); else printf("插入key = %d失敗\n中序遍歷為:\n",key); InOrderTravseBST(T); printf("\n"); //測試4 刪除 根節點 key = 10; if(DeleteBSTNode(T,key)) { printf("刪除key = %d 節點成功\n",key); }else printf("刪除key = %d 節點失敗\n",key); printf("中序遍歷為:\n"); InOrderTravseBST(T); printf("\n"); //測試5 刪除 只有右子樹 key = 2; if(DeleteBSTNode(T,key)) { printf("刪除key = %d 節點成功\n",key); }else printf("刪除key = %d 節點失敗\n",key); printf("中序遍歷為:\n"); InOrderTravseBST(T); printf("\n"); //測試6 刪除 只有左子樹 key = 9; if(DeleteBSTNode(T,key)) { printf("刪除key = %d 節點成功\n",key); }else printf("刪除key = %d 節點失敗\n",key); printf("中序遍歷為:\n"); InOrderTravseBST(T); printf("\n"); //測試7 刪除 葉子節點 key = 78; if(DeleteBSTNode(T,key)) { printf("刪除key = %d 節點成功\n",key); }else printf("刪除key = %d 節點失敗\n",key); printf("中序遍歷為:\n"); InOrderTravseBST(T); printf("\n"); } int main() { Test(); return 0; }