Java自学-集合框架 二叉树

时间:2021-01-19 09:10:40

Java集合框架 二叉树

示例 1 : 二叉树概念

二叉树由各种节点组成

二叉树特点:

每个节点都可以有子节点,子节点

每一个节点都有一个

Java自学-集合框架 二叉树

package collection;

public class Node {
// 左子节点
public Node leftNode;
// 右子节点
public Node rightNode;
// 值
public Object value;
}

示例 2 : 二叉树排序-插入数据

假设通过二叉树对如下10个随机数进行排序

67,7,30,73,10,0,78,81,10,74

排序的第一个步骤是把数据插入到该二叉树中

插入基本逻辑是,小、相同的放左边,大的放右边

  1. 67 放在根节点

  2. 7 比 67小,放在67的左节点

  3. 30 比67 小,找到67的左节点7,30比7大,就放在7的右节点

  4. 73 比67大, 放在67的右节点

  5. 10 比 67小,找到67的左节点7,10比7大,找到7的右节点30,10比30小,放在30的左节点。

    ...

    ...

  6. 10比67小,找到67的左节点7,10比7大,找到7的右节点30,10比30小,找到30的左节点10,10和10一样大,放在左边

    Java自学-集合框架 二叉树

     package collection;
    
     public class Node {
    // 左子节点
    public Node leftNode;
    // 右子节点
    public Node rightNode; // 值
    public Object value; // 插入 数据
    public void add(Object v) {
    // 如果当前节点没有值,就把数据放在当前节点上
    if (null == value)
    value = v; // 如果当前节点有值,就进行判断,新增的值与当前值的大小关系
    else {
    // 新增的值,比当前值小或者相同 if ((Integer) v -((Integer)value) <= 0) {
    if (null == leftNode)
    leftNode = new Node();
    leftNode.add(v);
    }
    // 新增的值,比当前值大
    else {
    if (null == rightNode)
    rightNode = new Node();
    rightNode.add(v);
    } } } public static void main(String[] args) { int randoms[] = new int[] { 67, 7, 30, 73, 10, 0, 78, 81, 10, 74 }; Node roots = new Node();
    for (int number : randoms) {
    roots.add(number);
    } }
    }

示例 3 : 二叉树排序-遍历

通过上一个步骤的插入行为,实际上,数据就已经排好序了。 接下来要做的是看,把这些已经排好序的数据,遍历成我们常用的List或者数组的形式

二叉树的遍历分左序,中序,右序

左序即: 中间的数遍历后放在左边

中序即: 中间的数遍历后放在中间

右序即: 中间的数遍历后放在右边

如图所见,我们希望遍历后的结果是从小到大的,所以应该采用中序遍历

Java自学-集合框架 二叉树

package collection;

import java.util.ArrayList;
import java.util.List; public class Node {
// 左子节点
public Node leftNode;
// 右子节点
public Node rightNode; // 值
public Object value; // 插入数据
public void add(Object v) {
// 如果当前节点没有值,就把数据放在当前节点上
if (null == value)
value = v; // 如果当前节点有值,就进行判断,新增的值与当前值的大小关系
else {
// 新增的值,比当前值小或者相同 if ((Integer) v -((Integer)value) <= 0) {
if (null == leftNode)
leftNode = new Node();
leftNode.add(v);
}
// 新增的值,比当前值大
else {
if (null == rightNode)
rightNode = new Node();
rightNode.add(v);
} } } // 中序遍历所有的节点
public List<Object> values() {
List<Object> values = new ArrayList<>(); // 左节点的遍历结果
if (null != leftNode)
values.addAll(leftNode.values()); // 当前节点
values.add(value); // 右节点的遍历结果
if (null != rightNode) values.addAll(rightNode.values()); return values;
} public static void main(String[] args) { int randoms[] = new int[] { 67, 7, 30, 73, 10, 0, 78, 81, 10, 74 }; Node roots = new Node();
for (int number : randoms) {
roots.add(number);
} System.out.println(roots.values()); }
}

练习英雄二叉树

根据上面的学习和理解,设计一个Hero二叉树,HeroNode.

可以向这个英雄二叉树插入不同的Hero对象,并且按照Hero的血量倒排序。

随机生成10个Hero对象,每个Hero对象都有不同的血量值,插入这个HeroNode后,把排序结果打印出来。

Java自学-集合框架 二叉树

package collection;

import java.util.ArrayList;
import java.util.List; import charactor.Hero; public class HeroNode { public HeroNode leftHero; public HeroNode rightHero; // 声明为Hero类型
public Hero value; public void add(Hero v) { if (null == value)
value = v; else { // 如果新英雄血量,比本节点大,就放在左边
if (v.hp > value.hp) {
if (null == leftHero)
leftHero = new HeroNode();
leftHero.add(v);
} else {
if (null == rightHero)
rightHero = new HeroNode();
rightHero.add(v);
} } } public List<Object> values() {
List<Object> values = new ArrayList<>(); if (null != leftHero)
values.addAll(leftHero.values()); values.add(value); if (null != rightHero) values.addAll(rightHero.values()); return values;
} public static void main(String[] args) { List<Hero> hs = new ArrayList<>();
for (int i = 0; i < 10; i++) {
Hero h = new Hero();
h.name = "hero " + i;
h.hp = (float) (Math.random() * 900 + 100); // 100-1000的随机血量
hs.add(h);
}
System.out.println("初始化10个Hero");
System.out.println(hs); HeroNode heroTree = new HeroNode();
for (Hero hero : hs) {
heroTree.add(hero);
}
System.out.println("根据血量倒排序后的Hero");
List<Object> treeSortedHeros = heroTree.values();
System.out.println(treeSortedHeros); }
}

