Java数据结构与算法(八)-二叉树
一、为什么要使用树
- 有序数组插入、删除数据慢。
- 链表查找数据慢
- 树可以解决这两个问题
二、相关术语
- 树的结点：包含一个数据元素及若干指向子树的分支；
- 孩子结点：结点的子树的根称为该结点的孩子；
- 双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；
- 兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；
- 祖先结点: 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中* 任一结点都称为该结点的子孙
- 结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；
- 树的深度：树中最大的结点层
- 结点的度：结点子树的个数
- 树的度： 树中最大的结点度。
- 叶子结点：也叫终端结点，是度为 0 的结点；
- 分枝结点：度不为0的结点；
- 有序树：子树有序的树，如：家族树；
- 无序树：不考虑子树的顺序；
三、基本操作
- 插入结点
- 从根结点开始查找一个相应的结点，这个结点成为新插入结点的父节点，当父节点找到后，通过判断新结点的值比父节点的值的大小来决定是连接到左子结点还是右子结点
- 查找结点
- 从根结点开始查找，如果查找的结点值比当前的结点的值小，则继续查找其左子树，否则查找其右子树。
- 遍历二叉树
- 遍历树是根据一个特定的顺序访问树的没一个节点，根据顺序的不通氛围前序、中序、后序三中遍历。
- 前序
- 访问跟节点
- 前序遍历左子树
3.遍历右子树
- 中序
- 遍历左子树
- 访问跟节点
3.遍历右子树
- 后序
- 遍历左子树
- 遍历右子树
3.访问跟节点
- 删除二叉树节点
- 删除是最复杂的，在删除之前首先要查找要删的节点。找到节点后，这个要删除的节点可能会有三中情况需要考虑。
- 该节点是叶子节点，没有子节点
- 要删除叶子节点，只需要改变该节点的父节点的引用值，将指向该节点的引用设置为null就可以了。
- 该节点有一个子节点
- 改变父节点的引用，将其直接指向要删除节点的子节点。
- 该节点右两个子节点
- 要删除右两个子节点的节点，就需要使用他的中序后继来替代该节点。
代码实现
package com.fantj.dataStruct.tree;/*** 二叉树结点* Created by Fant.J.* 2017/12/22 16:09*/
public class Node {//数据项public long data;//左子结点public Node leftChild;//右子结点public Node rightChild;//构造方法public Node(long data){this.data = data;}
}
package com.fantj.dataStruct.tree;/*** 二叉树* Created by Fant.J.* 2017/12/22 16:11*/
public class Tree {//根结点public Node root;/** 插入结点 */public void insert(long value){//封装结点Node newNode = new Node(value);//引用当前结点Node current = root;//引用父节点Node parent;//如果root为null，也就是第一次插入的时候if (root == null){root = newNode;return;}else {while (true){//父节点指向当前结点parent = current;//如果当前指向的结点数据比插入的要大，则向左走if (current.data > value){current = current.leftChild;if (current == null){parent.leftChild = newNode;return;}}else {//生成一个右子节点，并且赋值为 newNodecurrent = current.rightChild;if (current == null){parent.rightChild = newNode;return;}}}}}/* 查找节点 **/public Node find(long value){//引用当前节点，从根节点开始Node current = root;//循环，只要查找值不等于当前节点值while (current.data != value){//进行比较，比较查找值和当前节点的大小if (current.data > value){current = current.leftChild;}else {current = current.rightChild;}//如果是空，则退出if (current == null){return null;}}return current;}/* 前序遍历 **/public void frontOrder(Node localNode){if (localNode != null){//访问根节点System.out.print(localNode.data+",");//前序遍历左子树frontOrder(localNode.leftChild);//前序遍历右子树frontOrder(localNode.rightChild);}}/* 中序遍历 **/public void inOrder(Node localNode){if (localNode != null){//中序遍历左子树inOrder(localNode.leftChild);//访问根节点System.out.print(localNode.data+",");//中序遍历右子树inOrder(localNode.rightChild);}}/* 后序遍历 **/public void afterOrder(Node localNode){if (localNode != null){//后序遍历左子树afterOrder(localNode.leftChild);//后序遍历右子树afterOrder(localNode.rightChild);//访问根节点System.out.print(localNode.data+",");}}/* 删除结点 **/
}
这里我把删除节点的操作单独拿出来*（因为比较复杂）
/* 删除结点 **/public boolean delete(long value){//引用当前节点，从根节点开始Node current = root;//引用当前节点的父节点Node parent = root;//是否右左子节点boolean isLeftChild = true;while (current.data != value){parent = current;//进行比较，比较value和当前节点if (current.data > value){current = current.leftChild;isLeftChild = true;}else {current = current.rightChild;isLeftChild = false;}//如果查找不到if (current ==null){return false;}}//删除叶子节点，也就是该节点没有子节点if (current.leftChild == null && current.rightChild == null){if (current == root){root = null;}//如果是左子节点if (isLeftChild){parent.leftChild = null;}else {parent.rightChild = null;}}else if (current.rightChild == null){if (current == root){root = current.leftChild;}else if (isLeftChild){parent.leftChild = current.leftChild;}else {parent.rightChild = current.leftChild;}}else if(current.leftChild == null){if (root == current){root = current.rightChild;}if (isLeftChild){parent.leftChild = current.rightChild;}else {parent.rightChild = current.rightChild;}}else {//获取中序后继节点Node succeed = getSucceed(current);if (current == root){root = succeed;}else if (isLeftChild){parent.leftChild = succeed;}succeed.leftChild = current.leftChild;}return true;}/* 找到后继(succeed)节点 , 后继是按照中序先找右子树，然后找左节点**/public Node getSucceed(Node delNode){Node succeed = delNode;Node succeedParent = delNode;Node current = delNode.rightChild;while (current != null){succeedParent = succeed;succeed = current;current = current.leftChild;}if (succeed != delNode.rightChild){succeedParent.leftChild = succeed.rightChild;succeed.rightChild = delNode.rightChild;}return succeed;}
相关文章：
linux驱动：i2c驱动（四）流程图之注册驱动
二、i2c设备的驱动部分 1、i2c驱动i2c_driver 2、通过i2c_add_driver注册 2、注册过程中 比较i2c_device_id数组中各成员的id与i2c_client中的名字，找到设备 3、执行i2c_driver驱动中的probe
Expression Blend实例中文教程(2) - 界面快速入门
上一篇主要介绍Expression系列产品，另外概述了Blend的强大功能，本篇将用Blend 3创建一个新Silverlight项目，通过创建的过程，对Blend进行快速入门学习。 在开始使用Blend前，首先需要进行Silverlight的开发环境搭建&…
Lua基本语法-书写规范以及自带常用函数
Lua基本语法-书写规范和常用函数本文提供全流程，中文翻译。Chinar坚持将简单的生活方式，带给世人！（拥有更好的阅读体验 —— 高分辨率用户请根据需求调整网页缩放比例） 1String Operation —— 字符串操作2Table ——…
linux驱动：音频驱动（一）ALSA
一、【基础知识】 1、J2 《--HPR_OUTHPL_OUT 《-- U13（TLV320AIC3104IRHBR）的HPROUTHPLOUT 2、驱动源码 IPNC_RDK_V3.8.0.1/Source/ti_tools/ipnc_psp_arago/kernel/sound/soc/codecs/tlv320aic3x.c 3、依赖于I2C驱动 4、声卡驱动框架：…
秘籍 | 机器学习数据集网址大全
作者 | Will Badr译者 | Linstancy整理 | Jane出品 | AI科技大本营（ID:rgznai100）要找到一定特定的数据集可以解决各种机器学习问题，是一件很难的事情。越来越多企业或研究机构将自己的数据集公开，已经成为全球的趋势，…
为asa防火墙配置ssh登陆
由于最近事情超多，单位下发某些令人恶心的制度，今天突然说北京分公司和总公司之间要做***的连接，虽然俺是个CCNP，但是对于***来说接触的少之又少，并且工作繁忙，每天头大，北京分公司的安全ie同事…
70.nodejs操作mongodb
转自：https://www.cnblogs.com/whoamme/p/3467374.html 首先安装nodejs mongodb npm install mongodb var mongodb require(mongodb); var server new mongodb.Server(localhost, 27017, {auto_reconnect:true}); var db new mongodb.Db(mydb, server, {saf…
明晚8点公开课 | 用AI给旧时光上色！详解GAN在黑白照片上色中的应用
在改革开放40周年之际，百度联合新华社推出了一个刷屏级的H5应用——用AI技术为黑白老照片上色，浓浓的怀旧风勾起了心底快被遗忘的时光。想了解如何给老照片上色？本次公开课中，我们邀请到了百度高级研发工程师李超，他的…
linux驱动：音频驱动（二）ASoc
五、【ASoC声卡驱动框架】 1、ASoC将嵌入式设备的音频系统从软件层面划分为3个组件 1.1 codec驱动：音频编解码器驱动，与平台无关，实现音频控制项添加、音频接口实现、DAPM（动态音频电源管理）、音频编解码器的IO功能 …
把32位的SharePoint服务器场迁移到64位, 应该怎么做?
总体步骤如下: 1. 迁移已经存在了的数据库服务器到新的数据库服务器. 先迁移这一层的目的是避免可能发生的一些由64位系统对32位系统执行查询或写入操作所引起的性能问题. 2. 迁移WFE服务器到64位环境下. 准备工作: 1. 重新编译已经存在的32位的应用程序和自定义的程序集(web p…
testem方便的web tdd 测试框架使用
备注：单元测试，对于日常的开发是比较重要的，testem 简化了我们的代码编写，以及运行。主要特性：a. 支持的测试框架有：jasmine quint mocha buster.js ，同时也包含一些其他的适配器，支…
linux驱动：音频驱动（三）ASoc之machine驱动及card初始化
一、machine驱动及card初始化
程序员老在改Bug，就不能一次改好吗？
作者丨伍杏玲来源 | 程序人生（ID：coder_life）程序员的日常三件事：写Bug、改Bug、背锅。连程序员都自我调侃道，为什么每天都在加班？因为我的眼里常含Bug。但是真的有这么多Bug要改吗？就不能一次改…
一场库文件的远程修复
一场库文件的远程修复系统环境RHEL 4.7一、原因：发现每天早上7点1分备份的数据库文件时间不对，登录上去后date下发现时间是正确。二、尝试解决：1）setup->Timezone configuration-> Asia/Shanghai保存后，发现由原…
linux驱动：音频驱动（四）ASoc之machine设备
linux驱动：音频驱动（四）ASoc之machine设备
Sql server Insert执行的秘密(下) 带外键的INSERT分析
2019独角兽企业重金招聘Python工程师标准>>> 这一篇分析一下带外键表的INSERT的例子。 本文所用的数据表结构如上图所示；其中Blog表上BlogID是自增的主键，并在CreateUserID和CreateTime列上分别建有两个非唯一索引。 我们要往Blog表中插入一…
熬夜写代码，不如换女装入GitHub获上千Star？
作者 | 琥珀出品 | AI科技大本营（ID: rgznai100）程序员如何以合规手段快速获得 GitHub 上千 Star？新年刚过，GitHub Trending 上一个名为“Dress”的开源项目迅速蹿红，并成功掀起了不少程序员及吃瓜群众的热议。项目地址…
CCNp笔记(EIGRP)
EIGRP<?xml:namespace prefix o ns "urn:schemas-microsoft-com:office:office" />特性1属于混合路由协议具有距离矢量路由协议的特性，又有链路状态路由协议的特性。2属于高级距离矢量路由协议3快速收敛4保证100%无环路5增量更新6支持默认4条最多…
linux驱动：音频驱动（五）ASoc之codec驱动
linux驱动：音频驱动（五）ASoc之codec驱动
科大讯飞市值腰斩背后，AI产业集体思考如何落地?
作者丨郭敏本文经授权转载自钛媒体（ID：taimeiti）【导语】在过去的一年里，科大讯飞受到了多方质疑，质疑的声音不外乎盈利疲软、靠政府补助、技术优势逐渐变弱等，种种质疑背后，其实整个 AI 产业从…
zabbix系列之邮件告警（三）
设置邮件告警有两种方式：1）、通过Linux自带的mail发送告警邮件2）、通过第三方邮箱发送（如QQ邮箱、163邮箱等）告警邮件1、修改 zabbx_server.conf 文件,指定脚本路径，没有则添加[rootcentos1 ~]# vim /usr/l…
Python告诉你：为何年终奖多发一元，到手却少两千多？
作者 | shenzhongqiang来源 | Python数据与分析（ID：ML_Python）年终奖多发一元，到手却要少两千多，甚至更多。听到这个消息的时候，大家是不是觉得有点意外，意外之余还有点淡淡的忧伤？上…
[译]一个系统管理员眼中的DevOps
前言 原文发表在Patrick Debois大神的官网上，传送门>> 通篇围绕运维工作进行阐述，始终是在强调运维人员和开发人员需要通力协作，这大概也是DevOps理念的核心价值所在吧！大概是因为作者来自比利时吧！翻译的时候还…
linux驱动：音频驱动（六）ASoc之codec设备
linux驱动：音频驱动（六）ASoc之codec设备
屏蔽“网页上有错误”提示，屏蔽java script 错误的代码
<script>window.onerrorhide_error_message;functionhide_error_message(){returntrue;}</script>代码再简写一点，就是： <script type"text/java script ">window.onerrorfunction(){returntrue;}</script >原来只要让…
linux驱动：音频驱动（七）交叉编译alsa库及工具集alsa-utils
0、编译时用到的库 libunistring0_0.9.3-5_i386.deb libgettextpo0_0.18.1.1-5ubuntu3_i386.deb gettext_0.18.1.1-5ubuntu3_i386.deb 1、下载源码 alsa-lib-1.0.27.tar.bz2 alsa-utils-1.0.27.2.tar.bz2 一、交叉编译alsa lib 1、su 进入root用户 2、进入/home/MY/evm-lin…
Python一键转Java？“Google翻译”你别闹
作者 | 若名出品 | AI科技大本营（ID:rgznai100）近日，Reddit 上有网友放出了一张疑似 Google 翻译添加了能让编程语言间互相转换的图片，立即引发数千名程序员网友的跟帖热议。图片显示，Google 翻译中添加了编程语言进行…
我所感兴趣的iOS10新特性
###SiriKit Siri API 的开放自然是 iOS 10 SDK 中最激动人心也是亮眼的特性。SiriKit 为我们提供一全套从语音识别到代码处理，最后向用户展示结果的流程。Apple 加入了一套全新的框架 Intents.framework 来表示 Siri 获取并解析的结果。你的应用需要提供一些关键字表…
如何将三万行代码从Flow移植到TypeScript？
作者 | David Gomes译者 | 弯月责编 | 郭芮来源 | CSDN（ID：CSDNnews）【编者按】在内存安全中，类型安全是很重要的一个命题。为了确保JavaScript项目运行的类型安全，本文的作者介绍了2016年时使用Flow的经历࿱…
CRM——插件流程回顾
1. Django项目启动 自动加载文件 制作启动文件1. 注册strak 在apps.py 类里面增加如下 def ready(self):from django.utils.module_loading import autodiscover_modulesautodiscover_modules("stark")2. 在已经注册的app中创建stark.py文件 加载2. 在stark中模仿Adm…