数据结构和算法15 之二叉树排序-阿里云开发者社区

开发者社区> shy丶gril> 正文

数据结构和算法15 之二叉树排序

简介:
+关注继续查看

 顾名思义,二叉树排序就是利用二叉搜索树的特点进行排序,前面提到过二叉搜索树的特点是,左子节点比自己小,右子节点比自己大,那么二叉树排序的思想就是先将待排序序列逐个添加到二叉搜索树中去,再通过中序遍历二叉搜索树就可以将数据从小到大取出来。如果对二叉树还不太了解,请看这篇博文:数据结构算法之二叉树 ,这里不再赘述。

下面我们来看看二叉树排序的实现:

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. public class Tree2Sort {  
  2.     private Node root;  
  3.     public Tree2Sort() {  
  4.         root = null;  
  5.     }  
  6.     public Node getRoot() {  
  7.         return root;  
  8.     }  
  9.     public void insertSort(int[] source) {  
  10.         for(int i = 0; i < source.length; i++) {  
  11.             int value = source[i];  
  12.             Node node = new Node(value);  
  13.             if(root == null) {  
  14.                 root = node;  
  15.             }  
  16.             else {  
  17.                 Node current = root;  
  18.                 Node parent;  
  19.                 boolean insertedOK = false;  
  20.                 while(!insertedOK) {  
  21.                     parent = current;  
  22.                     if(value < current.value) {  
  23.                         current = current.leftChild;  
  24.                         if(current == null) {  
  25.                             parent.leftChild = node;  
  26.                             insertedOK = true;  
  27.                         }  
  28.                     }  
  29.                     else {  
  30.                         current = current.rightChild;  
  31.                         if(current == null) {  
  32.                             parent.rightChild = node;  
  33.                             insertedOK = true;  
  34.                         }  
  35.                     }  
  36.                 }  
  37.                   
  38.             }  
  39.         }  
  40.     }  
  41.     //中序遍历  
  42.     public void inOrder(Node current) {  
  43.         if(current != null) {  
  44.             inOrder(current.leftChild);  
  45.             System.out.print(current.value + " ");  
  46.             inOrder(current.rightChild);  
  47.         }  
  48.     }  
  49. }  
  50. class Node {  
  51.     public int value;  
  52.     Node leftChild;  
  53.     Node rightChild;  
  54.     public Node(int val) {  
  55.         value = val;  
  56.     }  
  57. }  

        算法分析:二叉树的插入时间复杂度为O(logN),所以二叉树排序算法的时间复杂度为O(NlogN),但是二叉树排序跟归并排序一样,也需要额外的和待排序序列大小相同的存储空间。空间复杂度为O(N)。


转载:http://blog.csdn.net/eson_15/article/details/51193330

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
NOIP-C++大神培养计划 Step1.1.2基础算法——模拟算法2
大家好,我是小笨笨,今天我们继续来讲解模拟算法。 我们直接上例题! 栗1.1.2-1 洛谷P1014 Cantor表https://www.luogu.org/problemnew/show/P1014题目描述现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。
955 0
asp中的md5/sha1/sha256算法收集
对于asp这种古董级的技术,这年头想找一些有用的资料已经不容易了,下面是一些常用的加密算法: md5 (将以下代码另存为md5.inc) 31 Then Err.Raise 6 End If If (lValue And m_l2Power(31 ...
866 0
排序算法大数据量测试代码
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; using System.Diagnostics; using System.IO; namespace Sort { class Program
813 0
NOIP-C++大神培养计划Step1.1.1基础算法——模拟算法1
模拟算法,可以说是最基础的算法了。它的基本定义没太多意思:就是去模拟题目的要求。题意要你怎么做,你就怎么做,看懂了题目,基本上就会做了。 举一个大家耳熟能详的栗子。 A+B Problem给定两个整数A和B,输出他们的和。
1220 0
+关注
1878
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载