二叉排序树

1. 二叉排序树又称二叉查找树、二叉搜索树。它的基本性质有：

• 若它的左子树不空，则左子树上所有结点的值均小于它根结点的值。
• 若它的右子树不空，则右子树上所有结点的值均大于它根结点的值。
• 它的左、右树又分为⼆叉排序树

构造二叉排序树的目的并不是为了排序，而是为了提高查找和插入删除关键字的速度。

2.二叉排序树的创建：

根据性质可以容易得到创建的规则：

• 只要左子树为空，就把小于父节点的数插入作为左子树
• 只要右子树为空，就把大于父节点的数插入作为右子树
• 如果不为空，就一直往下去搜索，直到找到合适的插入位置

 其实这就是一个插入的过程：

int insert(struct node *tree,int key)
{struct node *p,*s;if(!search(*tree,key,NULL,&p)){s=(struct node)malloc(sizeof(struct node));s->data=key;s->left=s->right=NULL;if(!p) *tree=s;else if(key<p->data) p->left=s;else p->right=s;return 1;}else return 0;
}

3.二叉排序树的查找

查找，更据二叉排序树的性质，如果大于当前节点则往该节点的右子树继续向下查找，小于当前节点则往左子树方向查找。

int search(struct node *tree,int k,struct node *f,struct node *p)
{if(!tree){*p=f;return 0;}else if(key==tree->data){*p=tree;return 1;}else if(key<tree->data)return search(tree->left,key,tree,p);else return search(tree->right,key,tree,p);	
}

4.二叉排序树的删除，对于删除有3种情况：

• 删除叶子节点
• 删除仅有左或右子树的节点
• 左右子树都有节点

 先用递归查找key所在的位置，找到了就删除。

删除的代码：

int del(struct node *p)
{struct node q,s;if((*p)->right==NULL){q=*p;*p=(*p)->left;free(q);}else if((*p)->left==NULL){q=*p;*p=(*p)->right;free(q);}else {q=*p;s=(*p)->left;while(s->right){q=s;s=s->right;}(*p)->data=s->data;if(q!=p)q->right=s->left;else q->left=s->left;free(s);}return 1;
}

写了一个bfs的题目：

P1135奇怪的电梯_Repeat715的博客-CSDN博客