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;// 值
    private Node left, right; // 指向子树的链接
    private int n; // 以该节点为根的子树中的节点总数

    public Node(Key key, Value val, int n) {
      this.key = key;
      this.value = val;
      this.n = n;
    }
  }

  private Node root;

  public int size() {
    return size(root);
  }

  private int size(Node x) {
    if (x == null)
      return 0;
    else
      return x.n;
  }

  /**
   * 如果树是空的,则查找未命中 如果被查找的键小于根节点,则在左子树中继续查找 如果被查找的键大于根节点,则在右子树中继续查找
   * 如果被查找的键和根节点的键相等,查找命中
   *
   * @param key
   * @return
   */
  public Value get(Key key) {
    return get(root, key);
  }

  private Value get(Node x, Key key) {
    if (x == null)
      return null;
    int cmp = key.compareTo(x.key);
    if (cmp < 0)
      return get(x.left, key);
    else if (cmp > 0)
      return get(x.right, key);
    else
      return x.value;
  }

  /**
   * 二叉查找树的一个很重要的特性就是插入的实现难度和查找差不多。 当查找到一个不存在与树中的节点(null)时,new 新节点,并将上一路径指向该节点
   *
   * @param key
   * @param val
   */
  public void put(Key key, Value val) {
    root = put(root, key, val);
  }

  private Node put(Node x, Key key, Value val) {
    if (x == null)
      return new Node(key, val, 1);
    int cmp = key.compareTo(x.key);
    if (cmp < 0)
      x.left = put(x.left, key, val);
    else if (cmp > 0)
      x.right = put(x.right, key, val);
    else
      x.value = val;
    x.n = size(x.left) + size(x.right); // 要及时更新节点的子树数量
    return x;
  }

  public Key min() {
    return min(root).key;
  }

  private Node min(Node x) {
    if (x.left == null)
      return x;
    return min(x.left);
  }

  public Key max() {
    return max(root).key;
  }

  private Node max(Node x) {
    if (x.right == null)
      return x;
    return min(x.right);
  }

  /**
   * 向下取整:找出小于等于该键的最大键
   *
   * @param key
   * @return
   */
  public Key floor(Key key) {
    Node x = floor(root, key);
    if (x == null)
      return null;
    else
      return x.key;
  }

  /**
   * 如果给定的键key小于二叉查找树的根节点的键,那么小于等于key的最大键一定出现在根节点的左子树中
   * 如果给定的键key大于二叉查找树的根节点,那么只有当根节点右子树中存在大于等于key的节点时,
   * 小于等于key的最大键才会出现在右子树中,否则根节点就是小于等于key的最大键
   *
   * @param x
   * @param key
   * @return
   */
  private Node floor(Node x, Key key) {
    if (x == null)
      return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0)
      return x;
    else if (cmp < 0)
      return floor(x.left, key);
    else {
      Node t = floor(x.right, key);
      if (t == null)
        return x;
      else
        return t;
    }
  }

  /**
   * 向上取整:找出大于等于该键的最小键
   *
   * @param key
   * @return
   */
  public Key ceiling(Key key) {
    Node x = ceiling(root, key);
    if (x == null)
      return null;
    else
      return x.key;
  }

  /**
   * 如果给定的键key大于二叉查找树的根节点的键,那么大于等于key的最小键一定出现在根节点的右子树中
   * 如果给定的键key小于二叉查找树的根节点,那么只有当根节点左子树中存在大于等于key的节点时,
   * 大于等于key的最小键才会出现在左子树中,否则根节点就是大于等于key的最小键
   *
   * @param x
   * @param key
   * @return
   */
  private Node ceiling(Node x, Key key) {
    if (x == null)
      return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0)
      return x;
    else if (cmp > 0) {
      return ceiling(x.right, key);
    } else {
      Node t = floor(x.left, key);
      if (t == null)
        return x;
      else
        return t;
    }
  }

  /**
   * 选择排名为k的节点
   *
   * @param k
   * @return
   */
  public Key select(int k) {
    return select(root, k).key;
  }

  private Node select(Node x, int k) {
    if (x == null)
      return null;
    int t = size(x.left);
    if (t > k)
      return select(x.left, k);
    else if (t < k)
      return select(x.right, k - t - 1);// 根节点也要排除掉
    else
      return x;
  }

  /**
   * 查找给定键值的排名
   *
   * @param key
   * @return
   */
  public int rank(Key key) {
    return rank(key, root);
  }

  private int rank(Key key, Node x) {
    if (x == null)
      return 0;
    int cmp = key.compareTo(x.key);
    if (cmp < 0)
      return rank(key, x.left);
    else if (cmp > 0)
      return 1 + size(x.left) + rank(key, x.right);
    else
      return size(x.left);
  }
  /**
   * 删除最小键值对
   */
  public void deleteMin(){
    root = deleteMin(root);
  }
  /**
   * 不断深入根节点的左子树直到遇见一个空链接,然后将指向该节点的链接指向该结点的右子树
   * 此时已经没有任何链接指向要被删除的结点,因此它会被垃圾收集器清理掉
   * @param x
   * @return
   */
  private Node deleteMin(Node x){
    if(x.left == null) return x.right;
    x.left = deleteMin(x.left);
    x.n = size(x.left)+size(x.right) + 1;
    return x;
  }

  public void deleteMax(){
    root = deleteMax(root);
  }
  private Node deleteMax(Node x){
    if(x.right == null ) return x.left;
    x.right = deleteMax(x.right);
    x.n = size(x.left)+size(x.right) + 1;
    return x;
  }

  public void delete(Key key){
    root = delete(root,key);
  }
  private Node delete(Node x, Key key){
    if(x == null) return null;
    int cmp = key.compareTo(x.key);
    if(cmp < 0) x.left = delete(x.left,key);
    else if(cmp > 0) x.right = delete(x.right,key);
    else{
      if(x.right == null) return x.left;
      if(x.left == null ) return x.right;
      /**
       * 如果被删除节点有两个子树,将被删除节点暂记为t
       * 从t的右子树中选取最小的节点x,将这个节点x的左子树设为t的左子树
       * 这个节点x的右子树设为t的右子树中删除了最小节点的子树,这样就成功替换了t的位置
       */
      Node t = x;
      x = min(t.right);
      x.left = t.left;
      x.right = deleteMin(t.right);
    }
    x.n = size(x.left) + size(x.right) +1;
    return x;
  }

  public void print(){
    print(root);
  }
  private void print(Node x){
    if(x == null ) return;
    print(x.left);
    StdOut.println(x.key);
    print(x.right);
  }

  public Iterable<Key> keys(){
    return keys(min(),max());
  }
  public Iterable<Key> keys(Key lo, Key hi){
    Queue<Key> queue = new Queue<Key>();
    keys(root, queue, lo, hi);
    return queue;
  }
  private void keys(Node x, Queue<Key> queue, Key lo, Key hi){
    if(x == null) return;
    int cmplo = lo.compareTo(x.key);
    int cmphi = lo.compareTo(x.key);
    if(cmplo < 0 ) keys(x.left,queue,lo,hi);
    if(cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key);
    if(cmphi > 0 ) keys(x.right,queue,lo,hi);
  }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

