0x01 线性数据结构

线性数据结构是计算机组织数据的一种方式

  • 线性结构是一个数据元素集合

    • 有一个唯一的首元素
    • 有一个唯一的尾元素
    • 除了首元素和尾元素,所有的元素都有一个唯一的先驱
    • 除了首元素和尾元素,所有的元素都有一个唯一的后继

常见的线性数据结构有:数组、栈、队列、链表等

数组

Python语言没有提供数组数据类型,通常使用列表作为数组。

  • 栈(Stack)是一种特殊的列表

    • 栈内元素只能通过列表的一端访问
    • 栈是后进先出的数据结构
  • 栈的核心操作

    • 入栈(push)
    • 出栈(pop)
  • 栈的实现
    Python列表从最后的位置添加和移除元素都非常高效,可天然地实现栈的操作

    • 列表的append()方法对应入栈操作(push)
    • 列表的pop()方法对应出栈操作(pop)
    list = []
    list.append(1)
    list.append(2)
    print(list)
    # [1,2]
    list.pop
    print(list)
    # [1]

队列

  • 队列(Quene)也是一种特殊的列表

    • 队列插入元素只能从队尾进行
    • 队列删除元素只能在队首进行
    • 队列是先进先出的数据结构
  • 队列的核心操作

    • 尾部添加
    • 首部删除
  • 队列的实现
    队列用列表实现并不适合(在首部添加数据只能用insert方法需要移动其他数据),collections.deque是Python提供的双端队列,支持从任一端添加删除数据,速度快

    #deque支持的方法
    append(x) # 尾部添加元素
    appendleft(x) # 首部添加元素
    pop() # 尾部弹出元素
    popleft() # 首部弹出元素
    clear() # 清空队列
    reverse() # 反转队列
  1. collections import deque
  2. = deque()
    dq.append(1)
    dq.append(2)
    print(dq)
    # deque([1,2])
    dq.popleft()
    # deque([2])
    dq.popleft()
    # deque([])

0x02 树的概念

树不是一种线性结构,是非线性的,树在计算机科学里应用广泛,包括操作系统、图形学、数据库和计算机网络等。

树的术语

  • 节点(Node)
    树中每一个数据元素称为一个节点,节点是树的基本构成部分。
  • 边(Edge)
    边也是树的基本构成部分。边有方向,链接两个节点,并表示两个之间的联系。

除了根节点外每个节点都有且只有一条与其他节点相连的入边(指向该节点的边),每个节点可能有许多条出边(从该节点指向其他节点的边)

  • 根节点(Root)
    根节点是树中唯一一个没有入边的节点
  • 路径(Path)
    路径是由边连接起来的节点的有序排列。
  • 子节点集(Children)
    当一个节点的入边来自另一个节点时,称前者是后者的子节点,同一个节点的所有子节点构成子节点集。
  • 父节点(Parent)
    一个节点是它出边所连接所有节点的父节点
  • 兄弟节点(Sibling)
    同一个节点的所有子节点互为兄弟节点
  • 子树(Subtree)
    子树是一个父节点的某个子节点的所有边和后代节点所构成的集合
  • 叶节点(Leaf Node)
    没有子节点的节点称为叶节点
  • 层数(Level)
    一个节点的层数是指从根节点到该节点的路径中的边的数目
  • 高度(Height)
    树的高度等于所有节点的层数的最大值

树的定义

树是节点和连接节点的边的集合,它有以下特征:

  • 有一个节点被设计为根节点
  • 除了根节点,每个节点都通过一条边与它唯一的父节点相连接
  • 可以沿着唯一的路径从根节点到每个节点
  • 如果这个树的每个节点都至多有两个子节点,称为二叉树

0x03 二叉树

二叉树的定义

  • 二叉树是由n(n≥0)个结点组成的有限集合、每个结点最多有两个子树的有序树。它或者是空集,或者是一个根和称为左、右子树的两个不相交的二叉树组成。
  • 结点的度和树的度
    每个结点具有的子树个数称为结点的度,树中所有结点的度的最大值称为树的度
  • 二叉树的度为2

二叉树的特点

  • 二叉树是有序树,即使只有一个子树,也必须区分左、右子树;
  • 二叉树每个结点的度不能大于2,只能取0、1、2三者之一
  • 二叉树所有结点的形态有五种:空结点、无左右子树的结点、只有左子树的结点、只有右子树的结点和具有左右子树的结点

二叉树的性质

  • 二叉树的第i层至多拥有2^i-1个结点
  • 对任何一棵二叉树T,如果其叶结点数为N0,度为2的结点数为N2,则N0=N2-1
  • 满二叉树:当树中每一层都满时,则称此树为满二叉树。
  • 完全二叉树:在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是右边缺少连续的若干个结点,则称此树为完全二叉树
  • 满二叉树是完全二叉树的特例
  • 深度为h的满二叉树的结点数为2^h-1

二叉树的遍历

按照一定次序访问树中的所有结点,并且每个结点的值仅被访问一次的过程

  • 可能的三种遍历次序

    • 先序遍历:首先访问根结点然后遍历左子树,最后遍历右子树
    • 中序遍历:中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树
    • 后序遍历:首先遍历左子树,然后遍历右子树,最后访问根结点

Last modification:March 26th, 2020 at 12:37 am