位于上海,服务全国!

位于上海,服务全国!

助力您的企业早日腾飞!

助力您的企业早日腾飞!

携手走向远方!

携手走向远方!

ope体育网站-ope体育注册页-ope体育注册教程

作者:admin 分类: 时间:2017-06-08 16:35:03 点击量:1141

树是一种非线性数据结构,其中数据对象按层次关系组织。在这种意义上,结构是非线性的,与简单数组和链表实现不同,而树中的数据不是线性组织的。每个数据元素被存储在称为节点的结构中。 (倒置)树的最顶层或起始节点称为根节点。所有节点都与边缘链接,并形成从根节点开始的分层子树。在数据线性不足以表示的情况下,树形数据结构很有用,例如创建一个族树。 Java在Java Collection Framework中提供了两个内置的TreeSet和TreeMap类,以满足程序员通过上述形式描述数据元素的需要。

树数据结构
Java树类是特定种类的树数据结构的实际实现。因此,在使用之前,我们必须对其组织有一些了解。
根据定义,树T是一组非空的元素,其中这些元素中的一个被称为根和剩余元素(其中可能存在或可能不存在于具有空集合Set Theory的空树情况)被进一步划分为T的子树。
例如,思考以下族树中的层次关系。
 
图1:一棵族树

Tim的后裔节点以分层的方式安排。 (倒置)树顶部的Tim表示根节点。Tim的子节点是Bobby, Ron, 和 Amy。Bobby没有子节点,Ron有一个,Amy有两个。它们以相同的分层方式列出。每个节点之间的链接称为边。这个链接表示一个节点与另一个节点之间的关系,如Amy的子节点,Bobby的兄弟姐妹,Tim的后裔节点等等。有时,树的结尾节点称为叶。
现在,根据组织结构,树可以在很多方面实现。在其许多形式中,二叉树是特别重要的,因为它实现起来简单有效。二叉树的约束是允许最多两个子节点从父节点引出;他们分别被称为左节点和右节点。从左子节点延伸的树称为左子树,从右子节点延伸的树称为右子树。这对于任何类型的二叉树是常见的,因为二叉树还具有各种实现方案。这些方案中的每一个都有一些明确的创建和维护规范,其直接影响数据元素的访问机制,通常以大O符号表示。
例如,如果在特定类型的二叉树中搜索数据元素需要O(n2)次,并且在最坏的情况下需要另外一种类型的二叉树实现,则O(log2 n)次,则第二个实现是比第一个更有效率。

 
图2:二叉树实现
一些常见的二叉树类型被称为完整二叉树,完全二叉树,二叉搜索树(BST),高度平衡树(AVL),红黑树等。
红黑树
在各种类型的二叉树中,我们对红黑树感兴趣,因为Java树API实现是这种数据结构的一个实例。 Java API设计人员有理由剔除这种二叉树方案。 原因是它是许多平衡搜索树方案之一,即使在最坏的情况下也能保证O(log2 n)次的基本动态集合操作完成。
红黑树方案的属性如下:
红黑树为每个节点保留一个额外的信息,以表示其颜色,红色或黑色。
根节点总是黑色的。
每片叶子都是黑色的
红色节点的子节点都必须是黑色的。
对于每个节点,从节点到后续的所有简单路径都包含相同数量的黑色节点。
因此,实现必须确定这些属性在任何时间的情况下都保持,特别是在节点的“插入”和“删除”期间。 而且,为了保持动态的完整性,子树以错综复杂的逻辑左右旋转。 如果您想深入了解算法,并了解其在低级别中的工作原理,请阅读Cormen,Leiserson,Rivest和Stein的“算法简介”。
Java树API
幸运的是,使用Java API库时,我们不必处理红黑树的低级复杂实现逻辑。 相反,我们可以专注于解决现有问题,而不是从头开始实施该方案。 只需导入相关的软件包,并创建一个可用的现有树类的实例。 这就是我们需要做的。
如前所述,Java集合框架中有两种树型实现。 一个是TreeSet,另一个是TreeMap。 它们在java.util包中定义如下:

public class TreeSet
   extends AbstractSet
   implements NavigableSet, Cloneable, Serializable


public class TreeMap
   extends AbstractMap
   implements NavigableMap, Cloneable, Serializable
两种树类的令人兴奋的特征是,一个作为一个集合,另一个作为映射。 Set和Map分别是抽象类AbstractSet和AbstractMap实现的接口。
集合表示不同元素的集合 - 元素e1不能等于e1.equal(e2)同一集合的另一个元素e2。 此外,集合中只能有一个空元素。 它对元素的集合施加的属性是基于数学集抽象模型。
Map属性强制元素的集合必须有一个键值对。 每个键只映射到一个值; 这意味着它不允许有重复的键。 然而,具有不同键的值可能被重复。
树类TreeSet和TreeMap遵循从各自接口派生的具体规范,除了以二叉树形式组织其内部数据结构外。
TreeSet的一个快速示例
我们知道,Set实现的属性确保在将数据元素存储在树中时树不应包含任何重复项。 与其他集合实现相反,TreeSet保证根据元素的自然排序,存储的数据元素将默认排序。 让我们借助一个简单的例子来了解它的用法。
package org.mano.example;

import java.util.Arrays;
import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSetDemo {

   public static void main(String[] args) {

      Integer[] nums={2,4,1,6,3,7,9,5};
      SortedSettree=new TreeSet<>(Arrays.asList(nums));

      // Print first and last element
      System.out.println(tree.first());
      System.out.println(tree.last());

      printAll(tree);
      // False. Set does not allow duplicates,
      // so this will not be added.
      System.out.println(tree.add(1));

      // But, this will be added because 11 is not a duplicate
      System.out.println(tree.add(11));
      printAll(tree);

      printAll(tree.headSet(7));

   }

   public static void printAll(SortedSettree){
      for(int s: tree){
         System.out.println(s);
      }
      System.out.println();
   }
}
TreeMap的一个快速示例
一个关键的值对类很像另一个Map实现,称为HashMap。 除了将其数据元素存储在红黑树结构之外,TreeMap还保存了存储的密钥的顺序。 因此,当我们迭代键时,我们发现自然是有序的。 让我们借助一个简单的例子来看看。

package org.mano.example;

import java.util.Map;
import java.util.TreeMap;

public class TreeMapDemo {

   public static void main(String[] args){

      TreeMap treeMap=new TreeMap<>();

      treeMap.put("Paradise Lost", 23.56);
      treeMap.put("Golden Treasury", 12.47);
      treeMap.put("Moon and the Sixpence", 65.28);
      treeMap.put("Holinshed", 7.68);
      treeMap.put("Ancient Mariner", 45.36);

      printAll(treeMap);

      // Keys cannot be duplicates. This will not be stored.
      treeMap.put("Paradise Lost", 23.56);
      printAll(treeMap);

      // Values may be duplicates. This will be stored.
      treeMap.put("Paradise Regained", 23.56);
      printAll(treeMap);

   }

   public static void printAll(TreeMap treeMap){
      for(Map.Entry et:treeMap.entrySet()){
         System.out.println(et.getKey()+": "+et.getValue());
      }
      System.out.println();
   }
}
结论

TreeSet和TreeMap类是Java API库中二进制树数据结构中最明显的实现。 对于高级用户,数据组织规则在其用途上没有任何差异。 但是,由于维持平衡树结构规范的许多规则,树结构比其非树或线性对象(如HashSet和HashMap)要复杂得多,效率低下。 因此,除非有特定需要,否则其对应类会比树更频繁地被使用。