博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
二叉查找树中节点的删除
阅读量:5265 次
发布时间:2019-06-14

本文共 1270 字,大约阅读时间需要 4 分钟。

  二叉查找树重要性质:

                                            (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;

                                            (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;

                                            (3)左、右子树也分别为二叉排序树;

    现有,如下一棵二叉查找树。

                             

                                                                      (图1)

    现在,若要删除图1中,任意节点,需要考虑如下三种情况:

    (1)需要删除的节点下并没有其他子节点。

    (2)需要删除的节点下有一个子节点(左或右)。

    (3)需要删除的节点下有两个子节点(既左右节点都存在)。

    第一种情况直接删除即可,下面,直接讨论第二种情况。

    若我们要删除的是3号节点,由图1可以看到,它下面还有一个4号子节点。由下图2,可以看出,对于这种办法,我们只需要想办法,让5号节点的左子树的指针指向4就可以了。

                                        

                                                                       (图2)

    第三种情况,既我们要删除的节点下,有2个子节点。如图3,我们先在需要删除的节点的右子树中,找到一个最小的值(因为右子树中的节点的值一定大于根节点)。然后,用找到的最小的值与需要删除的节点的值替换。然后,再将最小值的原节点进行删除(图4)。

                                          

                                                                          (图3)

                                           

                                                                             (图4)

    好了,思路大概就这样了。下面见代码。

[java]   
 
  1. private Node<T> remove(T data,Node<T> node)  
  2. {  
  3.     if(data == null)  
  4.         return node;  
  5.     /** 
  6.      * compare函数内部实现大致如下: 
  7.      * ((comparable)data).compareTo(node.element); 
  8.      * 比较需要删除的数据与当前节点的值的大小 
  9.      */  
  10.     int result = compare(data,node.element);  
  11.     //result<0:表示需要删除的节点在左子树。(二叉查找数的性质)  
  12.     if(result<0)  
  13.         node.left = remove(data,node.left);  
  14.     else if(result>0)//在右子树  
  15.         node.right = remove(data,node.right);  
  16.     else if(node.left != null && node.right != null)//找到需要删除的节点且节点下有两个子节点  
  17.     {  
  18.         /**先找到需要删除的节点下,右子树中最小的节点 
  19.          * 并将它的值赋给需要删除的节点。 
  20.          * */  
  21.         node.element = findMin(node.right).element;  
  22.         //删除前面找到的最小的节点。  
  23.         node.right = remove(node.right);  
  24.     }  
  25.     else//找到需要删除的节点且节点下有一个子节点(左或者右)  
  26.         node = (node.left != null) ? node.left : node.right;  
  27. }  
  28.   
  29. public void remove(T data)  
  30. {  
  31.     this.remove(data,root);  
  32. }  

    学习笔记。拍砖请轻拍。- -

转载于:https://www.cnblogs.com/qiaoyanlin/p/6746362.html

你可能感兴趣的文章
A - Vasya and Socks
查看>>
项目管理、设计开发、代码管理、bug管理工具介绍
查看>>
分布式计算开源框架Hadoop介绍
查看>>
安卓平台接口剖析
查看>>
linux文件编码查看与修改
查看>>
[Java] 系统环境变量配置
查看>>
坏的事情不都会带来坏的结果
查看>>
设置placeholder的样式
查看>>
RPC的基础:调研EOS插件http_plugin
查看>>
HIT1946 希尔伯特分形曲线(dfs)
查看>>
第二次团队冲刺第二天
查看>>
青瓷引擎之纯JavaScript打造HTML5游戏第二弹——《跳跃的方块》Part 2
查看>>
bzoj 2257 (JSOI 2009) 瓶子与燃料
查看>>
11)Java abstract class 和 interface
查看>>
使用xrdp或Xmanager 远程连接 CentOS6
查看>>
CDC类介绍
查看>>
SEH简单研究
查看>>
Linux误删恢复
查看>>
Unity调用Windows窗口句柄,选择文件和目录
查看>>
字节流缓存
查看>>