~~~ #include "stdio.h" #include "iostream.h" typedef struct node { int data ; node*lChild ; node*rChild ; }TreeNode ; void Insert(TreeNode**root,int data) //向二叉查找樹中插入元素 采用非遞歸思想 { TreeNode * p=*root ;//獲得根結點 TreeNode*q=new TreeNode ;//分配一個要插入的新節點 q->lChild=q->rChild=NULL ; //新分配節點的左節點=右節點等于NULL q->data=data ; //保存數據到節點 TreeNode *parent =p ; //用于保存父節點 while(p!=NULL) //循環搜索節點 { parent=p ; //首先parent指向root節點 if(p->data>data) //如果節點數據大于當前節點 p=p->lChild ;//如果插入數據小于 節點數據那么指向左節點 我么最終是要找到一個NULL節點 else p=p->rChild ; } //如果因為parent總是指向NULL節點的父節點 ,所以parent指向的節點不會為空,如果為空那么說明該樹是一顆空的樹。 if(parent==NULL) *root=q ; //將分配的節點作為根節點 else if(parent->data>data) parent->lChild=q ; //<root左插 else parent->rChild=q ; //>root右插 } void InOrder(TreeNode*root) { if(root!=NULL) { InOrder(root->lChild) ; printf("%d ",root->data) ; InOrder(root->rChild) ; } } bool Find(TreeNode*root,int fData) //非遞歸方法查詢 { if(root==NULL) return false ; //搜索樹為空返回false while(root!=NULL) { if(root->data==fData) return true ; if(root->data>fData) root=root->lChild ; else root=root->rChild ; } return false ; } void BST_Delete(TreeNode**tp ,int dData) //刪除節點 { TreeNode*root=*tp ; TreeNode* parent =NULL ;//父指針用來表示 是否是根節點 while(root!=NULL) { //循環查找 if(dData<root->data) //如果刪除節點小于根節點數據 { parent=root ; //保存前一個節點的指針 root=root->lChild ; //dData小于root數據 那么查找左子樹 } else if(dData>root->data) { parent=root ; root=root->rChild ; //大于root數據那么查找右節點 } else //這里找到了節點 如果即不大于 節點數據 也不小于節點數據 并且節點不是NULL那就說明了 節點查找到了 ,揭曉來我們就需要判斷節點并刪除了。 { if(root->lChild==NULL&&root->rChild==NULL) //是葉子節點 1、根節點 2、非根節點 { if(parent==NULL) //因為parent是NULL說明沒有根節點 否則parent是不可能為NULL的 { delete root ;//直接刪除根節點 root=NULL ; *tp=NULL ; return ; //直接返回 } else //如果是非根節點的葉子節點 { (parent->lChild==root)?(parent->lChild=NULL):(parent->rChild=NULL) ; //判斷刪除節點是parent的left還是right delete root ; return ;//對于葉子節點可以直接返回 } } else if(root->lChild==NULL&&root->rChild!=NULL) //待刪除節點只有有孩子 情況和上面類似 { if(parent==NULL) //如果在是根節點 并且有右孩子的情況下 { *tp=root->rChild ;//只有右孩子 那么指針移動到右孩子 保存到tp delete root ; return ; } else { (parent->lChild==root)?(parent->lChild=root->rChild):(parent->rChild=root->rChild) ; //令parent的left或者right指向 root的left delete root; return ; } } else if(root->lChild!=NULL&&root->rChild==NULL) //待刪除節點只有左孩子 情況和上面類似 { if(parent==NULL) //如果在是根節點 并且有右孩子的情況下 { *tp=root->lChild ;//待刪除節點只有左孩子 那么指針移動到左孩子 delete root ; return ; } else { (parent->lChild==root)?(parent->lChild=root->lChild):(parent->rChild=root->lChild) ; //令parent的left或者right指向 root的left delete root ; return ; } } else //最后一種 刪除節點既有做孩子又有右孩子 { TreeNode *p=root->lChild ;//定義一個p保存當前刪除節點 我們利用這個節點左孩子找到最右下節點 。 while(p->rChild!=NULL) { parent=p ; //保存右下節點的父節點指針 p=p->rChild ;//從待刪除節點 } root->data=p->data ; parent->rChild=p->lChild ; delete p ; return ; } } } } int main(int argc,char*argv[]) { TreeNode *root=NULL; //如果根節點指針在局部那么一定要初始化NULL否則程序崩潰 ,如果我們的指針是在全局定義的可以不初始化NULL全局變量放在靜態存儲區 int a[]={32,36,15,53,18,45,72,48,16,93} ; for(int i=0;i<10;i++) Insert(&root,a[i]) ; InOrder(root) ; printf("\n") ; if(Find(root,0)) printf("數據0找到\n") ; else printf("沒有0數據\n") ; BST_Delete(&root,36) ; InOrder(root) ; return 1 ; } ~~~