~~~ #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 ; } ~~~