Java自学-集合框架 二叉树的更多相关文章

  1. Java自学-集合框架 Collections

    Java集合框架 工具类Collections Collections是一个类,容器的工具类,就如同Arrays是数组的工具类 步骤 1 : 反转 reverse 使List中的数据发生翻转 pack ...

  2. Java自学-集合框架 Collection

    Java集合框架 Collection Collection是一个接口 步骤 1 : Collection Collection是 Set List Queue和 Deque的接口 Queue: 先进 ...

  3. Java自学-集合框架 HashSet

    Java集合框架 HashSet 示例 1 : 元素不能重复 Set中的元素,不能重复 package collection; import java.util.HashSet; public cla ...

  4. Java自学-集合框架 HashMap

    Java集合框架 HashMap 示例 1 : HashMap的键值对 HashMap储存数据的方式是-- 键值对 package collection; import java.util.HashM ...

  5. Java自学-集合框架 LinkedList

    Java集合框架 LinkedList 序列分先进先出FIFO,先进后出FILO FIFO在Java中又叫Queue 队列 FILO在Java中又叫Stack 栈 示例 1 : LinkedList ...

  6. Java自学-集合框架 与数组的区别

    Java集合框架与数组的区别 示例 1 : 使用数组的局限性 如果要存放多个对象,可以使用数组,但是数组有局限性 比如 声明长度是10的数组 不用的数组就浪费了 超过10的个数,又放不下 //Test ...

  7. Java自学-集合框架 遍历

    遍历ArrayList的三种方法 步骤 1 : 用for循环遍历 通过前面的学习,知道了可以用size()和get()分别得到大小,和获取指定位置的元素,结合for循环就可以遍历出ArrayList的 ...

  8. Java自学-集合框架 Comparator和Comparable

    Java Comparator和Comparable 步骤 1 : Comparator 假设Hero有三个属性 name,hp,damage 一个集合中放存放10个Hero,通过Collection ...

  9. Java自学-集合框架 聚合操作

    聚合操作 步骤 1 : 聚合操作 JDK8之后,引入了对集合的聚合操作,可以非常容易的遍历,筛选,比较集合中的元素. 像这样: String name =heros .stream() .sorted ...

随机推荐

  1. &lbrack;Spring&rsqb; - Quartz定时任务 - Annotation

    Spring + Quartz可以使用annoation方式: 1.AppJob类: package com.my.quartz.testquartz1; import org.springframe ...

  2. 结对项目——高级四则运算检验器记录(168 &amp&semi; 187)

    首先,上图(*+﹏+*)~@ 1.如何看待结对编程 结对编程优点: 1.两个人能够相互支持,相互监督,客服编程过程中可能出现的烦躁的情况0_0. 2.在开发功能的同时,伴随了UnitTest的进行,可 ...

  3. OD调试程序3

    条件跳转指令的图片,作为以后的参考. 载入了reverses.eve程序,F8下去,发现一个跳转,调用了一个函数,致使程序结束.于是我们绕过它,参考上面的 跳转指令图片. 然后继续F8 又会发现一个跳 ...

  4. css动画特效与js动画特效(一)------2017-03-24

    1.用css做动画效果: 放鼠标才会发生 利用hover <head> <style> #aa{ background-color: red; width: 100px; he ...

  5. 基本环境安装&colon; Centos7&plus;Java&plus;Hadoop&plus;Spark&plus;HBase&plus;ES&plus;Azkaban

    1.  安装VM14的方法在 人工智能标签中的<跨平台踩的大坑有提到> 2. CentOS分区设置: /boot:1024M,标准分区格式创建. swap:4096M,标准分区格式创建. ...

  6. Notes of O&lowbar;DIRECT flag

    What is O_DIRECT Starting with kernel 2.4, Linux allows an application to bypass the buffer cache wh ...

  7. SpringBoot(十)-- 整合MyBatis

    1.pom.xml 配置maven依赖 <dependency> <groupId>org.mybatis.spring.boot</groupId> <ar ...

  8. python分享题目

    目前的分享题目:1 python在云计算虚拟教室领域的应用 2 python与虚拟货币(华三工程师) 3 python在移动游戏的实践(爪子) 4 python互联网敏捷运维实践(蓝雪) 5 pyth ...

  9. Hive(一)Hive初识

    一 Hive 简介 什么是Hive 1.Hive 由 Facebook 实现并开源 2.是基于 Hadoop 的一个数据仓库工具 3.可以将结构化的数据映射为一张数据库表 4.并提供 HQL(Hive ...

  10. 一道算法题-从1到n整数中1出现的次数

    1. 题目描述 输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数.例如输入12,从1到12这些整数中包含1的数字有1,10,11和12,1一共出现了5次. 2. 题目来源 第一次看到是在 ...