#include<stdio.h>#include<stdlib.h>typedef struct STree{ int date; struct STree *left,*right;}BSTNode;int BSTInsert(BSTNode *&bt,int k){ BSTNode *f,*p = bt; while(p != NULL) { if(p->date = k) return 0; f = p; //f指向*p结点的双亲结点 if(p->date < k) p = p->right; //在右子树中查找 else p = p->left; //在左子树中查找 } p = (BSTNode *)malloc(sizeof(BSTNode)); p->left = p->right = NULL; p->date = k; if(bt == NULL) bt = p; //原树为空时，*P作为根节点插入 else if(k < f->date) f->left = p; //插入*p作为*f的左孩子 else f->right = p; //插入*p作为*f的右孩子 return 1;}void CreateBST(BSTNode *&bt,int str[],int n){ bt = NULL; int i = 0; while(i < n) { BSTInsert(bt,str[i]); i++; }}void Display(BSTNode *bt){ if(bt != NULL) { printf("%d ",bt->date); Display(bt->left); Display(bt->right); }}//二叉树删除节点思路：首先在二叉顺序树中查找关键字为k的结点p,用f指向其双亲结点//(1)如果p结点无右子树则用*p结点的左孩子替换它//(2)如果p结点无左子树则用*p结点的右孩子替换它//(3)如果p结点既有左子树又有右子树，则可以用*p结点的左子树的最右下结点替换它，也可以用*p结点的右子树的最左下结点替换它int BSTDelete(BSTNode *&bt,int k){ BSTNode *p = bt,*f,*r,*f1; f = NULL; while(p != NULL && p->date != k) { f = p; if(p->date > k) p = p->left; //在左子树中查找 else p = p->right; //在右子树中查找 } if(p == NULL) return 0; else if (p->left == NULL) //*p 为被删除结点，若它无左子树 { if (f == NULL) bt = p->right; else if (f->left = p) //p是双亲结点的左孩子，则用其右孩子替换它 { f->left = p->right; free(p); } else if (f->right = p) //p是双亲结点的右孩子，则用其右孩子替换它 { f->right = p->right; free(p); } } else if (p->right == NULL) //*p 为被删除结点，若它无右子树 { if(f == NULL) bt->left; if(f->left == p) { f->left = p->left; free(p); }else if (f->right == p) { f->right = p->left; free(p); } }else { f1 = p; r = p->left; while(r->right != NULL) { f1 = r; r = r->right; } if(f1->left == r) f1->left = r->right; else if (f1->right = r) f1->left = p->left; r->left = p->left; r->right = p->right;
if(f == NULL) bt = r; else if (f->left == p) f->left = r; else f->right = r; free(p); } return 1;}int main(){ BSTNode *bt = NULL; int a[10] = {1,3,5,7,8,12,16,23,45,56}; CreateBST(bt,a,10); Display(bt); return 0;}
