`
jaychang
  • 浏览: 734613 次
  • 性别: Icon_minigender_1
  • 来自: 嘉兴
社区版块
存档分类
最新评论

泛型二叉排序树

阅读更多

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.Stack;

/**
* <p>
* This class is used to store Element that implements the interface of
* Comparable to a Binary Sorted Tree
*
* @param <E>
*            the type of elements stored in the tree
* @author Jay Chang
* @version 1.0, 08/14/09
* @see Iterator
* @see Comparable
* @see Stack
*/
public class SortedBiTree<E extends Comparable<E>> {

/** 内部类,定义二叉排序树的结点 */
private static class SortedBiTreeNode<E> {
   private E element;
   private SortedBiTreeNode<E> lChild;
   private SortedBiTreeNode<E> rChild;

   private SortedBiTreeNode(E element) {
    this.element = element;
    this.lChild = null;
    this.rChild = null;
   }

   public E getelement() {
    return this.element;
   }
}

/** 树根结点 */
private SortedBiTreeNode<E> root;

/** 树的元素个数 */
private int capacity;

public SortedBiTree() {
   this.capacity = 0;
}

/**
* @function 添加一个元素
* @param E类型的元素
* @return 若元素存在返回true,否则返回false
*/
public boolean add(E element) {
   if (this.isExist(element)) {
    return false;
   }
   this.create(element);
   return true;
}

/**
* @function 添加一个集合
* @param Collecton集合且,集合内元素必须是E类型
* @return 若Collection集合的元素没有一个添加成功则返回false,否则返回true
*/
public boolean addAll(Collection<E> c) {
   Iterator<E> it = c.iterator();
   int count = 0;
   while (it.hasNext()) {
    E element = it.next();
    if (!this.isExist(element)) {
     add(element);
     count++;
    }
   }
   return count >= 1 ? true : false;
}

/**
* @function 私有方法,用于协助获得添加元素后的树
* @param E类型的元素
* @return void
*/
private void create(E element) {
   this.root = this.createSortedBiTree(this.root, element);
}

/**
* @function 私有方法,用于协助判断是否存在指定的元素
* @param E类型的元素
* @return 存在返回true, 否则返回false
*/
private boolean isExist(E element) {
   SortedBiTreeNode<E> tempNode = this.root;
   while (tempNode != null) {
    if (tempNode.element.compareTo(element) > 0) {
     tempNode = tempNode.lChild;
    } else if (tempNode.element.compareTo(element) < 0) {
     tempNode = tempNode.rChild;
    } else {
     return true;
    }
   }
   return false;
}

/**
* @function 私有方法用于实现添加一个元素,且遵循二叉排序树原则
* @param SortedBiTreeNode
*            <E>类型的结点
* @param E类型元素
* @return SortedBiTreeNode<E>类型的结点
*/
private SortedBiTreeNode<E> createSortedBiTree(SortedBiTreeNode<E> node,
    E element) {
   if (node == null) {
    node = new SortedBiTreeNode<E>(element);
    this.capacity++;
   }
   if (node.element.compareTo(element) < 0) {
    node.rChild = createSortedBiTree(node.rChild, element);
   } else if (node.element.compareTo(element) > 0) {
    node.lChild = createSortedBiTree(node.lChild, element);
   }
   return node;
}

/**
* @function 判断树是否为空
* @param none
* @return 若为空,返回true,否则返回false
*/
public boolean isEmpty() {
   return this.root == null;
}

/**
* @function 判断是否存在指定元素
* @param E类型元素
* @return 存在返回true,否则返回false
*/
public boolean contains(E element) {
   if (this.isExist(element)) {
    return true;
   } else {
    return false;
   }
}

/**
* @function 判断是否存在指定集合内的所有元素
* @param Collection
*            <E>
* @return 存在返回true,否则返回false
*/
public boolean containsAll(Collection<E> c) {
   if (this.isEmpty())
    return false;
   Iterator<E> it = c.iterator();
   while (it.hasNext()) {
    if (!this.isExist(it.next())) {
     return false;
    }
   }
   return true;
}

/**
* @function 得到E类型元素最小的那个结点的元素,即树的最左下角的元素
* @param none
* @return SortedBiTreeNode<E>类型的结点
*/
public E getMin() {
   if (this.isEmpty())
    return null;
   SortedBiTreeNode<E> tempNode = this.root;
   SortedBiTreeNode<E> pref = null;
   while (tempNode != null) {
    pref = tempNode;
    tempNode = tempNode.lChild;
   }
   return pref.element;
}

/**
* @function 中序遍历后得到有序的E类型数组
* @param none
* @return E类型的数组
*/
public E[] toArray(E[] a) {
   Object[] elements = new Object[this.capacity];
   int count = 0;
   Stack<SortedBiTreeNode<E>> stack = new Stack<SortedBiTreeNode<E>>();
   SortedBiTreeNode<E> pCurrent = this.root;
   while (pCurrent != null || !stack.isEmpty()) {
    if (pCurrent != null) {
     stack.push(pCurrent);
     pCurrent = pCurrent.lChild;
    } else {
     pCurrent = stack.peek().rChild;
     elements[count++] = stack.pop().element;
    }
   }
   return (E[]) Arrays.copyOf(elements, this.capacity, a.getClass());
   // 下面是在ArrayList里找到的返回泛型数组的源代码,可是自己觉得只需要上面一行就够了
   // 首先传进E[] a是肯定需要的,因为在本方法体内不能够new一个泛型数组,需要在调用此方
   // 法时,传进来,然后可以通过复制的方法,并可数组长度,觉得一句足以完成下面7句,而无需
   // 判断,数组a的长度,与sortedBiTree的元素个数,最终一定返回的是数组的长度为sortedBiTree
   // 的长度,而且当a.length大于等于this.capacity时,返回的数组长度是a.length的,而
   // 调用者应该想得到的是sortedBiTree的元素个数
   /*
   * if (a.length < this.capacity) return (T[])
   * Arrays.copyOf(elementData,this.capacity, a.getClass());
   * System.arraycopy(elements, 0, a, 0,this.capacity); if (a.length >
   * size) a[capacity] = null; return a;
   */
}

/**
* @function 得到E类型元素最大的那个结点的元素,
* @param none
* @return SortedBiTreeNode<E>类型的结点
*/
public E getMax() {
   if (this.isEmpty())
    return null;
   SortedBiTreeNode<E> tempNode = this.root;
   SortedBiTreeNode<E> pref = null;
   while (tempNode != null) {
    pref = tempNode;
    tempNode = tempNode.rChild;
   }
   return pref.element;
}

/**
* @function 得到树的元素个数
* @param none
* @return 返回树的结点个数
*/
public int size() {
   return this.capacity;
}
}

分享到:
评论

相关推荐

    红黑树、二叉平衡树、二叉排序树的java实现

    本项目涵盖了三种重要的树形数据结构的Java实现:红黑树(RBTree)、二叉平衡树(AVLTree)以及二叉排序树(BSTree)。这些数据结构在处理大量数据时,能够提供高效的插入、删除和查找操作,广泛应用于数据库索引、...

    二叉查找树的插入、删除、遍历和查找等C++实现

    二叉查找树的插入、删除、遍历和查找等操作的C++实现,二叉查找树采用泛型结构

    c++ 二叉查找树模板示例.pdf

    在给定的C++代码中,定义了一个泛型的二叉查找树类`BinarySearchTree`,使用了模板类来支持不同类型的元素。以下是代码中的关键部分和它们对应的知识点: 1. **节点结构**:`BinarySearchTree`类中有一个私有嵌套...

    C++写的二叉树,使用了模板实现

    在C++中,我们通常通过结构体或类来表示树节点,而为了增加代码的通用性,我们可以使用模板来实现二叉树。这样,我们的二叉树不仅可以存储整型数据,还可以存储其他类型的数据,如字符串、浮点数甚至是自定义对象。 ...

    实现泛型树的多种遍历C#源代码.zip

    2. 中序遍历:对于二叉排序树,中序遍历可以得到升序序列。先遍历左子树,然后访问根节点,最后遍历右子树。 3. 后序遍历:先遍历左子树,然后遍历右子树,最后访问根节点。在处理计算问题时,后序遍历特别有用,...

    BinaryOrderTree.zip_数据结构_Visual_C++_

    在C++中,为了提高代码复用性,可以使用模板来创建一个泛型的二叉排序树类,这样不仅可以处理整型数据,还可以处理其他类型,如字符串、自定义对象等。例如: ```cpp template class BinarySearchTree { public: ...

    可反转排序的泛型字典类

    3. **性能优化**:为了平衡排序和查找性能,实现可能会利用一些数据结构,比如平衡二叉搜索树,以确保高效的插入、删除和查找操作。 4. **遍历接口**:为了方便遍历排序后的元素,可能提供了`GetEnumerator()`方法...

    各种排序算法c++版

    二叉排序树(也称为二叉搜索树)是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。左子树上所有节点的值均小于它的根节点的值,右子树上所有节点的值均大于它的根节点的值。二叉排序树的...

    C#泛型优先队列

    优先队列通常用二叉堆来实现,即每个父节点的值都大于或等于其子节点的值(最大堆)或小于或等于其子节点的值(最小堆)。在C#中,`System.Collections.Generic`命名空间下的`PriorityQueue`类提供了对优先队列的...

    数据结构与算法+视频教学课程+学习面试使用

    第 6 课|树、图、二叉树、二叉搜索树 第 7 课|泛型递归、树的递归 第 8 课|分治、回溯 第 9 课|深度优先搜索和广度优先搜索第10课|高级搜索:剪枝与启发式 第 11课|贪心算法 第 12课|二分查找 第 13 课|动态规划 第 ...

    data-strcut-1.0.jar

    对Java的一些基本数据结构进行一个泛型容器的封装,如链表,顺序表,栈,队列,平衡二叉排序树,哈希表等一些基本数据结构和一些算法;实际在我们下载jdk的时候,已经安装上封装好泛型容器,这个jar包所以算是模仿造...

    Dictionary, SortedDictionary, SortedList 横向评测

    SortedDictionary 和 SortedList 都是二叉搜索树,检索运算复杂度为 O(log n),适合需要排序的数据存储和检索。 在实际应用中,需要根据具体情况选择合适的类。Dictionary 适合大规模数据的存储和检索,...

    数据结构与算法(C#)

    数据结构与算法(C#).PDF及代码 第1章 Collections类、泛型类和Timing类概述 ...第12章 二叉树和二叉查找树 第13章 集合 第14章 高级排序算法 第15章 用于查找的高级数据结构和算法 第16章 图和图的算法 第17章 高级算法

    排序、链表、树、C++模板代码

    例如,二叉搜索树允许快速查找、插入和删除操作,而哈夫曼树(又称最优二叉树)在数据压缩中有着广泛应用。 最后,我们来看C++模板。C++模板是一种泛型编程工具,允许程序员创建可以处理多种数据类型的函数或类。...

    C++suanfa

    除了基本操作外,二叉搜索树还有一些高级应用,如AVL树和红黑树,它们是自平衡的,能够保持树的高度平衡,从而在最坏情况下也能保持较好的性能。AVL树通过旋转操作保持平衡,而红黑树则使用颜色属性进行调整。 在...

    (java语言描述+源码)数据结构与算法

    《数据结构与算法分析:Java语言描述 第2版 》是国外数据结构与算法分析方面的经典教材 使用卓越的Java编程语言作为实现...第26章 二叉查找树(层次结构) 第27单 图及其应用 第28章 加权图及其应用 第29章 多线程

    2021春年《数据结构》考试大纲(专插本).pdf

    7. 查找技术部分,考生需要了解查找的基本概念,熟悉静态表查找(顺序查找、二分查找、分块查找)和动态表查找(二叉排序树、平衡二叉树、B-树、B+树)。此外,哈希表查找,包括哈希函数和冲突解决策略也是重点。 ...

    redblacktree:C#中的红黑泛型树

    红黑树是一种自平衡二叉查找树,由Rudolf Bayer在1972年提出。在C#中,红黑树被实现为一个泛型数据结构,可以在`System.Collections.Generic.RedBlack`命名空间中找到,它提供了高效的数据存储和检索功能。这个库...

    C++模板实现简单的数据结构

    3. **平衡二叉树(如AVL树、红黑树)**:这些是自我平衡的二叉搜索树,通过旋转操作确保树的平衡,以保持查找、插入和删除操作的效率在O(log n)范围内。 在C++中,二叉树的模板类需要包含节点结构、插入、删除、...

    基于java各类数据结构的实现和各种排序

    常见的有二叉搜索树(BST),其中左子节点的值小于父节点,右子节点的值大于父节点。二叉树支持插入、查找、删除等操作。 这些数据结构的泛型实现意味着它们可以存储任何类型的数据,只要这些数据实现了Comparable...

Global site tag (gtag.js) - Google Analytics