【数据结构】二叉查找树
发布时间：2021-05-23 13:00:25 所属栏目：站长百科 来源：网络整理
导读：副标题#e# 1、概念： 二叉查找树，也称排序二叉树，是指一棵空树或者具备下列性质的二叉树(每个节点都不能有多于两个儿子的树)： 1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 2. 若任意节点的右子树不空，则右子树上所有节点
|
如果删除节点6，也就是根节点，先用其右子树的最小数据节点8代替该节点的数据，然后递归的删除节点8，这样删除节点8就和删除只有右儿子的数据节点操作(第4点)是一样的了。 为什么是用右子树的最小节点来替代呢？因为根据二叉查找树的特性，某节点的右子树的最小数据节点大于该节点的所有左子树节点，小于该节点的右子树节点当中除了最小节点的所有节点，这样用这个右子树最小数据节点代替该节点，那么操作之后的还是二叉查找树。 3）删除节点只有左儿子： 1. 该左儿子是叶子节点。删除节点4，由于节点(2)的右子树的所有节点键值均大于该节点键值，所以删除节点4后，直接用该节点的左儿子3取代节点4，这里的取代是将节点4的键值替换为3，这样该树中就有两个键值为3的节点，然后删除其左儿子节点3。过程如下图所示 /* * 6 6 6 * / / / * 2 8 3 8 3 8 * / --> / --> / * 1 4 10 1 3 10 1 3 10 * / / * 3 3 */ 2. 该左儿子不是叶子节点，考虑下面这种情况：删除节点6，那么就需要先查找该节点6左子树的最大数据节点替代该节点，然后递归的删除该左子树的最大数据节点，过程如下所示，至于为什么是左子树的最大数据节点，原因和上面分析的一样。 /* * 6 4 4 4 * / / / / * 2 2 2 2 * / --> / --> / --> / * 1 4 1 4 1 3 1 3 * / / / * 3 3 3 */ 4）删除节点只有右儿子： 1. 该右儿子是叶子节点，删除节点8，这个和删除只有左儿子的节点操作一样，过程如下所示 /* * 6 6 6 * / / / * 2 8 3 10 3 10 * / --> / --> / * 1 4 10 1 4 10 1 4 * / / * 3 3 */2. 该右儿子不是叶子节点 ：删除节点2，先找到该节点右子树的最小数据节点并用最小节点数据代替该节点，然后递归的删除最小节点，其实此时的最小节点就是右子树的左叶子节点，可以直接删除。过程如下所示 （编辑：网站开发网_盐城站长网 ） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