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-10-11 二叉树排序也太秀了
hty



true true 1467 6124 178
package 集合框架;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 选择冒泡二叉排序比较 {
    public static void main(String[] args){
        int a[]=new int[40000];
        for (int i=0;i<40000;i++){
            a[i]=(int)(Math.random()*100);
        }
        int b[]= Arrays.copyOf(a,40000);
        System.out.println(Arrays.equals(a,b));
        int c[]=Arrays.copyOf(a,40000);
        System.out.println(Arrays.equals(a,c));
        long start=System.currentTimeMillis();
        for (int j=0;j<a.length-1;j++){
            for (int i=j+1;i<a.length;i++){
                if (a[j]>a[i]){
                    int temp=a[j];
                    a[j]=a[i];
                    a[i]=temp;
                }
            }
        }
        long end=System.currentTimeMillis();
        System.out.println(end-start);

        long start1=System.currentTimeMillis();
        for (int j=0;j<b.length;j++){
            for (int i=0;i<b.length-j-1;i++){
                if (b[i]>b[i+1]){
                    int temp=a[i];
                    a[i]=a[i+1];
                    a[i+1]=temp;
                }
            }
        }
        long end1=System.currentTimeMillis();
        System.out.println(end1-start1);

        long start2=System.currentTimeMillis();
        Node c1=new Node();
        for (int x:c)
            c1.add(x);
        long end2=System.currentTimeMillis();
        System.out.println(end2-start2);


    }
    public static class Node{
        public Node left;
        public Node right;
        public Object value;
        public void add(Object v){
            if (value==null)
                value=v;
            else{
                if ((Integer)v<=(Integer) value){
                    if (left==null)
                        left=new Node();
                    left.add(v);
                }
                else{
                    if (right==null)
                        right=new Node();
                    right.add(v);
                }
            }
        }
        public List<Object> values(){
            List<Object> values=new ArrayList<>();
            if (left==null)
                values.addAll(values());
            values.add(value);
            if (right==null)
                values.addAll(values());
            return values;
        }
    }
}

							






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





2018-10-04 为啥二叉树里面的计时器不输出?
JJG



为啥二叉树里面的计时器不输出?
package demo.collection;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/*
* 创建4万个随机数,然后用分别用冒泡法,选择法,二叉树3种排序算法进行排序,比较哪种更快 
* */
public class TestSorting {
    private static long startMili;
    private static long endMili;
    public static void main(String[] args) {
        int[] arr = new int[20000];
        Random r = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt(50000);
        }
        int[] brr = Arrays.copyOf(arr,arr.length);
        int[] crr = Arrays.copyOf(arr,arr.length);

        try {
            System.out.println("暂停2秒");
            Thread.sleep(2000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }


        startMili = System.currentTimeMillis();
        select(brr);
        endMili = System.currentTimeMillis();
        System.out.println("\n选择法排序耗时" + (endMili - startMili) + "毫秒");

        try {
            System.out.println("暂停2秒");
            Thread.sleep(2000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        startMili = System.currentTimeMillis();
        bubble(arr);
        endMili = System.currentTimeMillis();
        System.out.println("\n冒泡法排序耗时" + (endMili - startMili) + "毫秒");

        try {
            System.out.println("暂停2秒");
            Thread.sleep(2000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }


        startMili = System.currentTimeMillis();
        select(crr);
        endMili = System.currentTimeMillis();
        System.out.println("\n二叉树法排序耗时" + (endMili - startMili) + "毫秒");



        
    }
    
    public static void bubble(int[] arr){
        int j = 1;
        while(j < arr.length){
            for (int i = 0; i < arr.length - j; i++) {
                if (arr[i] > arr[i+1]){
                    int temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
            j++;
        }
        for (int i = 100; i <120 ; i++) {
            System.out.print(arr[i] + "\t");
        }
    }

    public static void select(int[] arr){
        for (int i = 0; i < arr.length -1; i++) {
            for (int j = i + 1;j<arr.length;j++){
                if (arr[j] < arr[i]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                 }
            }
        }

        for (int i = 100; i <120 ; i++) {
            System.out.print(arr[i] + "\t");
        }
    }

    public static void tree(int[] arr){
        long start = System.currentTimeMillis();
        SplitNode sn = new SplitNode(arr[0]);
        for (int i = 1; i < arr.length ; i++) {
            sn.attach(arr[i]);
        }
        long end = System.currentTimeMillis();
        System.out.println("\n二叉树注入耗时" + (end - start) + "毫秒");

        List<Integer> list = sn.values();
        Integer[] drr = list.toArray(new Integer[list.size()]);
        for (int i = 100; i < 120; i++) {
            System.out.print(drr[i] + "\t");
        }
    }
}
暂停2秒
228	228	228	230	234	236	251	253	258	258	258	264	265	268	271	274	275	275	276	280	
选择法排序耗时810毫秒
暂停2秒
228	228	228	230	234	236	251	253	258	258	258	264	265	268	271	274	275	275	276	280	
冒泡法排序耗时765毫秒
暂停2秒
228	228	228	230	234	236	251	253	258	258	258	264	265	268	271	274	275	275	276	280	
二叉树法排序耗时803毫秒

Process finished with exit code 0






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





2018-09-29 二叉树排序-插入数据代码错误了吧
2018-09-26 二叉树排序性能
2018-09-26 中序遍历是怎样实现的啊
2018-09-23 简单易懂,忽略前面的其他内容
2018-09-23 简单易懂,忽略前面的其他内容
2018-09-22 简单易懂
2018-09-21 求助,按照站长的代码,但输出结果不对~
2018-09-07 线程出现栈溢出
2018-08-30 ok?
2018-08-25 Arrysort比二叉更快速的排序方法,还可以排列对象
2018-08-03 为什么我的选择排序比冒泡还慢?求解答....十分感谢!
2018-08-03 为什么我的选择排序比冒泡用时还长?求解答....非常感谢!
2018-08-03 如果在输入的时候左节点不为空呢?
2018-07-30 交作业
2018-07-24 二叉树真快阿,快排就更快了
2018-07-07 StackOverflowError
2018-07-02 交作业,仅供参考
2018-07-02 交作业,仅供参考
2018-06-01 站长大大,答案就不能单条购买吗,非要来个全部
2018-05-31 帮我看下为什么我的二叉树排序速度最慢, 数组一多的时候报错
2018-05-31 为何我的二叉树最慢?
2018-05-04 【交作业】比较冒泡法,选择法以及二叉树排序的性能区别
2018-05-03 我使用idea直接复制教程中二叉树插入那段的代码,为何add报错?
2018-04-28 二叉树需要的时间和其他两个差不多
2018-04-19 谁能解决这个问题?!
2018-04-16 leftNode和rightNode是Node类型的引用,不理解为什么可以作为rootNode的属性?
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群交流: 902680467
提问尽量提供完整的代码,环境描述,越是有利于问题的重现,您的问题越能更快得到解答。
对教程中代码有疑问,请提供是哪个步骤,哪一行有疑问,这样便于快速定位问题,提高问题得到解答的速度
在已经存在的几千个提问里,有相当大的比例,是因为使用了和站长不同版本的开发环境导致的,比如 jdk, eclpise, idea, mysql,tomcat 等等软件的版本不一致。
请使用和站长一样的版本,可以节约自己大量的学习时间。 站长把教学中用的软件版本整理了,都统一放在了这里, 方便大家下载: http://how2j.cn/k/helloworld/helloworld-version/1718.html

上传截图