时间: 2017-08-08

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

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

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

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二叉排序树

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

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

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

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

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

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 二叉查找树实例代码 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 实现二叉树(链式存储结构)

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

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 实现二叉搜索树的查找、插入、删除、遍历

由于最近想要阅读下JDK1.8 中HashMap的具体实现,但是由于HashMap的实现中用到了红黑树,所以我觉得有必要先复习下红黑树的相关知识,所以写下这篇随笔备忘,有不对的地方请指出- 学习红黑树,我觉得有必要从二叉搜索树开始学起,本篇随笔就主要介绍Java实现二叉搜索树的查找.插入.删除.遍历等内容. 二叉搜索树需满足以下四个条件: 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值: 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值: 任意节点的左.右子

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

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

C语言二叉树的三种遍历方式的实现及原理

二叉树遍历分为三种:前序.中序.后序,其中序遍历最为重要.为啥叫这个名字?是根据根节点的顺序命名的. 比如上图正常的一个满节点,A:根节点.B:左节点.C:右节点,前序顺序是ABC(根节点排最先,然后同级先左后右):中序顺序是BAC(先左后根最后右):后序顺序是BCA(先左后右最后根). 比如上图二叉树遍历结果 前序遍历:ABCDEFGHK 中序遍历:BDCAEHGKF 后序遍历:DCBHKGFEA 分析中序遍历如下图,中序比较重要(java很多树排序是基于中序,后面讲解分析) 下面介绍一下,二

