Java实现二叉树-知识学堂

二叉树的定义
树（tree）是一种抽象数据类型（ADT），用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点通过连接它们的边组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的树。

二叉树是一种特殊的树，每个节点最多只能有两个子节点。（如图1.1）

二叉搜索树要求：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树

二叉树1.1
二叉搜索树作为一种数据结构，那么它是如何工作的呢？它查找一个节点，插入一个新节点，以及删除一个节点，遍历树等工作效率如何，下面我们来一一介绍

二叉树节点类（节点一般存储是对象，这里为了方便演示用的是int）
/**
* 二叉树节点
*/
public class Node {

public int data;

public Node leftNode;

public Node rightNode;

public Node(int key) {
data = key;
}

}
准备实现的几个方法
/**
* 二叉树
*
* @author hh
*/
public abstract class AbstractTree {

public int count = 0;

/**
* 查询
*
* @return
*/
public abstract Node find(int o);

/**
* 插入
*
* @param o
*/
public abstract boolean insert(int o);

/**
* 删除
*
* @param o
*/
public abstract boolean delete(int o);

/**
* 节点个数
*
* @return
*/
public int count() {
return this.count;
}
}
查找节点
查找节点从根节点开始遍历查找

1 、查找值比当前节点值大，则搜索右子树；

2、查找值等于当前节点值，停止搜索（终止条件）；

3、查找值小于当前节点值，则搜索左子树；

public Node find(int key) {
Node current = root;
while (current != null) {
if (current.data > key) {
//当前值比查找值大则继续遍历左子树
current = current.leftNode;
} else if (current.data < key) {
//当前值小于查找值则继续遍历右子树
current = current.rightNode;
} else {
//查找到返回
return current;
}
}
//查不到返回null
return null;
}
插入节点
要插入节点，必须先找到插入的位置。与查找操作相似，由于二叉搜索树的特殊性，待插入的节点也需要从根节点开始进行比较，小于根节点则与根节点左子树比较，反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置，在比较的过程中要注意保存父节点的信息及待插入的位置是父节点的左子树还是右子树，才能插入到正确的位置

public boolean insert(int data) {
count++;
//如果第一个节点为空设置第一个节点
Node newNode = new Node(data);
if (root == null) {
root = newNode;
return true;
}
Node current = root;
Node parentNode = null;

while (current != null) {
parentNode = current;
//当前值比新插入值大
if (current.data > data) {
current = current.leftNode;
//若左节点为空则直接插入即可
if (current == null) {
parentNode.leftNode = newNode;
return true;
}
} else {
//当前值小于新插入值
current = current.rightNode;
if (current == null) {
parentNode.rightNode = newNode;
return true;
}
}
}
return false;
}
删除节点
删除节点相对于查询和删除稍微复杂点，主要是删除时考虑的情况多一点点。

1、删除节点没有子节点

2、删除节点有一个子节点

3、删除节点有两个子节点

（1）删除节点没有子节点
这种的话就直接删除当前节点就好了，只需讲当前节点的父节点指向的右节点置为null即可

(2)删除节点有一个子节点
删除有一个子节点的节点，我们只需要将其父节点原本指向该节点的引用，改为指向该节点的子节点即可。

（3）删除节点有两个子节点
当删除的节点存在两个子节点，那么删除之后，两个子节点的位置我们就没办法处理了。既然处理不了，我们就想到一种办法，用另一个节点来代替被删除的节点，那么用哪一个节点来代替呢？

这实际上就是要找比删除节点关键值大的节点集合中最小的一个节点，只有这样代替删除节点后才能满足二叉搜索树的特性。

删除节点有两个子节点的情况
删除代码如下

