|
|
|
|
本视频是解读性视频，所以希望您已经看过了本知识点的内容，并且编写了相应的代码之后，带着疑问来观看，这样收获才多。 不建议一开始就观看视频
29分53秒 本视频采用html5方式播放，如无法正常播放，请将浏览器升级至最新版本，推荐火狐，chrome，360浏览器。 如果装有迅雷，播放视频呈现直接下载状态，请调整 迅雷系统设置-基本设置-启动-监视全部浏览器 (去掉这个选项)。 chrome 的 视频下载插件会影响播放，如 IDM 等，请关闭或者切换其他浏览器 示例 1 : 二叉树概念 示例 2 : 二叉树排序-插入数据 示例 3 : 二叉树排序-遍历 示例 4 : 练习-英雄二叉树 示例 5 : 答案-英雄二叉树 示例 6 : 练习-比较冒泡法，选择法以及二叉树排序的性能区别 示例 7 : 答案-比较冒泡法，选择法以及二叉树排序的性能区别
二叉树由各种节点组成
二叉树特点： 每个节点都可以有左子节点，右子节点 每一个节点都有一个值 package collection;
public class Node {
// 左子节点
public Node leftNode;
// 右子节点
public Node rightNode;
// 值
public Object value;
}
package collection;
public class Node {
// 左子节点
public Node leftNode;
// 右子节点
public Node rightNode;
// 值
public Object value;
}
假设通过二叉树对如下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的左节点。 ... ... 9. 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);
}
}
}
通过上一个步骤的插入行为，实际上，数据就已经排好序了。 接下来要做的是看，把这些已经排好序的数据，遍历成我们常用的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后，把排序结果打印出来。
在查看答案前，尽量先自己完成，碰到问题再来查看答案，收获会更多
本视频是解读性视频，所以希望您已经看过了本答案的内容，带着疑问来观看，这样收获才多。 不建议一开始就观看视频
3分17秒 本视频采用html5方式播放，如无法正常播放，请将浏览器升级至最新版本，推荐火狐，chrome，360浏览器。 如果装有迅雷，播放视频呈现直接下载状态，请调整 迅雷系统设置-基本设置-启动-监视全部浏览器 (去掉这个选项)。 chrome 的 视频下载插件会影响播放，如 IDM 等，请关闭或者切换其他浏览器
为了方便打印效果，重写了Hero的toString()方法
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);
}
}
package charactor;
public class Hero {
public String name;
public float hp;
public int damage;
public Hero() {
}
public Hero(String name) {
this.name = name;
}
public String toString() {
return String.format("[name:%s hp:%.0f]%n", name,hp);
}
}
在查看答案前，尽量先自己完成，碰到问题再来查看答案，收获会更多
本视频是解读性视频，所以希望您已经看过了本答案的内容，带着疑问来观看，这样收获才多。 不建议一开始就观看视频
9分34秒 本视频采用html5方式播放，如无法正常播放，请将浏览器升级至最新版本，推荐火狐，chrome，360浏览器。 如果装有迅雷，播放视频呈现直接下载状态，请调整 迅雷系统设置-基本设置-启动-监视全部浏览器 (去掉这个选项)。 chrome 的 视频下载插件会影响播放，如 IDM 等，请关闭或者切换其他浏览器 package collection;
import java.util.Arrays;
import java.util.List;
public class SortCompare {
public static void main(String[] args) {
//初始化随机数
int total = 40000;
System.out.println("初始化一个长度是"+total+"的随机数字的数组");
int[] originalNumbers = new int[total];
for (int i = 0; i < originalNumbers.length; i++) {
originalNumbers[i] = (int)(Math.random()*total);
}
System.out.println("初始化完毕");
System.out.println("接下来分别用3种算法进行排序");
//从初始化了的随机数组复制过来，以保证，每一种排序算法的目标数组，都是一样的
int[] use4sort;
use4sort= Arrays.copyOf(originalNumbers, originalNumbers.length);
int[] sortedNumbersBySelection= performance(new SelectionSort(use4sort),"选择法");
use4sort= Arrays.copyOf(originalNumbers, originalNumbers.length);
int[] sortedNumbersByBubbling=performance(new BubblingSort(use4sort),"冒泡法");
use4sort= Arrays.copyOf(originalNumbers, originalNumbers.length);
int[] sortedNumbersByTree=performance(new TreeSort(use4sort),"二叉树");
System.out.println("查看排序结果，是否是不同的数组对象");
System.out.println(sortedNumbersBySelection);
System.out.println(sortedNumbersByBubbling);
System.out.println(sortedNumbersByTree);
System.out.println("查看排序结果，内容是否相同");
System.out.println("比较 选择法 和 冒泡法 排序结果：");
System.out.println(Arrays.equals(sortedNumbersBySelection, sortedNumbersByBubbling));
System.out.println("比较 选择法 和 二叉树 排序结果：");
System.out.println(Arrays.equals(sortedNumbersBySelection, sortedNumbersByTree));
}
interface Sort{
void sort();
int[] values();
}
static class SelectionSort implements Sort{
int numbers[];
SelectionSort(int [] numbers){
this.numbers = numbers;
}
@Override
public void sort() {
for (int j = 0; j < numbers.length-1; j++) {
for (int i = j+1; i < numbers.length; i++) {
if(numbers[i]<numbers[j]){
int temp = numbers[j];
numbers[j] = numbers[i];
numbers[i] = temp;
}
}
}
}
@Override
public int[] values() {
// TODO Auto-generated method stub
return numbers;
}
}
static class BubblingSort implements Sort{
int numbers[];
BubblingSort(int [] numbers){
this.numbers = numbers;
}
@Override
public void sort() {
for (int j = 0; j < numbers.length; j++) {
for (int i = 0; i < numbers.length-j-1; i++) {
if(numbers[i]>numbers[i+1]){
int temp = numbers[i];
numbers[i] = numbers[i+1];
numbers[i+1] = temp;
}
}
}
}
@Override
public int[] values() {
// TODO Auto-generated method stub
return numbers;
}
}
static class TreeSort implements Sort{
int numbers[];
Node n;
TreeSort(int [] numbers){
n =new Node();
this.numbers = numbers;
}
@Override
public void sort() {
for (int i : numbers) {
n.add(i);
}
}
@Override
public int[] values() {
List<Object> list = n.values();
int sortedNumbers[] = new int[list.size()];
for (int i = 0; i < sortedNumbers.length; i++) {
sortedNumbers[i] = Integer.parseInt(list.get(i).toString());
}
return sortedNumbers;
}
}
private static int[] performance(Sort algorithm, String type) {
long start = System.currentTimeMillis();
algorithm.sort();
int sortedNumbers[] = algorithm.values();
long end = System.currentTimeMillis();
System.out.printf("%s排序，一共耗时 %d 毫秒%n",type,end-start);
return sortedNumbers;
}
}
HOW2J公众号，关注后实时获知最新的教程和优惠活动，谢谢。
问答区域
2024-01-02
英雄BST排序
回答已经提交成功，正在审核。 请于 我的回答 处查看回答记录，谢谢
2023-12-04
英雄二叉树
回答已经提交成功，正在审核。 请于 我的回答 处查看回答记录，谢谢
2023-09-23
练习-英雄二叉树
2022-09-22
快速排序是神
2022-09-12
三种排序法答案
提问太多，页面渲染太慢，为了加快渲染速度，本页最多只显示几条提问。还有 125 条以前的提问，请 点击查看
提问之前请登陆
提问已经提交成功，正在审核。 请于 我的提问 处查看提问记录，谢谢
|
