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公众号,关注后实时获知布最新的教程和优惠活动,谢谢。


问答区域    
2017-12-28 我这里怎么是二叉树的排序性能远低于其他两个啊
神奇大叶子



简单排序法排序,一共耗时 3068 冒泡排序法排序,一共耗时 2950 二叉树排序法排序,一共耗时 165388 [I@14ae5a5 true true
代码就是和你一模一样的

							


1 个答案

神奇大叶子 答案时间:2017-12-28




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





2017-12-08 好不容易写出了快排的递归形式,给大家参考下
嫩岩



弄了一个上午,把快速排序写成递归的形式。感觉自己懂了点递归算法。
package container;

import java.util.ArrayList;
import java.util.Arrays;

public class Quick implements Sortinter {
	public int[] value;

	@Override
	public void sort(int[] shuzu) {
		value = Arrays.copyOf(shuzu, shuzu.length);
		ArrayList<Integer> sorted = new ArrayList<>();
		sorted = quicksort(value);
		for (int i = 0; i < sorted.size(); i++) {
			value[i] = sorted.get(i);
		}
	}

	private static ArrayList<Integer> quicksort(int[] value2) {
		ArrayList<Integer> myvalue = new ArrayList<>();
		if (value2.length <= 2) {
			if (value2[0] > value2[value2.length - 1]) {
				int t = value2[0];
				value2[0] = value2[1];
				value2[1] = t;
			}
			for (int i = 0; i < value2.length; i++) {
				myvalue.add(value2[i]);
			}
			return myvalue;
		} else {
			int j = clsort(value2);
			if (0 == j)
				j++;
			int left[] = Arrays.copyOfRange(value2, 0, j);
			int right[] = Arrays.copyOfRange(value2, j, value2.length);
			myvalue.addAll(quicksort(left));
			myvalue.addAll(quicksort(right));
		}
		return myvalue;
	}

	private static int clsort(int[] value2) {
		int i, j, base;
		base = value2[0];
		i = 1;
		j = value2.length - 1;
		while (i < j) {
			while (j > i && value2[j] >= base) {
				j--;
			}
			while (i < j && value2[i] <= base) {
				i++;
			}
			if (i < j) {
				int t = value2[i];
				value2[i] = value2[j];
				value2[j] = t;
			} else {
				if (value2[0] > value2[j]) {
					int t = value2[0];
					value2[0] = value2[j];
					value2[j] = t;
				} else {
					j = 0;
				}
			}
		}
		return j;

	}

	@Override
	public int[] sortedarray() {
		// TODO Auto-generated method stub
		return value;
	}

	public static void main(String[] args) {
		int testarray[] = new int[10];
		for (int i = 0; i < testarray.length; i++)
			testarray[i] = (int) (Math.random() * 5);
		System.out.println(Arrays.toString(testarray));
		ArrayList<Integer> rslt = quicksort(testarray);
		for (int i = 0; i < testarray.length; i++) {
			System.out.println(rslt.get(i));
		}
	}

}

							






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





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个

上传截图