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

开发者社区> 人工智能> 正文

数据结构和算法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

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

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章