总结---2

1.各种排序算法的时间复杂度和空间复杂度分析

  • 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,
  • 冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

排序法

平均时间

最差情形

稳定度

额外空间

备注

冒泡

O(n2)

O(n2)

稳定

O(1)

n小时较好

交换

O(n2)

O(n2)

不稳定

O(1)

n小时较好

选择

O(n2)

O(n2)

不稳定

O(1)

n小时较好

插入

O(n2)

O(n2)

稳定

O(1)

大部分已排序时较好

基数

O(logRB)

O(logRB)

稳定

O(n)

B是真数(0-9),R是基数(个十百)

Shell

O(nlogn)

O(ns) 1<s<2

不稳定

O(1)

s是所选分组

快速

O(nlogn)

O(n2)

不稳定

O(nlogn)

n大时较好

归并

O(nlogn)

O(nlogn)

稳定

O(1)

n大时较好

O(nlogn)

O(nlogn)

不稳定

O(1)

n大时较好

image.png

详细分析见:http://www.cnblogs.com/heyonggang/p/3356930.html

2.满二叉树

在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树

满二叉树的特点有:

  1. 叶子只能出现在最下一层。出现在其他层就不可能达到平衡。
  2. 非叶子结点的度一定是2 。 否则就是“缺胳膊少腿”了。
  3. 在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多。

3.完全二叉树

对一棵具有n个结点的二叉树按层序编号,如果编号为i(1≤i≤n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树

顺序存储结构一般只使用于完全二叉树。

完全二叉树的特点:

  1. 叶子结点只能出现在最下两层。
  2. 最下层的叶子一定集中在右部连续位置。
  3. 倒数第二层,若有叶子结点,一定都在右部连续位置。
  4. 如果结点度为1,则该结点只有左孩子,即不存在只有右子树的情况。
  5. 同样结点数的二叉树,完全二叉树的深度最小。

从这些特点可以得出一个判断是否是完全二叉树的方法:那就是看着树的示意图,心中默念给每个结点按照满二叉树的结构逐层顺序编号,如果编号出现空档,就说明不是完全二叉树,否则就是

4.二叉树性质

性质1:在二叉树的第i层上至多有2i-1个结点。

性质2:深度为k的二叉树至多有2k - 1个结点(k≥1)。

性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1 。

性质4:具有n个结点的完全二叉树的深度[log2n+1] ([x]表示不大于x的最大整数)。

性质5:如果对一棵有n个结点的完全二叉树(其深度为[log2n]+1)的结点按层序编号(从第1层到第[log2n]+1层,每层从左到右),对任一结点i(1≤i≤n)有:

  1. 如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是结点[i/2]。
  2. 如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i。
  3. 如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1 。

5.____的先序序列和后序序列正好相反。

A.二叉排序树                        B.3个结点的二叉树                C.平衡二叉树                       D.无右孩子的二叉树

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

每周学点大数据 | No.26外存数据结构——B 树

No.26期 外存数据结构——B 树 小可:看来在磁盘上二叉搜索树对新来的数据插入树中支持得不好,那么究竟怎么解决这个问题呢? Mr. 王:有一个非常经典的...

36670
来自专栏恰童鞋骚年

数据结构基础温故-4.树与二叉树(上)

前面所讨论的线性表元素之间都是一对一的关系,今天我们所看到的结构各元素之间却是一对多的关系。树在计算机中有着广泛的应用,甚至在计算机的日常使用中,也可以看到树形...

12230
来自专栏desperate633

LintCode N皇后问题题目分析代码

每个解决方案包含一个明确的n皇后放置布局,其中“Q”和“.”分别表示一个女王和一个空位置。

8720
来自专栏cmazxiaoma的架构师之路

Java数据结构与算法(3) 寻找中序遍历时的下一个结点

12630
来自专栏java一日一条

Calendar 详解

究竟什么是一个 Calendar 呢?中文的翻译就是日历,那我们立刻可以想到我们生活中有阳(公)历、阴(农)历之分。它们的区别在哪呢?

6510
来自专栏Petrichor的专栏

leetcode: 78. Subsets

11910
来自专栏java一日一条

Calendar 详解

究竟什么是一个 Calendar 呢?中文的翻译就是日历,那我们立刻可以想到我们生活中有阳(公)历、阴(农)历之分。它们的区别在哪呢?

9110
来自专栏大史住在大前端

野生前端的数据结构基础练习(7)——二叉树

一棵树最上面的点称为根节点,如果一个节点下面连接多个节点,那么该节点称为父节点,下面的节点称为子节点,二叉树的每一个节点最多有2个子节点,一个节点子节点的个数称...

9920
来自专栏青蛙要fly的专栏

Android技能树 — 树基础知识小结(一)

现在安卓面试,对于数据结构的问题也越来越多了,也经常看到别人发的面试题都是问什么红黑树,二叉树查找等,所以我们虽然不会马上就会各种难的面试题,但起码树的基础知识...

10330
来自专栏JavaEdge

二分查找复杂度分析

43850

扫码关注云+社区

领取腾讯云代金券