Chinaunix首页 | 论坛 | 博客
  • 博客访问: 862803
  • 博文数量: 156
  • 博客积分: 6553
  • 博客等级: 准将
  • 技术积分: 3965
  • 用 户 组: 普通用户
  • 注册时间: 2010-06-22 18:36
文章存档

2012年(3)

2011年(43)

2010年(110)

分类: C/C++

2010-11-17 19:15:07

若设二叉树的高度为h,除第 h 层外,其它各层 (1h-1) 的结点数都达到最大个数,第 h 层所有的节点都连续集中在最左边,这就是完全二叉树。

 

性质:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1
性质四 具有n个结点的完全二叉树的深度为「log2n+1

 

查找:

1.       顺序查找

a)         算法简单,适应面广,稳定算法

b)        平均查找长度比较大,当n比较大时,查找效率会很低,时间复杂度为O(n)

2.       折半查找法

a)         针对有序的序列表,不稳定算法

b)        查找速度快,时间复杂度是O(log2n)

3         分块查找

a)         也是针对有序表,不稳定算法

b)        查找速度介于顺序查找和折半查找之间

 

树表查找:

1.    二叉查找树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。

2.    平衡二叉树:棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树,查找时间的时间复杂度为O(log2n)

 

排序:

 

排序分类     平均时间       时间复杂度       辅助存储空间

简单排序     O(n2)           O(n2)            O(1)

快速排序     O(nlog2n)       O(nlog2n)         O(nlog2n)

堆排序       O(nlog2n)       O(nlog2n)         O(1)

归并排序     O(nlog2n)       O(nlog2n)         O(n)

 

从平均时间来讲,快速排序是最快的,但是在最坏的情况下,它的时间复杂度(为O(n2))就不如堆排序和归并排序,归并排序所需时间比堆排序省,但是它需要辅助空间,从方法的稳定性来讲,归并排序是一种稳定排序,快速排序和堆排序都是不稳定的。

 

阅读(23369) | 评论(1) | 转发(1) |
0

上一篇:死锁

下一篇:区分文本流和二进制流

给主人留下些什么吧!~~

chinaunix网友2010-11-18 17:19:06

很好的, 收藏了 推荐一个博客,提供很多免费软件编程电子书下载: http://free-ebooks.appspot.com