文档章节

基本数据结构之BinarySearchTree

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/10/20 14:40
字数 418
阅读 245
收藏 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


关西大汉弹琵琶
粉丝 8
博文 41
码字总数 14221
作品 0
浦东
程序员
私信 提问
加载中
请先登录后再评论。
二叉树和平衡二叉树

先来了解一下二叉搜索树 二叉搜索树和红黑树的对比 二叉搜索树代码实现 红黑树的一些规则

你好-
01/03
7
0
二叉查找树 (Binary Search Tree)

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

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

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

osc_9hgpcg9o
2018/05/01
1
0
算法导论-----------二叉搜索树【转】

转自:https://blog.csdn.net/chenxun_2010/article/details/41709801 先上二叉树查找树的删除的代码,因为删除是二叉查找树最复杂的操作: int BinarySearchTree<T>::tree_remove(const T& ......

osc_q50is30g
2018/07/24
2
0
数据结构与算法——搜索二叉树

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

木兰宿莽
2016/11/05
35
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringCloud 应用在 Kubernetes 上的最佳实践 — 开发篇

作者 | 孤弋 阿里云高级技术专家,负责 EDAS 的开发和用户体验优化工作。 前言 近年来,云原生、Kubernetes、微服务、SpringCloud 这些名词在技术圈内不绝于耳,数据显示,使用 SpringCloud ...

阿里云技术博客
1分钟前
0
0
如何能够高效率学习Web前端技术

  Web前端开发作为前端技术的重要组成,一直占据着重要的地位,整个IT行业内有大量的前端开发从业者,随着移动互联网、大数据和人工智能的发展,目前前端的知识体系也在逐渐丰富。   要想...

SXXpenguin
1分钟前
0
0
Spring Boot 2.3.0正式发布:优雅停机、配置文件位置通配符新特性一览

当大潮退去,才知道谁在裸泳。。关注公众号【BAT的乌托邦】开启专栏式学习,拒绝浅尝辄止。本文 https://www.yourbatman.cn 已收录,里面一并有Spring技术栈、MyBatis、中间件等小而美的专栏...

osc_odp8kgup
2分钟前
0
0
HttpMessageConverter是这样转换数据的

Java Web 人员经常要设计 RESTful API(如何设计好的RESTful API),通过 json 数据进行交互。那么前端传入的 json 数据如何被解析成 Java 对象作为 API入参,API 返回结果又如何将 Java 对象...

tan日拱一兵
2019/05/27
0
0
angular浏览器兼容性问题解决方案

问题:edge浏览器下,固定列的边框消失 原因:ng-zorro-antd表格组件使用nzLeft和nzRight指令固定的表格列,这两个指令的实现css3中的标签: position: -webkit-sticky !important;positio...

osc_elbmybcg
3分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部