how2j.cn

本视频是解读性视频,所以希望您已经看过了本知识点的内容,并且编写了相应的代码之后,带着疑问来观看,这样收获才多。 不建议一开始就观看视频



29分53秒
本视频采用html5方式播放,如无法正常播放,请将浏览器升级至最新版本,推荐火狐,chrome,360浏览器 如果装有迅雷,播放视频呈现直接下载状态,请调整 迅雷系统设置-基本设置-启动-监视全部浏览器 (去掉这个选项)



示例 1 : 二叉树概念   
示例 2 : 二叉树排序-插入数据   
示例 3 : 二叉树排序-遍历   
示例 4 : 练习-英雄二叉树   
示例 5 : 答案-英雄二叉树   
示例 6 : 练习-比较冒泡法,选择法以及二叉树排序的性能区别   
示例 7 : 答案-比较冒泡法,选择法以及二叉树排序的性能区别   

示例 1 :

二叉树概念

二叉树由各种节点组成
二叉树特点:
每个节点都可以有左子节点,右子节点
每一个节点都有一个
二叉树概念
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;
}
示例 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的左节点。
...
...
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); } } }
示例 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()); } }
示例 4 :

练习-英雄二叉树

Or  姿势不对,事倍功半! 点击查看做练习的正确姿势
根据上面的学习和理解,设计一个Hero二叉树,HeroNode.
可以向这个英雄二叉树插入不同的Hero对象,并且按照Hero的血量倒排序

随机生成10个Hero对象,每个Hero对象都有不同的血量值,插入这个HeroNode后,把排序结果打印出来。
练习-英雄二叉树
示例 5 :

答案-英雄二叉树

在查看答案前,尽量先自己完成,碰到问题再来查看答案,收获会更多
本视频是解读性视频,所以希望您已经看过了本答案的内容,带着疑问来观看,这样收获才多。 不建议一开始就观看视频

3分17秒 本视频采用html5方式播放,如无法正常播放,请将浏览器升级至最新版本,推荐火狐,chrome,360浏览器 如果装有迅雷,播放视频呈现直接下载状态,请调整 迅雷系统设置-基本设置-启动-监视全部浏览器 (去掉这个选项)


为了方便打印效果,重写了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); } }
示例 6 :

练习-比较冒泡法,选择法以及二叉树排序的性能区别

Or  姿势不对,事倍功半! 点击查看做练习的正确姿势
创建4万个随机数,然后用分别用冒泡法选择法二叉树3种排序算法进行排序,比较哪种更快
示例 7 :

答案-比较冒泡法,选择法以及二叉树排序的性能区别

在查看答案前,尽量先自己完成,碰到问题再来查看答案,收获会更多
本视频是解读性视频,所以希望您已经看过了本答案的内容,带着疑问来观看,这样收获才多。 不建议一开始就观看视频

9分34秒 本视频采用html5方式播放,如无法正常播放,请将浏览器升级至最新版本,推荐火狐,chrome,360浏览器 如果装有迅雷,播放视频呈现直接下载状态,请调整 迅雷系统设置-基本设置-启动-监视全部浏览器 (去掉这个选项)


答案-比较冒泡法,选择法以及二叉树排序的性能区别
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公众号,关注后实时获知布最新的教程和优惠活动,谢谢。


问答区域    
2018-04-19 谁能解决这个问题?!
weigong



