【数据结构】之二叉排序树的实现（C语言）

如果我们要查找的数据集是有序线性表&＃xff0c;并且是顺序存储的&＃xff0c;查找可以用折半&＃xff0c;插值&＃xff0c;等查找算法来实现。可惜&＃xff0c;因为有序&＃xff0c;在插入和删除操作上&＃xff0c;就需要耗费大量的时间。

有没有一种既可以使得插入和删除的效率不错&＃xff0c;又可以比较高效率的实现查找的算法呢&＃xff1f;

二叉排序树

二叉排序树&＃xff0c;又称为二叉查找树。它或者是一颗空树&＃xff0c;或者是具有下列性质的二叉树。

• 若他的左子树不为空&＃xff0c;则左子树上所有结点的值均小于他的根节点的值。
• 若他的右子树不为空&＃xff0c;则右子树上所有结点的值均大于他的根节点的值。
• 他的左&＃xff0c;右子树也分别为二叉排序树。

从二叉树的定义也可以知道&＃xff0c;它的前提是二叉树&＃xff0c;然后它采用了递归的定义方法&＃xff0c;再者&＃xff0c;它的结点间满足一定的次序关系&＃xff0c;左子树结点一定比其双亲结点小&＃xff0c;右子树结点一定比其双亲结点大。
构造一颗儿二叉排序树的目的&＃xff0c;其实并不是为了排序&＃xff0c;而是为了提高查找和插入删除关键字的速度。在一个有序数据集上的查找&＃xff0c;速度总是要快于无序的数据集的。而二叉排序树这种非线性结构&＃xff0c;也有利于插入和删除的实现。

二叉排序树的查找操作

定义一个二叉树的结构

/* 二叉树的二叉链表结点结构定义 */
typedef struct BiTNode /* 结点结构 */
{int data; /* 结点数据 */struct BiTNode *lchild, *rchild; /* 左右孩子指针 */
} BiTNode, *BiTree;


实现二叉排序树的查找

/* 递归查找二叉排序树T中是否存在key, */
/* 指针f指向T的双亲&＃xff0c;其初始调用值为NULL */
/* 若查找成功&＃xff0c;则指针p指向该数据元素结点&＃xff0c;并返回TRUE */
/* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{ if (!T) /* 查找不成功 */{ *p &＃61; f; return FALSE; }else if (key&＃61;&＃61;T->data) /* 查找成功 */{ *p &＃61; T; return TRUE; } else if (key<T->data) return SearchBST(T->lchild, key, T, p); /* 在左子树中继续查找 */else return SearchBST(T->rchild, key, T, p); /* 在右子树中继续查找 */
}

二叉排序树的插入操作

有了二叉排序树的查找函数&＃xff0c;那么所谓的二叉排序树的插入&＃xff0c;其实就是将关键字放到树中合适的位置而已。

/* 当二叉排序树T中不存在关键字等于key的数据元素时&＃xff0c; */
/* 插入key并返回TRUE&＃xff0c;否则返回FALSE */
Status InsertBST(BiTree *T, int key)
{ BiTree p,s;if (!SearchBST(*T, key, NULL, &p)) /* 查找不成功 */{s &＃61; (BiTree)malloc(sizeof(BiTNode));s->data &＃61; key; s->lchild &＃61; s->rchild &＃61; NULL; if (!p) *T &＃61; s; /* 插入s为新的根结点 */else if (key<p->data) p->lchild &＃61; s; /* 插入s为左孩子 */else p->rchild &＃61; s; /* 插入s为右孩子 */return TRUE;} else return FALSE; /* 树中已有关键字相同的结点&＃xff0c;不再插入 */
}

二叉排序树的删除操作

对于删除情况我们要考虑多种情况&＃xff0c;并不是那么容易的。我们不能因为删除了结点&＃xff0c;而让这棵树变得不满足二叉排序树的特性。
如下图1-1所示&＃xff0c;我们需要查找并删除入37,51,73,93&＃xff0c;这些在二叉排序树中是叶子结点。那是很容易的&＃xff0c;因为删除它&＃xff0c;他们呢对于整棵树来说&＃xff0c;其他的结点并没有受到影响。

