文档章节

基本数据结构之BinarySearchTree

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/10/20 14:40
字数 418
阅读 226
收藏 0
点赞 0
评论 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
博文 40
码字总数 14221
作品 0
浦东
程序员
二叉查找树 (Binary Search Tree)

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

ryany
2011/01/27
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
ASN.1编码规则(数据类型)

ASN.1中定义的数据类型既有简单的基本数据类型,也有复杂的结构类型。 基本类型是不可再再分的,包括: 布尔型(BOOLEAN) 整型(INTEGER) 实型(REAL) 位串类型(BITSTRING) 8位位组类型...

DayDayUpCQ
2013/07/05
0
0
C语言/C加加程序员新手入门学习基础之数据类型分享

请点击此处输入图片描述 关注我们 为什么要首先介绍数据类型? 因为(数据结构就是对数据类型的操作)不论是哪一种语言,都要有其基本数据类型,这些基本的数据类型就像一块块砖,而程序中的...

小辰GG
2017/12/30
0
0
Python 基础:数据类型和结构(二)丨数析学院

课程简介 本节为 Python 金融数据分析基础课程,将重点介绍 Python 基本数据类型和数据结构,此外,也对 NumPy 库特有的数据结构进行了说明。建议初学者认真学习本节内容,已经掌握数据结构的...

Datartisan数据工匠
2017/11/28
0
0
【old】博客还是需要写的哦-赋值、拷贝

1)预备知识 1.1)预备知识1--python的变量及其存储 ·python中,变量保存的是对象的引用,我们称之为"引用语义".·采用这种语义,变量需要的内存大小一致,因为变量只是保存了一个引用. 1.2)各基本...

Mx孔小发
2017/12/24
0
0
C语言结构体 Struct

前述 C 语言中,结构体用来存储一组类型不同的数据; 定义 ############################################################################ struct 结构体名{ 结构体中的变量和数组; }; s...

诸葛孔明亮
2016/10/14
3
0
前端你应该了解的数据结构与算法

提到数据结构与算法都感觉这应该是后端要掌握的知识,对前端来说只要写写页面,绑定事件,向后台发发数据就好了,用不到数据结构与算法,也许对于一些数据查找 简单的for循环就能搞定,也许只...

幸福拾荒者
06/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

分布式之抉择分布式锁

前言: 目前网上大部分的基于zookpeer,和redis的分布式锁的文章都不够全面。要么就是特意避开集群的情况,要么就是考虑不全,读者看着还是一脸迷茫。坦白说,这种老题材,很难写出新创意,博...

Java大蜗牛
4分钟前
0
0
rm: cannot remove `xxx’: Operation not permitted

rm: cannot remove `xxx': Operation not permitted可以先用lsattr xxx查看文件的隐藏属性。如果看到-----a-------的情况,可以用chattr -a xxx去除a属性,然后再进行删除就可以了....

殘留回憶
5分钟前
0
0
oracle 如何查看当前用户的表空间名称

如何查询当前用户的表空间名称?因为oracle建立索引,需要知道当前用户的表空间,查找了一下资料 --查询语法-- select default_tablespace from dba_users where username='登录用户' 如,...

youfen
9分钟前
0
0
MicroPython-TPYBoard开发板DIY小型家庭气象站

对于喜欢登山的人来说,都会非常关心自己所处的高度跟温度,海拔高度的测量方法,海拔测量一般常用的有两种方式,一是通过GPS全球定位系统,二是通过测出大气压,根据气压值算出海拔高度。 ...

bodasisiter
9分钟前
0
0
抓取沪A股票资金流向数据

library(rvest)mydata<-list()day1<-Sys.Date()day2<-Sys.Date()-7stock<-c("600695","600734","603693","601990","603650","603045","603895","600735","601999","603970","600619"......

cuyi
9分钟前
0
0
Java中mqtt消息队列发送和订阅消息

1.首先本地建立mqtt协议的服务器 2.直接上代码 package io.powerx.test;import java.util.Date;import org.eclipse.paho.client.mqttv3.IMqttDeliveryToken;import org.eclipse.p......

江湖鱼大虾
11分钟前
0
0
数据结构-树的学习

1. 相关连接 维基-二叉搜索树 维基-红黑树 思否-红黑树

liuyan_lc
13分钟前
0
0
Nginx upstream 负载均衡

Nginx upstream 负载均衡 了了情空 关注 2016.05.31 16:16* 字数 612 阅读 537评论 1喜欢 0 上周五同事跟我提一个需求,大概描述是酱紫:“我们现在终端都在访问同一台服务器,如果流量过大造...

linjin200
14分钟前
0
0
Dubbo 源码解读——自定义 Classloader 之 ExtensionLoader

众所周知,Dubbo 是阿里巴巴公司自主研发开源的一个高性能的服务框架(现已捐献给 Apache 基金会组织),应用之间可以通过 RPC 的方式来互相调用并返回结果。主要基于 Java 语言开发,它提供...

Ryan-瑞恩
22分钟前
0
0
Sonar Maven/IDEA集成(未完待续)

前言:在上一篇(SonarQube安装步骤)的基础上,我们来集成maven/IDEA 1.首先是集成maven(maven的安装配置就不多说了) 找到maven安装目录下-conf文件夹-setting.xml文件 然后添加以下配置信...

张艺兴女朋友
22分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部