Java 实现二叉搜索树的查找、插入、删除、遍历

由于最近想要阅读下JDK1.8 中HashMap的具体实现,但是由于HashMap的实现中用到了红黑树,所以我觉得有必要先复习下红黑树的相关知识,所以写下这篇随笔备忘,有不对的地方请指出~

学习红黑树,我觉得有必要从二叉搜索树开始学起,本篇随笔就主要介绍Java实现二叉搜索树的查找、插入、删除、遍历等内容。

二叉搜索树需满足以下四个条件:

若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

任意节点的左、右子树也分别为二叉查找树;

没有键值相等的节点。

二叉搜索树举例:

图一

接下来将基于图一介绍二叉搜索树相关操作。

首先,应先有一个节点对象相关的类,命名为 Node。

class Node {
 int key;
 int value;
 Node leftChild;
 Node rightChild;
 public Node(int key, int value) {
 this.key = key;
 this.value = value;
 }
 public void displayNode() {
 }
}

Node 类中包含 key 值,用于确定节点在树中相应位置,value 值代表要存储的内容,还含有指向左右孩子节点的两个引用。

接下来看下搜索树相应的类:

class Tree {
 Node root;//保存树的根
 public Node find(int key) {//查找指定节点
 }
 public void insert(int key, int value) {//插入节点
 }
 public boolean delete(int key) {//删除指定节点
 }
 private Node getDirectPostNode(Node delNode) {//得到待删除节点的直接后继节点
 }
 public void preOrder(Node rootNode) {//先序遍历树
 }
 public void inOrder(Node rootNode) {//中序遍历树
 }
 public void postOrder(Node rootNode) {//后序遍历树
 }
}

类中表示树的框架,包含查找、插入、遍历、删除相应方法,其中删除节点操作最为复杂,接下来一一介绍。

一、查找某个节点

由于二叉搜索树定义上的特殊性,只需根据输入的 key 值从根开始进行比较,若小于根的 key 值,则与根的左子树比较,大于根的key值与根的右子树比较,以此类推,找到则返回相应节点,否则返回 null。

public Node find(int key) {
 Node currentNode = root;
 while (currentNode != null && currentNode.key != key) {
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 } else {
 currentNode = currentNode.rightChild;
 }
 }
 return currentNode;
}

二、插入节点

与查找操作相似,由于二叉搜索树的特殊性,待插入的节点也需要从根节点开始进行比较,小于根节点则与根节点左子树比较,反之则与右子树比较,直到左子树为空或右子树为空,则插入到相应为空的位置,在比较的过程中要注意保存父节点的信息 及 待插入的位置是父节点的左子树还是右子树,才能插入到正确的位置。

public void insert(int key, int value) {
 if (root == null) {
 root = new Node(key, value);
 return;
 }
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 Node newNode = new Node(key, value);
 if (isLeftChild) {
 parentNode.leftChild = newNode;
 } else {
 parentNode.rightChild = newNode;
 }
}

三、遍历二叉搜索树

遍历操作与遍历普通二叉树操作完全相同,不赘述。

public void preOrder(Node rootNode) {
 if (rootNode != null) {
 System.out.println(rootNode.key + " " + rootNode.value);
 preOrder(rootNode.leftChild);
 preOrder(rootNode.rightChild);
 }
 }
