Java集合框架 二叉树
示例 1 : 二叉树概念
二叉树由各种节点组成
二叉树特点:
每个节点都可以有左子节点,右子节点
每一个节点都有一个值
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
排序的第一个步骤是把数据插入到该二叉树中
插入基本逻辑是,小、相同的放左边,大的放右边
67 放在根节点
7 比 67小,放在67的左节点
30 比67 小,找到67的左节点7,30比7大,就放在7的右节点
73 比67大, 放在67的右节点
10 比 67小,找到67的左节点7,10比7大,找到7的右节点30,10比30小,放在30的左节点。
...
...-
10比67小,找到67的左节点7,10比7大,找到7的右节点30,10比30小,找到30的左节点10,10和10一样大,放在左边
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或者数组的形式
二叉树的遍历分左序,中序,右序
左序即: 中间的数遍历后放在左边
中序即: 中间的数遍历后放在中间
右序即: 中间的数遍历后放在右边
如图所见,我们希望遍历后的结果是从小到大的,所以应该采用中序遍历
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后,把排序结果打印出来。
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自学-集合框架 二叉树的更多相关文章
-
Java自学-集合框架 Collections
Java集合框架 工具类Collections Collections是一个类,容器的工具类,就如同Arrays是数组的工具类 步骤 1 : 反转 reverse 使List中的数据发生翻转 pack ...
-
Java自学-集合框架 Collection
Java集合框架 Collection Collection是一个接口 步骤 1 : Collection Collection是 Set List Queue和 Deque的接口 Queue: 先进 ...
-
Java自学-集合框架 HashSet
Java集合框架 HashSet 示例 1 : 元素不能重复 Set中的元素,不能重复 package collection; import java.util.HashSet; public cla ...
-
Java自学-集合框架 HashMap
Java集合框架 HashMap 示例 1 : HashMap的键值对 HashMap储存数据的方式是-- 键值对 package collection; import java.util.HashM ...
-
Java自学-集合框架 LinkedList
Java集合框架 LinkedList 序列分先进先出FIFO,先进后出FILO FIFO在Java中又叫Queue 队列 FILO在Java中又叫Stack 栈 示例 1 : LinkedList ...
-
Java自学-集合框架 与数组的区别
Java集合框架与数组的区别 示例 1 : 使用数组的局限性 如果要存放多个对象,可以使用数组,但是数组有局限性 比如 声明长度是10的数组 不用的数组就浪费了 超过10的个数,又放不下 //Test ...
-
Java自学-集合框架 遍历
遍历ArrayList的三种方法 步骤 1 : 用for循环遍历 通过前面的学习,知道了可以用size()和get()分别得到大小,和获取指定位置的元素,结合for循环就可以遍历出ArrayList的 ...
-
Java自学-集合框架 Comparator和Comparable
Java Comparator和Comparable 步骤 1 : Comparator 假设Hero有三个属性 name,hp,damage 一个集合中放存放10个Hero,通过Collection ...
-
Java自学-集合框架 聚合操作
聚合操作 步骤 1 : 聚合操作 JDK8之后,引入了对集合的聚合操作,可以非常容易的遍历,筛选,比较集合中的元素. 像这样: String name =heros .stream() .sorted ...
随机推荐
-
[Spring] - Quartz定时任务 - Annotation
Spring + Quartz可以使用annoation方式: 1.AppJob类: package com.my.quartz.testquartz1; import org.springframe ...
-
结对项目——高级四则运算检验器记录(168 &; 187)
首先,上图(*+﹏+*)~@ 1.如何看待结对编程 结对编程优点: 1.两个人能够相互支持,相互监督,客服编程过程中可能出现的烦躁的情况0_0. 2.在开发功能的同时,伴随了UnitTest的进行,可 ...
-
OD调试程序3
条件跳转指令的图片,作为以后的参考. 载入了reverses.eve程序,F8下去,发现一个跳转,调用了一个函数,致使程序结束.于是我们绕过它,参考上面的 跳转指令图片. 然后继续F8 又会发现一个跳 ...
-
css动画特效与js动画特效(一)------2017-03-24
1.用css做动画效果: 放鼠标才会发生 利用hover <head> <style> #aa{ background-color: red; width: 100px; he ...
-
基本环境安装: Centos7+Java+Hadoop+Spark+HBase+ES+Azkaban
1. 安装VM14的方法在 人工智能标签中的<跨平台踩的大坑有提到> 2. CentOS分区设置: /boot:1024M,标准分区格式创建. swap:4096M,标准分区格式创建. ...
-
Notes of O_DIRECT flag
What is O_DIRECT Starting with kernel 2.4, Linux allows an application to bypass the buffer cache wh ...
-
SpringBoot(十)-- 整合MyBatis
1.pom.xml 配置maven依赖 <dependency> <groupId>org.mybatis.spring.boot</groupId> <ar ...
-
python分享题目
目前的分享题目:1 python在云计算虚拟教室领域的应用 2 python与虚拟货币(华三工程师) 3 python在移动游戏的实践(爪子) 4 python互联网敏捷运维实践(蓝雪) 5 pyth ...
-
Hive(一)Hive初识
一 Hive 简介 什么是Hive 1.Hive 由 Facebook 实现并开源 2.是基于 Hadoop 的一个数据仓库工具 3.可以将结构化的数据映射为一张数据库表 4.并提供 HQL(Hive ...
-
一道算法题-从1到n整数中1出现的次数
1. 题目描述 输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数.例如输入12,从1到12这些整数中包含1的数字有1,10,11和12,1一共出现了5次. 2. 题目来源 第一次看到是在 ...