对python For 循环的三种遍历方式解析

实例如下所示: array = ["a","b","c"] for item in array: print(item) for index in range(len(array)): print(str(index)+".."+array[index]) for index,val in enumerate(array): print(str(index)+"--"+val); 打印结果 a b c 0.

Python三种遍历文件目录的方法实例代码

本文实例代码主要实现的是python遍历文件目录的操作,有三种方法,具体代码如下. #coding:utf-8 # 方法1:递归遍历目录 import os def visitDir(path): li = os.listdir(path) for p in li: pathname = os.path.join(path,p) if not os.path.isfile(pathname): #判断路径是否为文件,如果不是继续遍历 visitDir(pathname) else: print

SpringMVC上传文件的三种实现方式

SpringMVC上传文件的三种实现方式,直接上代码吧,大伙一看便知 前台: <%@ page language="java" contentType="text/html; charset=utf-8" pageEncoding="utf-8"%> <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.

Python 二叉树的层序建立与三种遍历实现详解

前言 二叉树(Binary Tree)时数据结构中一个非常重要的结构,其具有....(此处省略好多字)....等的优良特点. 之前在刷LeetCode的时候把有关树的题目全部跳过了,(ORZ:我这种连数据结构都不会的人刷j8Leetcode啊!!!) 所以 !!!敲黑板了!!!今天我就在B站看了数据结构中关于树的内容后,又用我浅薄的Python大法来实现一些树的建立和遍历. 关于树的建立我觉得层序建立对于使用者来说最为直观,输入很好写.(好吧,我是看LeetCode中的树输入都是采用层序输入觉得

Python实现重建二叉树的三种方法详解

本文实例讲述了Python实现重建二叉树的三种方法.分享给大家供大家参考,具体如下: 学习算法中,探寻重建二叉树的方法: 用input 前序遍历顺序输入字符重建 前序遍历顺序字符串递归解析重建 前序遍历顺序字符串堆栈解析重建 如果懒得去看后面的内容,可以直接点击此处本站下载完整实例代码. 思路 学习算法中,python 算法方面的资料相对较少,二叉树解析重建更少,只能摸着石头过河. 通过不同方式遍历二叉树,可以得出不同节点的排序.那么,在已知节点排序的前提下,通过某种遍历方式,可以将排序进行解析

Map集合的四种遍历方式代码示例

很久以前写的代码,和上一个做比较吧!便于以后查看. import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class TestMap { public static void main(String[] args) { Map<Integer, String> map = new HashMap<Integer, String>(); map.put(1, "a&

Android XML数据的三种解析方式

本篇文章包含以下内容: XML数据的Dom解析      XML数据的Sax解析      XML数据的Pull解析      Activity中使用三种解析      Sax解析与Pull解析区别 三种解析方式的步骤: 1.在Assets文件夹中模拟创建XML数据 2.创建对应XML的Bean对象 3.开始解析 XML数据的Dom解析 DOM解析XML文件时,会将XML文件的所有内容读取到内存中(内存的消耗比较大),然后允许您使用DOM API遍历XML树.检索所需的数据 一.在Assets文

oracle中if/else的三种实现方式详解

1.标准sql规范 1.单个IF IF v=... THEN END IF; 2.IF ... ELSE IF v=... THEN ELSE t....; END IF; 3.多个IF IF v=... THEN ELSIF v=... THEN t...; END IFL 注意: 多个IF的是'ELSIF' 不是 ' ELSE IF' 2.decode函数 DECODE(VALUE,IF1,THEN1,IF2,THEN2,IF2,THEN2,..,ELSE) 表示如果value等于if1时,