/**
* 删除共三种情况
* 1 该节点是叶子节点
* 2 该节点有一个叶子节点
* 3 该节点有两个叶子节点
*
* @param data
*/
@Override
public boolean delete(int data) {
Node current = root;
Node parentNode = root;
//当前节点是否为左节点
boolean isLeftNode = false;

//定位data的位置
while (current.data != data) {
parentNode = current;
if (current.data > data) {
isLeftNode = true;
current = current.leftNode;
} else {
isLeftNode = false;
current = current.rightNode;
}

if (current == null) {
return false;
}
}
// 1 第一种情况此节点为叶子节点
if (current.leftNode == null && current.rightNode == null) {
if (current == root) {
root = null;
} else if (isLeftNode) {
//如果要删除的节点为父节点的左节点把父节点的左节点置为空
parentNode.leftNode = null;
} else {
parentNode.rightNode = null;
}
return true;
}
//2 当前节点有一个节点
if (current.leftNode == null && current.rightNode != null) {
if (root == current) {
root = current.rightNode;
} else if (isLeftNode) {
parentNode.leftNode = current.rightNode;
} else {
parentNode.rightNode = current.rightNode;
}
} else if (current.leftNode != null && current.rightNode == null) {
if (root == current) {
root = current.leftNode;
} else if (isLeftNode) {
parentNode.leftNode = current.leftNode;
} else {
parentNode.rightNode = current.leftNode;
}
}

//3 当前节点有两个节点

if(current.leftNode != null && current.rightNode != null){
//获取删除节点的后继结点
Node successor = getSuccessor(current);
if (root == current) {
root = successor;
} else if (isLeftNode) {
parentNode.leftNode = successor;
} else {
parentNode.rightNode = successor;
}
}
return false;
}
/**
* 获取要删除节点的后继节点
*
* @param delNode
* @return
*/
public Node getSuccessor(Node delNode) {

Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightNode;
while (current != null) {
successorParent = successor;
successor = current;
current = current.leftNode;
}
if (successor != delNode.rightNode) {
successorParent.leftNode = successor.rightNode;
successor.rightNode = delNode.rightNode;
}
return successor;
}
完整二叉树实现代码如下

Node类

package com.example.demo.BinaryTree;

/**
* 二叉树节点
*/
public class Node {

public int data;

public Node leftNode;

public Node rightNode;

public Node(int key) {
data = key;
}

}
抽象类AbstractTree

package com.example.demo.BinaryTree;

/**
* 二叉树
*
* @author hh
*/
public abstract class AbstractTree {

public int count = 0;

/**
* 查询
*
* @return
*/
public abstract Node find(int o);

/**
* 插入
*
* @param o
*/
public abstract boolean insert(int o);

/**
* 删除
*
* @param o
*/
public abstract boolean delete(int o);

/**
* 节点个数
*
* @return
*/
public int count() {
return this.count;
}
}
二叉树实现类Tree

package com.example.demo.BinaryTree;

/**
*
*/
public class Tree extends AbstractTree {

private Node root;

@Override
public Node find(int key) {
Node current = root;
while (current != null) {
if (current.data > key) {
current = current.leftNode;
} else if (current.data < key) {
current = current.rightNode;
} else {
return current;
}
}
return null;
}

@Override
public boolean insert(int data) {
count++;
//如果第一个节点为空设置第一个节点
Node newNode = new Node(data);
if (root == null) {
root = newNode;
return true;
}
Node current = root;
Node parentNode = null;

//3 当前节点有两个节点

}
测试类Test

package com.example.demo.BinaryTree;

/**
* Created by HH on 2019/7/2.
*/
public class Test {
public static void main(String[] args) {
Tree t=new Tree();
t.insert(80);
t.insert(70);
t.insert(100);
t.insert(90);
Node node = t.find(100);
System.out.println(node.leftNode.data);
System.out.println(t.count());
}
}
总结：

树是由边和节点构成，根节点是树最顶端的节点，它没有父节点；二叉树中，最多有两个子节点；某个节点的左子树每个节点都比该节点的关键字值小，右子树的每个节点都比该节点的关键字值大，那么这种树称为二叉搜索树，其查找、插入、删除的时间复杂度都为logN；删除一个节点只需要断开指向它的引用即可；

本期内容就到这里啦～以上内容均可在 方包博客「http://fang1688.cn」 网站直接搜索名称访问哦。欢迎感兴趣的小伙伴试试，如果本文对您有帮助，也请帮忙点个 赞 + 在看 啦！❤️

欢迎大家加入方包的「优派编程」学习圈子，和多名小伙伴们一起交流学习，向方包 1 对 1 提问、跟着方包做项目、领取大量编程资源等。Q群「891029429」欢迎想一起学习进步的小伙伴~

另外方包最近开发了一款工具类的小程序「方包工具箱」,功能包括：抖音、小红书、快手去水印，天气预报，小说在线免费阅读（内含上万部热门小说），历史今天，生成图片二维码,图片识别文字，ai伪原创文章，数字摇号抽奖,文字转语音MP3功能...

送福利！关注下方的公众号：「优派编程」回复「资料」，即可获得软件app下载资源和python、java等编程学习资料！

点击卡片关注「优派编程」
定期分享 it编程干货

‍‍‍ ⬇️ 点击链接阅读原文直达 方包博客

Java实现二叉树

分享到：

Java实现二叉树

相关推荐

评论抢沙发

分类目录

最新文章