图1-1

对于要删除的结点只有左子树金额右子树的情况&＃xff0c;相对也比较好解决&＃xff0c;那就是结点删除之后&＃xff0c;将它的左子树和右子树整个移动到删除结点的位置即可&＃xff0c;可以理解为子承父业。如下图1-2所示&＃xff0c;就是先删除35&＃xff0c;和99结点&＃xff0c;在删除58结点的变化图&＃xff0c;删除完后&＃xff0c;整个结构还是一个二叉排序树。

图1-2

但是对于要删除的结点既有左子树又有右子树的情况怎么办&＃xff1f;如图1-3所示中的结点47若要删除&＃xff0c;它的两个儿子以及子孙怎么处理了&＃xff1f;

图1-3

起初的想法&＃xff0c;我们当47结点只有一个左子树&＃xff0c;那么做法和一个左子树的操作一样&＃xff0c;让35及它之下的结点成为58的左子树&＃xff0c;然后再对47的右子树所有节点进行插入操作&＃xff0c;图1-4所示&＃xff0c;但是结点47的右子树共有5个子孙结点&＃xff0c;这么做效率低下&＃xff0c;而且还会导致整个二叉排序树的结构发生很大的变化&＃xff0c;有可能会增加树的高度。

图1-4

观察观察&＃xff0c;47的两个子树中能否找出一个结点可以替代47了&＃xff1f; 37或者48都可替代。
为什么是37和48了&＃xff1f;对的&＃xff0c;因为他们正好是二叉排序树中比他小或比他大的最接近47的两个数。
因此较好的办法就是&＃xff0c;找到需要删除的结点p的直接前驱或者直接后继s&＃xff0c;用s来替换结点p&＃xff0c;然后在删除结点s&＃xff0c;图1-5所示。

图1-5

根据对删除结点的三种情况的分析&＃xff1a;

• 叶子节点
• 仅有左或右子树的结点。
• 左右子树都有的结点。

/* 从二叉排序树中删除结点p&＃xff0c;并重接它的左或右子树。 */
Status Delete(BiTree *p)
{BiTree q,s;if((*p)->rchild&＃61;&＃61;NULL) /* 右子树空则只需重接它的左子树&＃xff08;待删结点是叶子也走此分支) */{q&＃61;*p; *p&＃61;(*p)->lchild; free(q);}else if((*p)->lchild&＃61;&＃61;NULL) /* 只需重接它的右子树 */{q&＃61;*p; *p&＃61;(*p)->rchild; free(q);}else /* 左右子树均不空 */{q&＃61;*p; s&＃61;(*p)->lchild;while(s->rchild) /* 转左&＃xff0c;然后向右到尽头&＃xff08;找待删结点的前驱&＃xff09; */{q&＃61;s;s&＃61;s->rchild;}(*p)->data&＃61;s->data; /* s指向被删结点的直接前驱&＃xff08;将被删结点前驱的值取代被删结点的值&＃xff09; */if(q!&＃61;*p)q->rchild&＃61;s->lchild; /* 重接q的右子树 */ elseq->lchild&＃61;s->lchild; /* 重接q的左子树 */free(s);}return TRUE;
}/* 若二叉排序树T中存在关键字等于key的数据元素时&＃xff0c;则删除该数据元素结点, */
/* 并返回TRUE&＃xff1b;否则返回FALSE。 */
Status DeleteBST(BiTree *T,int key)
{ if(!*T) /* 不存在关键字等于key的数据元素 */ return FALSE;else{if (key&＃61;&＃61;(*T)->data) /* 找到关键字等于key的数据元素 */ return Delete(T);else if (key<(*T)->data)return DeleteBST(&(*T)->lchild,key);elsereturn DeleteBST(&(*T)->rchild,key);}
}

总结

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