public void inOrder(Node rootNode) {
 if (rootNode != null) {
 inOrder(rootNode.leftChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 inOrder(rootNode.rightChild);
 }
 }
public void postOrder(Node rootNode) {
 if (rootNode != null) {
 postOrder(rootNode.leftChild);
 postOrder(rootNode.rightChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 }
 }

四、删除指定节点。

在二叉搜索树中删除节点操作较复杂,可分为以下三种情况。

1、待删除的节点为叶子节点,可直接删除。

public boolean delete(int key) {
 Node currentNode = root;//用来保存待删除节点
 Node parentNode = root;//用来保存待删除节点的父亲节点
 boolean isLeftChild = true;//用来确定待删除节点是父亲节点的左孩子还是右孩子
 while (currentNode != null && currentNode.key != key) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 if (currentNode == null) {
 return false;
 }
 if (currentNode.leftChild == null && currentNode.rightChild == null) {//要删除的节点为叶子节点
 if (currentNode == root)
 root = null;
 else if (isLeftChild)
 parentNode.leftChild = null;
 else
 parentNode.rightChild = null;
 }
 ......
 }

2、待删除节点只有一个孩子节点

例如删除图一中的 key 值为 11 的节点,只需将 key 值为 13 的节点的左孩子指向 key 值为 12的节点即可达到删除 key 值为 11 的节点的目的。

由以上分析可得代码如下(接上述 delete 方法省略号后):

else if (currentNode.rightChild == null) {//要删除的节点只有左孩子
 if (currentNode == root)
 root = currentNode.leftChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.leftChild;
 else
 parentNode.rightChild = currentNode.leftChild;
 } else if (currentNode.leftChild == null) {//要删除的节点只有右孩子
 if (currentNode == root)
 root = currentNode.rightChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.rightChild;
 else
 parentNode.rightChild = currentNode.rightChild;
 }
 ......

3、待删除节点既有左孩子,又有右孩子。

例如删除图一中 key 值为 10 的节点,这时就需要用 key 值为 10 的节点的中序后继节点(节点 11)来代替 key 值为 10 的节点,并删除 key 值为 10 的节点的中序后继节点,由中序遍历相关规则可知, key 值为 10 的节点的直接中序后继节点一定是其右子树中 key 值最小的节点,所以此中序后继节点一定不含子节点或者只含有一个右孩子,删除此中序后继节点就属于上述 1,2 所述情况。图一中 key 值为 10 的节点的直接中序后继节点 为 11,节点 11 含有一个右孩子 12。

所以删除 图一中 key 值为 10 的节点分为以下几步:

a、找到 key 值为 10 的节点的直接中序后继节点(即其右子树中值最小的节点 11),并删除此直接中序后继节点。

private Node getDirectPostNode(Node delNode) {//方法作用为得到待删除节点的直接后继节点
 Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
 Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
 Node currentNode = delNode.rightChild;
 while (currentNode != null) {
 parentNode = direcrPostNode;
 direcrPostNode = currentNode;
 currentNode = currentNode.leftChild;
 }
 if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
 parentNode.leftChild = direcrPostNode.rightChild;
 direcrPostNode.rightChild = null;
 }
 return direcrPostNode;//返回此直接后继节点
}

b、将此后继节点的 key、value 值赋给待删除节点的 key,value值。(接情况二中省略号代码之后)

else { //要删除的节点既有左孩子又有右孩子
 //思路:用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
 //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
}

至此删除指定节点的操作结束。

最后给出完整代码及简单测试代码及测试结果:

class Node {
 int key;
 int value;
 Node leftChild;
 Node rightChild;
 public Node(int key, int value) {
 this.key = key;
 this.value = value;
 }
 public void displayNode() {
 }
}
class Tree {
 Node root;
 public Node find(int key) {
 Node currentNode = root;
 while (currentNode != null && currentNode.key != key) {
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 } else {
 currentNode = currentNode.rightChild;
 }
 }
 return currentNode;
 }
 public void insert(int key, int value) {
 if (root == null) {
 root = new Node(key, value);
 return;
 }
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 Node newNode = new Node(key, value);
 if (isLeftChild) {
 parentNode.leftChild = newNode;
 } else {
 parentNode.rightChild = newNode;
 }
 }
 public boolean delete(int key) {
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null && currentNode.key != key) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 if (currentNode == null) {
 return false;
 }
 if (currentNode.leftChild == null && currentNode.rightChild == null) {
 //要删除的节点为叶子节点
 if (currentNode == root)
 root = null;
 else if (isLeftChild)
 parentNode.leftChild = null;
 else
 parentNode.rightChild = null;
 } else if (currentNode.rightChild == null) {//要删除的节点只有左孩子
 if (currentNode == root)
 root = currentNode.leftChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.leftChild;
 else
 parentNode.rightChild = currentNode.leftChild;
 } else if (currentNode.leftChild == null) {//要删除的节点只有右孩子
 if (currentNode == root)
 root = currentNode.rightChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.rightChild;
 else
 parentNode.rightChild = currentNode.rightChild;
 } else { //要删除的节点既有左孩子又有右孩子
 //思路:用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
 //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
 }
 return true;
 }
 private Node getDirectPostNode(Node delNode) {//方法作用为得到待删除节点的直接后继节点
 Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
 Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
 Node currentNode = delNode.rightChild;
 while (currentNode != null) {
 parentNode = direcrPostNode;
 direcrPostNode = currentNode;
 currentNode = currentNode.leftChild;
 }
 if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
 parentNode.leftChild = direcrPostNode.rightChild;
 direcrPostNode.rightChild = null;
 }
 return direcrPostNode;//返回此直接后继节点
 }
 public void preOrder(Node rootNode) {
 if (rootNode != null) {
 System.out.println(rootNode.key + " " + rootNode.value);
 preOrder(rootNode.leftChild);
 preOrder(rootNode.rightChild);
 }
 }
 public void inOrder(Node rootNode) {
 if (rootNode != null) {
 inOrder(rootNode.leftChild);
 System.out.println("key: " + rootNode.key + " " + "value: " + rootNode.value);
 inOrder(rootNode.rightChild);
 }
 }
 public void postOrder(Node rootNode) {
 if (rootNode != null) {
 postOrder(rootNode.leftChild);
 postOrder(rootNode.rightChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 }
 }
}
public class BinarySearchTreeApp {
 public static void main(String[] args) {
 Tree tree = new Tree();
 tree.insert(6, 6);//插入操作,构造图一所示的二叉树
 tree.insert(3, 3);
 tree.insert(14, 14);
 tree.insert(16, 16);
 tree.insert(10, 10);
 tree.insert(9, 9);
 tree.insert(13, 13);
 tree.insert(11, 11);
 tree.insert(12, 12);
 System.out.println("删除前遍历结果");
 tree.inOrder(tree.root);//中序遍历操作
 System.out.println("删除节点10之后遍历结果");
 tree.delete(10);//删除操作
 tree.inOrder(tree.root);
 }
}

