详解 二叉排序树的使用以及理解

  

前言:

     二叉排序树是当今唯一一种只用一个循环就能进行排序的算法,在java程序中用的循环越少,那么执行的时间越短,速度越快,这个我在上一次已经讲过了，具体内容请移步   作者 amor

     二叉排序树，那么肯定会用到树的概念，那么我们先扫扫盲，讲讲树的理论。

     一、树状结构

      如图

     

      上图显示的就是一个简单的树状结构,N2该节点有两个子节点，N0表示该节点没有子节点

概念：

度：度你也可以说是节点，如图中1，2，3 表的的就是度

二叉树：一个度小于等于二的数为二叉树 ，也就是说，1号节点只能有2，3两个节点，2号3号节点也只能有小于等于二个节点的树

深度(或者所高度)：树的最大层数  如图的树为三层

有数二叉树：如果一个树通过中根遍历得到一个有序的数就叫有序二叉树  这个后面会重点讲

  ......

 

树的三大性质：

1. 高度为h的二叉树，节点最多为 =2的h次方 -1

2. 第i层最大的节点个数为=2的i-1次方

3. N0=N2+1  解释:N0的个数等于N2的个数+1

 

树的遍历方法

图：

 

1．先根遍历    遍历顺序-->根左右  对应 2—1—3  根在前面  

2．中根遍历    遍历顺序-->左根右  对应 1—2—3  根在中间 ，中根遍历可以遍历数组

3．后根遍历    遍历顺序-->左右根  对应 1—3—2  根在后面

 

 

 

其实树的概念很多很多，在这儿我主要是想讲讲它的使用，所以也就不过多的列举，下面来说说使用

 

首先，我们定义一个树的节点

 

1. //树节点定义 
2.  
3. public class TreeNode { 
4.  
5. int data; 
6.  
7.     //定义树的左右节点 
8.  
9. TreeNode left; 
10.  
11. TreeNode right; 
12.  
13. public TreeNode(int data) { 
14.  
15. this.data = data; 
16.  
17. //当新建一个数的时候，没有左右节点，所以设置为null 
18.  
19. left=null; 
20.  
21. right=null; 
22.  
23. }    
24.  
25. } 

保存为 TreeNode .java

 

然后新建一个二叉排序法.java 文件实现排序

 

 

1. public class 二叉排序法 { 
2.  
3. //中根遍历法 
4.  
5. static int k=0; 
6.  
7. public static void mid_root(TreeNode root,int[] a){ 
8.  
9. //访问left节点(左子树) 
10.  
11. //有left才访问 
12.  
13. if(root.left!=null){ 
14.  
15. mid_root(root.left,a); 
16.  
17. } 
18.  
19. //存回数组,如果不存回数组，那么原数组将不会改变，所以这一步不能遗漏 
20.  
21. a[k++]=root.data;  //相当于：a[k]=root.data;  k++; 
22.  
23. //访问右子树(right) 
24.  
25. if(root.right!=null){ 
26.  
27. mid_root(root.right,a); 
28.  
29. } 
30.  
31. } 
32.  
33. //这儿是对树的一个位置摆放 
34.  
35. public static void sort_tree(TreeNode root,TreeNode in){ 
36.  
37. //比大小，决定in放在左边还是右边 
38.  
39. if(root.data>in.data){ 
40.  
41. //左边 
42.  
43. if(root.left==null) 
44.  
45. root.left=in; 
46.  
47. else 
48.  
49. sort_tree(root.left, in); 
50.  
51. }else{ 
52.  
53. //右边 
54.  
55. if(root.right==null) 
56.  
57. root.right=in; 
58.  
59. else 
60.  
61. sort_tree(root.right, in); 
62.  
63. } 
64.  
65. } 
66.  
67. public static void main(String[] args) { 
68.  
69. int[] a={
    5,1,8,4,2,7,3,6,9}; 
70.  
71.     //有些朋友，在看下面一句的时候，以为放的是一个数组，当时在TreeNode中并没//有定义这样的一个构造方法，其实，a[0] 表示的是一个int类型的数a[0]=5 
72.  
73. //给树一个根节点     
74.  
75. TreeNode root=new TreeNode(a[0]); 
76.  
77. for(int i=1;i<a.length;i++){ 
78.  
79. TreeNode in=new TreeNode(a[i]); 
80.  
81. sort_tree(root, in); 
82.  
83. } 
84.  
85. //调用排序的算法 
86.  
87. mid_root(root,a); 
88.  
89. for(int i=0;i<a.length;i++) 
90.  
91. System.out.print(a[i]+"-"); 
92.  
93. } 
94.  
95. } 

 

 

通过上面的调用，我们就知道实现了对一个数组只用一个循环来实现。

 

后记：

  浅谈一下二叉树排序的优缺点

  首先优点：很显然，二叉树排序只是使用了一个循环，那么在执行速度上比起冒泡，快速排序等等快的多，在时间上很占优势。 但是缺点，二叉树排序会消耗较多的内存，在内存中构建一个数，然后排序。所以根据不同的条件，会选用不同的方法，例如，别人的服务器是2G，那么我搞一个200G的内存，那么我肯定是选用二叉排序，以追求最大的速度。 但是我们仍然肯定二叉排序时一个好的算法。 

 

声明：此文仅仅是和大家分享自己所知道的，其中有一部分概念不准确也请大家多多谅解，指出批评，谢谢。也欢迎你光临我的博客   

  

作者amor