中序遍历所有的节点,它根据二叉树的逻辑关系按从小到大的顺序给遍历出来。很神奇啊!?我不理解的是他按照这种方式就把他从小到大排列出来了。我按这种方式走了一遍确实可以。笼统的来理解的话,三个数是按从左往右依次加进values集合的,所以输出也就是按这种顺序打印出来的,所以多个数按照某种逻辑也是可以这样输出的。这种逻辑我不知道是什么?是数学知识吗?实在不知道?那个大神帮忙给看看。
// 中序遍历所有的节点,它根据二叉树的逻辑关系按从小到大的顺序给遍历出来。很神奇啊!?我不理解的是他按照这种方式就把他从小到大排列出来了。我按这种方式走了一遍确实可以。笼统的来理解的话,三个数是按从左往右依次加进values集合的,所以输出也就是按这种顺序打印出来的,所以多个数按照某种逻辑也是可以这样输出的。这种逻辑我不知道是什么?是数学知识吗?实在不知道?那个大神帮忙给看看。
    public List<Object> values() {
        List<Object> values = new ArrayList<>();
  
        // 左节点的遍历结果
        if (null != leftNode)
            values.addAll(leftNode.values());   //
  
        // 当前节点
        values.add(value);zhong
  
        // 右节点的遍历结果
        if (null != rightNode)
  
            values.addAll(rightNode.values());
  
        return values;
    }

							


1 个答案

有梦想的小白 答案时间:2018-04-21
感觉是递归算法,你用小一点的数组写在纸上按照步骤全部写出来就体会到了




答案 或者 代码至少填写一项, 如果是自己有问题,请重新提问,否则站长有可能看不到





2018-04-16 leftNode和rightNode是Node类型的引用,不理解为什么可以作为rootNode的属性?
cmaooooyuaaaan



leftNode和rightNode是Node类型的引用,不理解为什么可以作为rootNode的属性?
public class Node {
	
	public Node leftNode;
	public Node rightNode;
	public Integer value;

							






答案 或者 代码至少填写一项, 如果是自己有问题,请重新提问,否则站长有可能看不到





2018-04-11 values 跟values() 真的弄蒙圈了 建议命名区分下吧
2018-03-12 二叉树,恐怖如斯
2017-12-28 我这里怎么是二叉树的排序性能远低于其他两个啊
2017-12-08 好不容易写出了快排的递归形式,给大家参考下
2017-11-28 示例7:StackOverflowError
2017-11-28 实例7:StackOverflowError
2017-11-28 泛型Node类,供参考
2017-11-13 Node中的add方法内,为什么可以调用自身(add方法)?
2017-10-28 方法的名字问题
2017-10-28 字符格式化问题
2017-10-15 Node是哪个包下面的?
2017-09-20 二叉树插入数据,0的位置
2017-09-20 站长能加个深度优先遍历和广度优先遍历吗
2017-09-16 public Object value;
2017-09-13 疑惑
2017-09-12 怎样将list中的Object的属性顺利变为String
2017-08-24 这里的遍历算法我是真的服气
2017-08-24 add() 与 addAll() 区别?
2017-07-29 二叉树排序是怎么回到上一层的
2017-07-27 有一点疑问就是比如public Node rightNode,在null的情况下会一直new创建新的,然后新的对象的引用都是同一个名称,就是对于具体的执行过程不是很了解
2017-07-08 最后一题按着答案来为什么报错Node cannot be resolved to a type
2017-07-07 递归真是有点吃力
2017-06-19 不知道怎么输出值
2017-06-14 二叉树排序性能
2017-05-26 hs是ArrayList类型对象,为什么它可以调用Hero的toString()方法啦?
2017-01-25 在add方法中判断欲插入值位置时为什么判断条件是“(Integer) v -((Integer)value) <= 0”
2016-05-15 addAll是一个什么方法?




提问之前请登陆
关于 JAVA 中级-集合框架-二叉树 的提问

尽量提供截图代码异常信息,有助于分析和解决问题。 也可进本站QQ群交流: 389538688
站长会在每个工作日早上尽量回答提问(如果有漏掉没有回答的,请进群提醒一下)
提问尽量提供完整的代码,环境描述,越是有利于问题的重现,您的问题越能更快得到解答。
对教程中代码有疑问,请提供是哪个步骤,哪一行有疑问,这样便于快速定位问题,提高问题得到解答的速度
站长是玻璃心,提问的时候请语气温柔些 kiss~
截止2017-5-19日累计提问 1638个,站长回答了 1546个
截止2017-8-15日累计提问 2788个,站长回答了 2544个

上传截图