文档章节

基本数据结构之BinarySearchTree

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/10/20 14:40
字数 418
阅读 227
收藏 0

问题描述: 

BinarySearchTree


问题分析: 

基本的实现


代码实现:

package c04;
/**
 * @project: DataStructureAndAlgorithmAnalysis
 * @filename: BinarySearchTree.java
 * @version: 0.10
 * @author: JM Han
 * @date: 18:38 2015/10/19
 * @comment: Test Purpose
 * @result:
 */

import c02.BinarySearch;
import master.UnderflowException;
import java.util.Comparator;
import static tool.util.*;

public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
   private static class BinaryNode<AnyType>{
      BinaryNode(AnyType theElement)
      {this(theElement, null, null);}

      BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt)
      {element = theElement; left = lt; right = rt;}

      AnyType element;
      BinaryNode<AnyType> left;
      BinaryNode<AnyType> right;
   }

   private BinaryNode<AnyType> root;

   public BinarySearchTree(){
      root = null;
   }

   public void makeEmpty(){
      root = null;
   }

   public boolean isEmpty(){
      return null == root;
   }

   public boolean contains(AnyType x){
      return contains(x, root);
   }

   public AnyType findMin(){
      if(isEmpty())
         throw new UnderflowException();
      return findMin(root).element;
   }

   public AnyType findMax(){
      if(isEmpty())
         throw new UnderflowException();
      return findMax(root).element;
   }

   public void insert(AnyType x){
      root = insert(x, root);
   }

   public void remove(AnyType x){
      root = remove(x, root);
   }

   public void printTree(){
      if(isEmpty())
         System.out.println("Empty Tree");
      else
         printTree(root);
   }

   private boolean contains(AnyType x, BinaryNode<AnyType> t){
      if(t == null)
         return false;

      int comparableResult = x.compareTo(t.element);

      if(comparableResult < 0)
         return contains(x, t.left);
      else if(comparableResult > 0)
         return contains(x, t.right) ;
      else
         return true;
   }
   private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t){
      if(null == t)
         return null;
      else if(t.left == null)
         return t;
      return findMin(t.left);
   }

   private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t){
      if(t != null)
         while(t.right != null)
            t = t.right;
      return t;
   }
   private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t){
      if(null == t)
         return new BinaryNode<AnyType>(x, null, null);
      int compareResult = x.compareTo(t.element);
      if(compareResult < 0)
         t.left = insert(x, t.left);
      else if(compareResult > 0)
         t.right = insert(x, t.right);
      else
         ;
      return t;
   }
   private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t){
      if(null == t)
         return t;
      int compareResult = x.compareTo(t.element);

      if(compareResult < 0)
         t.left = remove(x, t.left);
      else if(compareResult > 0)
         t.right = remove(x, t.right);
      else if(t.left != null && t.right != null){
         t.element = findMin(t.right).element;
         t.right = remove(t.element, t.right);
      }
      else
         t = (t.left != null)?t.left:t.right;
      return t;
   }
   private void printTree(BinaryNode<AnyType> t){
      if(null != t){
         printTree(t.left);
         System.out.println(t.element);
         printTree(t.right);
      }
   }

   public static void main(String[] args) {
      BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
      bst.insert(4);
      bst.insert(3);
      bst.insert(6);
      bst.insert(0);
      bst.insert(2);
      bst.insert(3);
      System.out.println("Contains 3: " + bst.contains(3));
      System.out.println("Max: " + bst.findMax());
      System.out.println("Min: " + bst.findMin());
      bst.remove(3);
      bst.printTree();
   }
}

代码输出:

Contains 3: true
Max: 6
Min: 0
0
2
4
6


© 著作权归作者所有

共有 人打赏支持
关西大汉弹琵琶
粉丝 7
博文 41
码字总数 14221
作品 0
浦东
程序员
私信 提问
二叉查找树 (Binary Search Tree)

今天开始看 数据结构与算法分析C++版本 看到树了 然后写了一下自己的实现, 自己的算法功底太弱了 这对于一个想向底层发展的人来说是难以忍受的,希望 过年之后把这本书看完,加强一下自己的...

ryany
2011/01/27
0
0
用js来实现那些数据结构13(树01-二叉搜索树的实现)

  前一篇文章我们学会了第一个非顺序数据结构hashMap,那么这一篇我们来学学树,包括树的概念和一些相关的术语以及二叉搜索树的实现。唉?为什么不是树的实现,不是二叉树的实现。偏偏是二...

zaking
05/01
0
0
数据结构与算法——搜索二叉树

基础的数据结构一般都会包含插入、删除、查找和修改等几个基本的操作。对于搜索二叉树而言,数据的插入和删除操作都是在叶子结点进行。搜索二叉树主要方便于数据的查找,其查找算法复杂度为O...

木兰宿莽
2016/11/05
17
0
BinarySearchTree

//创建内部类Node,Node代表的就是树节点public static class Node{ int key; Node leftChild; Node rightChild; public Node(int key){ this.key=key; this.leftChild=null; this.rightChil......

此鱼不得水
2016/03/18
34
0
图解:二叉搜索树算法(BST)

摘要: 原创出处:www.bysocket.com 泥瓦匠BYSocket 希望转载,保留摘要,谢谢! “岁月极美,在于它必然的流逝” “春花 秋月 夏日 冬雪” — 三毛 一、树 & 二叉树 树是由节点和边构成,储存...

泥沙砖瓦浆木匠
2016/07/16
73
0

没有更多内容

加载失败,请刷新页面

加载更多

不学无数——SpringBoot入门IV

SpringBoot 1.Profiles Spring Profiles能够在不同的环境中使不同的应用配置生效。@Component和@Configuration两个注解都能够通过@Profiles来标记。下面是例子: @Configuration@Profile("b...

不学无数的程序员
24分钟前
2
0
nginx长连接出现504的解决办法

在http 中添加如下 fastcgi_connect_timeout 300s; fastcgi_send_timeout 300s; fastcgi_read_timeout 300s;...

hansonwong
24分钟前
1
0
记一次 Spring Boot多数据源 循环引用问题

如题,升级了一下mybatis版本后出现循环引用的问题。 具体异常如下 ***************************APPLICATION FAILED TO START***************************Description:The depen...

HeyS1
25分钟前
1
0
MongoDB Could not find host matching read preference { mode: \"primary\" } for set repl_shard1

最近在测试 MongoDB 4.0 分片集群 ,搭建好所有节点后,往mongos添加分片的时候,一直报错 Could not find host matching read preference { mode: \"primary\" } for set ,如下 mongos> sh...

xxj123gogo
29分钟前
1
0
linux安装java1.8

# tar -zxvf jdk-8u144-linux-x64.tar.gz vi /etc/profile export JAVA_HOME="/usr/local/java/jdk1.8.0_144" export CATALINA_HOME="/usr/local/tomcat/apache-tomcat-9.0.0.M22" export PA......

八戒八戒八戒
31分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部