文档章节

基本数据结构之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
数据结构与算法——搜索二叉树

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

木兰宿莽
2016/11/05
17
0
用js来实现那些数据结构13(树01-二叉搜索树的实现)

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

zaking
05/01
0
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

没有更多内容

加载失败,请刷新页面

加载更多

09-利用思维导图梳理JavaSE-

09-利用思维导图梳理JavaSE-Java IO流 主要内容 1.Java IO概述 1.1.定义 1.2.输入流 - InputStream 1.3.输出流 - OutputStream 1.4.IO流的分类 1.5.字符流和字节流 2.InputStream类 2.1.File...

飞鱼说编程
29分钟前
1
0
Spring Cloud 微服务的那点事

在详细的了解SpringCloud中所使用的各个组件之前,我们先了解下微服务框架的前世今生。 单体架构 在网站开发的前期,项目面临的流量相对较少,单一应用可以实现我们所需要的功能,从而减少开...

我是你大哥
39分钟前
1
0
步步深入MySQL:架构->查询执行流程->SQL解析顺序

一、前言 一直是想知道一条SQL语句是怎么被执行的,它执行的顺序是怎样的,然后查看总结各方资料,就有了下面这一篇博文了。 本文将从MySQL总体架构--->查询执行流程--->语句执行顺序来探讨一...

Java干货分享
53分钟前
1
0
gson1.7.1线程并发导致空指针问题

java.lang.NullPointerExceptionat com.google.gson.FieldAttributes.getAnnotationFromArray(FieldAttributes.java:231)at com.google.gson.FieldAttributes.getAnnotation(FieldAttribut......

东风125
今天
3
0
以太坊RPC接口使用

以太坊RPC接口文档: https://github.com/ethereum/wiki/wiki/JSON-RPC#web3_clientversion 使用方式: 比如我要调用某个合约的balanceOf(address _owner)方法。 因为没有改变合约的状态,所以...

王坤charlie
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部