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-12-13 作业
逝月



理解二叉树那段代码花了一段时间,乍一看并不难,递归而已。然而对于以类为数据类型的左右两个节点,如何通过递归存储那么多数据,我纠结了好久。
package how2j;

import java.util.List;
import java.util.ArrayList;

public class HeroNode{
	
	public HeroNode leftNode;
	public HeroNode rightNode;
	public Hero value;
	
	public void add(Hero h)
	{
		if(null==value)
			value=h;
		else
		{
			if((Integer)h.hp-(Integer)value.hp<=0)
			{
				if(null==leftNode)
					leftNode=new HeroNode();
				leftNode.add(h);	
			}
			else
			{
				if(null==rightNode)
					rightNode=new HeroNode();
				rightNode.add(h);
			}
		}
	}
	
	public List<Hero> values()
	{
		List<Hero> values=new ArrayList<>();
		if(null!=rightNode)
			values.addAll(rightNode.values());
		values.add(value);
		if(null!=leftNode)
			values.addAll(leftNode.values());
		return values;
		
	}
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		
	}
}
/*******************************************************************/
package how2j;
import java.util.ArrayList;
import java.util.List;
public class Hero {
	
	String name;
	int hp;
	Hero(String name,int hp)
	{
		this.name=name;
		this.hp=hp;
	}

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		List<Hero> l=new ArrayList<>();
		HeroNode hn=new HeroNode();
		
		//创建4万个……对象,和数字差不多吧
		for(int i=0;i<40000;i++)
		{
			int hp=(int)(Math.random()*100);
			l.add(new Hero("Hero "+i,hp));
		}		
		//二叉树
		long ls=System.currentTimeMillis();
		for(int i=0;i<l.size();i++)
		{
			hn.add(l.get(i));
		}
		l=hn.values();
		long exs=System.currentTimeMillis();
		System.out.println("二叉树:"+(exs-ls));
		//冒泡
		for(int i=0;i<l.size();i++)
		{
			for(int j=0;j<l.size()-i-1;j++)
			{
				if(l.get(j).hp<l.get(j+1).hp)
				{
					Hero h=l.get(j);
					l.set(j, l.get(j+1));
					l.set(j+1, h);
				}
			}
		}
		long mp=System.currentTimeMillis();
		System.out.println("冒泡:"+(mp-exs));
		//选择
		for(int i=0;i<l.size()-1;i++)
		{
			for(int j=1+i;j<l.size();j++)
			{
				if(l.get(i).hp<l.get(j).hp)
				{
					Hero h=l.get(i);
					l.set(i, l.get(j));
					l.set(j, h);
				}
			}
		}
		long xz=System.currentTimeMillis();
		System.out.println("选择:"+(xz-mp));
	}

}

							






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





2018-11-19 二叉树问题求教
茶客



我构建了10个对象,但是一顿操作后只有两个打印出来,这是为什么呢?大神们指点一二
package collection;

import charactor.Hero0;

import java.util.ArrayList;
import java.util.List;

public class HeroHpSort {
    public String name;

    public static List heros = new ArrayList();
    public Node leftNode;
    public Node rightNode;
    public Object value;

    //构建二叉树
    public void addHero(Object v) {
        if (null == value) {
            value = v;
        } else {
            if (getHp(value) >= getHp(v)) {
                leftNode = new Node();
                leftNode.add(v);
            } else {
                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 float getHp(Object o) {
        String str = o.toString();
        int hpLocal = str.lastIndexOf("hp");
        float strHp = (Integer.parseInt((str.substring(hpLocal + 3))));
        return strHp;
    }

    public static void main(String[] args) {
        //生成对象数据集合
        for (int i = 0; i < 10; i++) {
            heros.add(new Hero0("name:hero " + i + " hp:" + (int) (Math.random() * 100)));
        }

        HeroHpSort root = new HeroHpSort();

        for (int j = 0; j < heros.size(); j++) {
            root.addHero(heros.get(j));
        }
        System.out.println(root.values());

    }

}

							


1 个答案

ppprice 答案时间:2018-11-27
你在addHero里缺少判断LeftNode和RightNode是否为空的语句,并且你addHero里面添加元素的时候用的是add而不是addHero,压根就构不成递归 if (getHp(value) >= getHp(v)) { if(leftNode==null) { leftNode = new Node(); } leftNode.addHero(v); } 这个递归算法的原理就在于,当左子树已经有一些节点时,通过向根节点左侧的节点执行addHero,当根节点的左节点已经存在时,继续向根节点左侧节点的左侧节点执行addHero,一直到执行到了LeftNode为空,这时候再去创建一个新的节点作为子节点,因为新创建出来的子节点的value == null,那么这一重递归中 if (null == value)成立,value=v执行,才能算是添加节点成功。




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





2018-10-18 最终输出List ,怎样才能变成例子中数组的输出格式。我的是十六进制地址。
2018-10-11 二叉树排序也太秀了
2018-10-04 为啥二叉树里面的计时器不输出?
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

上传截图