二叉排序树

在说二叉排序树之前先考虑这样一个例子，假设我们的数据集开始只有一个数{62}，然后现在需要将88插入数据集，于是数据集成了{62,88}，还保持着从小到大有序，再查找有没有58，没有则插入，可此时要想在线性表的顺序存储中有序，就得移动62和88的位置，如图所示，可不可以不移动呢？当然是可以，那就是二叉树结构，当我们用二叉树的方式时，首先将第一个数62定为根结点，88因为比62大，因此让它做62的右子树，58因此62小，所以成为它的左子树，此时58的插入并没有影响到62与88的关系。

也就是说，若我们现在需要对集合{62,88,58,47,35,73,51,99,37,93}做查找，在我们打算创建此集合时就考虑用二叉树结构，而且是排好序的二叉树来创建。以62，58，88这三个数组成的二叉树为基础，将剩下的数进行添加到树中，小于根结点的数作为左子树，大于根结点的树作为右子树，这样就得到了如图所示的二叉树，并且当我们对它进行中序遍历时，就可以得到一个有序的序列{35,37,47,51,58,62,73,88,93,99}，所以我们通常称它为二叉排序树。二叉排序树(Binary Sort Tree)，又称为二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：
1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
3.它的左丶右子树也分别为二叉排序树

二叉排序树的意义：构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度，不管怎么说，在一个有序数据集上的查找，速度总是要快于无序的数据集的，而二叉树排序这种非线性的结构，也有利于插入和删除的实现。

二叉排序树节点信息

typedef struct BiTNode
{int data;struct BiTNode* lchild, *rchild;
}BiTNode, *BiTree;

二叉排序树查找操作

#if 0
递归查找二叉排序树T中是否存在key
f指向T的双亲，初始调用值为NULL
查找成功则p指向该元素节点，否则p指向查找路径上访问最后一个节点并返回false
#endif
bool SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{if (!T){*p = f;return false;}else if (key == T->data){*p = T;return true;}else if (key < T->data)return SearchBST(T->lchild, key, T, p);elsereturn SearchBST(T->rchild, key, T, p);
}

二叉排序树插入操作

bool InsertBST(BiTree* T, int key)
{BiTree p, s;if (!SearchBST(*T, key, NULL, &p)){s = (BiTree)malloc(sizeof(BiTNode));s->data = key;s->lchild = s->rchild = NULL;if (!p)*T = s;			//插入为新根节点else if (key < p->data)p->lchild = s;	//插入为左孩子elsep->rchild = s;	//插入为右孩子return true;}elsereturn false;
}

二叉排序树创建

int i;
int a[10] = { 62,88,58,47,35,73,51,99,37,93 };
BiTree T = NULL;
for (int i = 0; i < 10; ++i)InsertBST(&T, a[i]);

二叉排序树删除操作

删除叶子结点：其他节点结构并未受影响

仅有左或者右子树的结点：也比较好解决，节点删除后将它的左/右子树整个移动到删除结点的位置即可(子承父业)

左右子树都有的结点：(删除47)

低效方式：，可能会增加树的高度

高效方式：找个可以替代47的结点，比如37和48，因为它们是最接近47的俩个数，如果对其进行中序遍历后，得到这俩个数正好是47的前驱和后继，因此比较好的方法是找到需要删除的结点p的直接前驱(或直接后继)s，来替换结点p，然后再删除此结点s

bool Delete(BiTree* p)
{BiTree q, s;if ((*p)->rchild == NULL)	//右子树空则只需要接它的左子树{q = (*p);*p = (*p)->lchild;free(q);}else if ((*p)->rchild == NULL){q = (*p);*p = (*p)->rchild;free(q);}else    //左右子树均不空{q = *p;s = (*p)->lchild;while (s->rchild)		//左子树中查找到右节点尽头(待删节点前驱){q = s;s = s->rchild;}(*p)->data = s->data;if (q != *p)q->rchild = s->lchild;  //重接q的右子树elseq->lchild = s->lchild;  //重接q的左子树(没有右节点，只有左节点的情况，比如左侧没有36、37只有35、29)free(s);}return true;
}bool DeleteBST(BiTree *T, int key)
{if (!*T)return false;else{if (key == (*T)->data)Delete(T);else if (key < (*T)->data)DeleteBST(&(*T)->lchild, key);elseDeleteBST(&(*T)->lchild, key);}
}

总结

二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入、删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后仅需修改链接指针即可，插入删除的时间性能比较好。对于二叉排序树的查找走的就是从根节点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数，最少为1次，最多不超过树的深度，也就是说，二叉排序树的查找性能取决于二叉排序树的形状。问题在于二叉排序树的形状不确定。

比如右边的也是一棵二叉排序树，但查找99结点，左图只需要两次比较，右图需要10次比较