java使用归并删除法删除二叉树中节点的方法
作者:hitxueliang 发布时间:2022-03-31 23:06:12
标签:java,二叉树,节点
本文实例讲述了java使用归并删除法删除二叉树中节点的方法。分享给大家供大家参考。具体分析如下:
实现的思想很简单:
first:找到要删除的节点
second:如果删除的节点没有右子树那么左子树链到父节点
third:如果删除的节点没有左子树那么右子树链到父节点
forth:如果删除的节点又左右孩子,那么可以归并删除节点后的子树:方法有两种一种是用删除节点的左子树的最右节点,指向删除节点的右子树,另一种是用删除节点的用字数的最左节点指向删除节点的左子树。
Java 实现如下:
public void deleteByMerging(int el)
{
IntBSTNode tmp,node,p=root,prev=null;
/*find the node to be deleted*/
while(p!=null&&p.key!=el)
{
prev=p;
if(p.key<el)
p=p.right;
else p=p.left;
}
/*find end*/
node=p;
if(p!=null&&p.key==el)
{
if(node.right==null)
//node has no right child then its left child (if any) is attached to
node=node.left;
//its parent
else if(node.left==null)
//node has no left child then its right child (if any) is attched to
node=node.right
//its parent
else{
tmp=node.left;
while(tmp.right!=null)
tmp=tmp.right;
//find the rightmost node of the left subtree
tem.right=node.right;
//establish the link between the rightmost node of the left subtree and the right subtree
node=node.left;
}
if(p==root)
{
root=node;
}
else if (prev.left==p)
{
prev.left=node;
}
else prev.right=node
}
else if(root!=null)
{
System.out.println("the node is not in the tree");
}
else System.out.println("The tree is empty");
}
希望本文所述对大家的java程序设计有所帮助。
0
投稿
猜你喜欢
- 这两天遇到一个服务假死的问题,具体现象就是服务不再接收任何请求,客户端会抛出Broken Pipe。检查系统状态执行top,发现CPU和内存
- JDK7前处理之前的练习,我们一直把异常抛出,而实际开发中并不能这样处理,建议使用try...catch...finally 代码块,处理异
- JPA是什么? JPA(Java Persistence API)是Sun官方提出的Java持久化规范. 为Java开发人员提供了一种对象/
- IDEA service层跳转实现类的快捷图标消失了,但别人IDEA同样的代码可以正常看到跳转图标。。(暗示:这只是你的IDEA 编译器的b
- 跨域问题,其实百度上面有一堆的解决方案针对普通的情况其实百度上面的方案都是可行的。我这里主要介绍2种情况。当然我这里的配置都是基于网关的,而
- 本文为大家分享了swing实现窗体拖拽和拉伸的具体代码,供大家参考,具体内容如下当用setUndecorated(true) 后 JFram
- 一、DES加密和解密package com.itjh.javaUtil;import java.io.UnsupportedEncoding
- 1.BIO1.1 简述BIO是同步阻塞IO,所有连接都是同步执行的,在上一个连接未处理完的时候是无法接收下一个连接1.2 代码示例在上述代码
- Lambda 表达式Lambda 表达式是现代 C++ 中最重要的特性之一,而 Lambda 表达式,实际上就是提供了一个类似匿名函数的特性
- 异常分类可查的异常(checked exceptions):Exception下除了RuntimeException外的异常不可查的异常(u
- 1.定义多态是同一个行为具有多个不同表现形式或形态的能力。多态性意味着有多重形式。在面向对象编程范式中,多态性往往表现为"一个接口
- 有时,类或方法需要对类型变量加以约束。下面是一个典型的例子,我们要寻找数组中的最小元素:public class ArrayAlg { &n
- 本文实例为大家分享了Java实现发送邮件并携带附件的具体代码,供大家参考,具体内容如下一、 邮件服务器与传输协议要在网络上实现邮件功能,必须
- 话不多说,请看实例代码String ip = request.getHeader("x-forwarded-for");
- Java去掉指定字符串的开头的指定字符/** * 去掉指定字符串的开头的指定字符 *
- 前言:上篇C#进阶系列——WebApi接口传参不再困惑:传参详解介绍了WebApi参数的传递,这篇来看看WebApi里面异常的处理。关于异常
- 一、前言用过Spring Cloud的同学都知道在使用动态配置刷新的我们要配置一个@RefreshScope 在类上才可以实现对象属性的的动
- WPF换肤的设计原理,利用资源字典为每种皮肤资源添加不同的样式,在后台切换皮肤资源文件。截图上图中,第一张图采用规则样式,第二张图采用不规则
- 网上各种解决方案,我试了好久,整合了几篇文章才凑出来,在这里分享一下,实在不想网友们在这里面绕圈子,毕竟,写代码的时间是愉快的,解决bug也
- 概述本文的编写初衷,是想了解一下Spring Boot2中,具体是怎么序列化和反序列化JSR 310日期时间体系的,Spring MVC应用