测试结果:

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持我们!

(0)

相关推荐

  • JAVA 实现二叉树(链式存储结构)

    二叉树的分类(按存储结构) 树的分类(按存储结构) 顺序存储(用数组表示(静态二叉树))   链式存储 一些特别的二叉根: 完全二叉树,平衡二叉树(AVL),线索二叉树,三叉的(带父亲的指针)    二叉搜索树或者叫二叉 查找树(BST)  所用二叉树如下图所示: 二叉树的Java实现(链式存储结构) class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false

  • 图解二叉树的三种遍历方式及java实现代码

    二叉树(binary tree)是一颗树,其中每个节点都不能有多于两个的儿子. 1.二叉树节点 作为图的特殊形式,二叉树的基本组成单元是节点与边:作为数据结构,其基本的组成实体是二叉树节点(binary tree node),而边则对应于节点之间的相互引用. 如下,给出了二叉树节点的数据结构图示和相关代码: // 定义节点类: private static class BinNode { private Object element; private BinNode lChild;// 定义指向

  • Java基于二叉查找树实现排序功能示例

    本文实例讲述了Java基于二叉查找树实现排序功能.分享给大家供大家参考,具体如下: /** * 无论排序的对象是什么,都要实现Comparable接口 * * @param <T> */ public class BinaryNode<T extends Comparable<T>> { private static int index = 0; // 排序下标 private static int len = 0; // 最大数组长度 private T t; //

  • java二叉查找树的实现代码

    本文实例为大家分享了java二叉查找树的具体代码,供大家参考,具体内容如下 package 查找; import edu.princeton.cs.algs4.Queue; import edu.princeton.cs.algs4.StdOut; public class BST<Key extends Comparable<Key>, Value> { private class Node { private Key key; // 键 private Value value;

  • 详解Java二叉排序树

    一.二叉排序树定义 1.二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree).其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树: ①若它的左子树非空,则左子树上所有结点的值均小于根结点的值: ②若它的右子树非空,则右子树上所有结点的值均大于根结点的值: ③左.右子树本身又各是一棵二叉排序树. 上述性质简称二叉排序树性质(BST性质),故二叉排序树实际上是满足BST性质的二叉树. 2.二叉排序树的性质 按中序遍历二

  • java 二叉查找树实例代码

    java 二叉查找树实例代码 1.左边<中间<右边 2.前序遍历 左中右 3.中序遍历 中左右 4.后序遍历 左右中 public class BinaryTree { // 二叉树的根节点 public TreeNode rootNode ; // 记录搜索深度 public int count; /** * 利用传入一个数组来建立二叉树 */ public BinaryTree(int[] data) { for (int i = 0; i < data. length; i++)

  • Java实现求二叉树的深度和宽度

    这个是常见的对二叉树的操作.总结一下: 设节点的数据结构,如下: 复制代码 代码如下: class TreeNode {     char val;     TreeNode left = null;     TreeNode right = null; TreeNode(char _val) {         this.val = _val;     } } 1.二叉树深度 这个可以使用递归,分别求出左子树的深度.右子树的深度,两个深度的较大值+1即可. 复制代码 代码如下: // 获取最大

  • java实现二叉树的创建及5种遍历方法(总结)

    用java实现的数组创建二叉树以及递归先序遍历,递归中序遍历,递归后序遍历,非递归前序遍历,非递归中序遍历,非递归后序遍历,深度优先遍历,广度优先遍历8种遍历方式: package myTest; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Stack; public class myClass { public static void main(

  • java使用归并删除法删除二叉树中节点的方法

    本文实例讲述了java使用归并删除法删除二叉树中节点的方法.分享给大家供大家参考.具体分析如下: 实现的思想很简单: first:找到要删除的节点 second:如果删除的节点没有右子树那么左子树链到父节点 third:如果删除的节点没有左子树那么右子树链到父节点 forth:如果删除的节点又左右孩子,那么可以归并删除节点后的子树:方法有两种一种是用删除节点的左子树的最右节点,指向删除节点的右子树,另一种是用删除节点的用字数的最左节点指向删除节点的左子树. Java 实现如下: public v

  • 图解红黑树及Java进行红黑二叉树遍历的方法

    红黑树 红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树,也是技术面试中经常被问到的树,然而无论是书上还是网上的资料,通常都比较刻板难以理解,能不能一种比较直观的方式来理解红黑树呢?本文将以图形的方式来解释红黑树的插入与删除操作. 对树结构的学习是一个递进的过程,我们通常所接触的树都是二叉树,二叉树简单来说就是每个非叶子节点都有且只有两个孩子,分别叫做左孩子和右孩子.二叉树中有一类特殊的树叫二叉查找树,二叉查找树是一种有序的树,对于每个非叶子节点,其左子树的值都小于它,其右子树的值都大于

  • Java的二叉树排序以及遍历文件展示文本格式的文件树

    Java二叉树排序算法 排序二叉树的描述也是一个递归的描述, 所以排序二叉树的构造自然也用递归的: 排序二叉树的3个特征: 1:当前node的所有左孩子的值都小于当前node的值: 2:当前node的所有右孩子的值都大于当前node的值: 3:孩子节点也满足以上两点 package test.sort; public class BinaryNode { private int value;//current value private BinaryNode lChild;//left chil

  • Java中二叉树数据结构的实现示例

    来看一个具体的习题实践: 题目 根据二叉树前序遍历序列例如:7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#,构建二叉树,并且用前序.中序.后序进行遍历 代码 import java.util.Scanner; public class BinaryTree { public static String[] str; public static int count; /** * 静态内部类,定义二叉树节点 */ static class TreeNode { public Str

随机推荐