数据结构算法学习笔记(一)

数据结构算法学习笔记(一)

一、树

树的储存结构分3种

  1. 双亲表示法
    根结点外,其余每个结点,它不一定有孩子,但是一定有且仅有一个双亲。我们假设以一组连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点在数组中的位置。也就是说,每个结点除了知道自己是谁以外,还知道它的双亲在哪里
    以下是我们的双亲表示法的结点结构定义代码。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    /* 树的双亲表示法结点结构定义 */
    define MAX_TREE_SIZE 100
    /* 树结点的数据类型,目前暂定为整型 */
    typedef int TElemType;
    /* 结点结构 */
    typedef struct PTNode
    {
    /* 结点数据 */
    TElemType data;
    /* 双亲位置 */
    int parent;
    } PTNode;
    /* 树结构 */
    typedef struct
    {
    /* 结点数组 */
    PTNode nodes[MAX_TREE_SIZE];
    /* 根的位置和结点数 */
    int r, n;
    } PTree;

    在此基础上我们可以改进下树的结构,增加一个结点最左边孩子的域,不妨叫它长子域,这样就可以很容易得到结点的孩子。如果没有孩子的结点,这个长子域就设置为-1,如下表格

  2. 孩子表示法
    换一种完全不同的考虑方法。由于树中每个结点可能有多棵子树,可以考虑用多重链表,即每个结点有多个指针域,其中每个指针指向一棵子树的根结点,我们把这种方法叫做多重链表表示法。不过,树的每个结点的度,也就是它的孩子个数是不同的。所以可以设计两种方案来解决

    我们为了要遍历整棵树,把每个结点放到一个顺序存储结构的数组中是合理的,但每个结点的孩子有多少是不确定的,所以我们再对每个结点的孩子建立一个单链表体现它们的关系

    这就是我们要讲的孩子表示法。具体办法是,把每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中

  3. 孩子兄弟表示法
    刚才我们分别从双亲的角度和从孩子的角度研究树的存储结构,如果我们从树结点的兄弟的角度考虑又会如何呢?当然,对于树这样的层级结构来说,只研究结点的兄弟是不行的,我们观察后发现,任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟。


二、二叉树

二叉树特点

  • 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点。注意不是只有两棵子树,而是最多有。没有子树或者有一棵子树都是可以的。
  • 左子树和右子树是有顺序的,次序不能任意颠倒。就像人有双手、双脚,但显然左手、左脚和右手、右脚是不一样的,右手戴左手套、右脚穿左鞋都会极其别扭和难受。
  • 即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。图6-5-3中,树1和树2是同一棵树,但它们却是不同的二叉树。就好像你一不小心,摔伤了手,伤的是左手还是右手,对你的生活影响度是完全不同的。

二叉树分类:

  1. 斜树:斜树一定要是斜的,但是往哪斜还是有讲究。所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。斜树有很明显的特点,就是每一层都只有一个结点,结点的个数与二叉树的深度相同。
  2. 满二叉树:在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。

    单是每个结点都存在左右子树,不能算是满二叉树,还必须要所有的叶子都在同一层上,这就做到了整棵树的平衡。

    满二叉树具有以下特点:

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

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

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

      上图只有图1、3是完全二叉树

二叉树性质

  1. 在二叉树的第i层上至多有2i-1个结点(i≥1)
  2. 深度为k的二叉树至多有2k-1个结点(k≥1)
  3. 对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1
  4. 具有n个结点的完全二叉树的深度为|log2n+1|(|x|表示不大于x的最大整数,由性质2反推
  5. 如果对一棵有n个结点的完全二叉树(其深度为)的结点按层序编号(从第1层到第层,每层从左到右),对任一结点i(1≤i≤n)有:

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

    我们以下图为例,来理解这个性质。这是一个完全二叉树,深度为4,结点总数是10。

    对于第一条来说是很显然的,i=1时就是根结点。i>1时,比如结点7,它的双亲就是,结点9,它的双亲就是。

    第二条,比如结点6,因为2×6=12超过了结点总数10,所以结点6无左孩子,它是叶子结点。同样,而结点5,因为2×5=10正好是结点总数10,所以它的左孩子是结点10。

    第三条,比如结点5,因为2×5+1=11,大于结点总数10,所以它无右孩子。而结点3,因为2×3+1=7小于10,所以它的右孩子是结点7。


二叉树存储结构

  1. 二叉树顺序存储结构
  2. 二叉链表

二叉树遍历

  1. 前序遍历

    规则是若二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树

  2. 中序遍历

    规则是若树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点),中序遍历根结点的左子树,然后是访问根结点,最后中序遍历右子树

  3. 后序遍历

    规则是若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后是访问根结点

  4. 层序遍历

    规则是若树为空,则空操作返回,否则从树的第一层,也就是根结点开始访问,从上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问

遍历算法

  1. 前序遍历
    二叉树的定义是用递归的方式,所以,实现遍历算法也可以采用递归,而且极其简洁明了。先来看看二叉树的前序遍历算法。代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    /* 二叉树的前序遍历递归算法 */
    void PreOrderTraverse(BiTree T)
    {
    if (T == NULL)
    return;
    /* 显示结点数据,可以更改为其他对结点操作 */
    printf("%c", T->data);
    /* 再先序遍历左子树 */
    PreOrderTraverse(T->lchild);
    /* 最后先序遍历右子树 */
    PreOrderTraverse(T->rchild);
    }
  2. 中序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    /* 二叉树的中序遍历递归算法 */
    void InOrderTraverse(BiTree T)
    {
    if (T == NULL)
    return;
    /* 中序遍历左子树 */
    InOrderTraverse(T->lchild);
    /* 显示结点数据,可以更改为其他对结点操作 */
    printf("%c", T->data);
    /* 最后中序遍历右子树 */
    InOrderTraverse(T->rchild);
    }

换句话说,它等于是把调用左孩子的递归函数提前了。

  1. 后序遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    /* 二叉树的后序遍历递归算法 */
    void PostOrderTraverse(BiTree T)
    {
    if (T == NULL)
    return;
    /* 先后序遍历左子树 */
    PostOrderTraverse(T->lchild);
    /* 再后序遍历右子树 */
    PostOrderTraverse(T->rchild);
    /* 显示结点数据,可以更改为其他对结点操作 */
    printf("%c", T->data);
    }

二叉树推倒遍历特性:

  • 已知前序遍历序列和中序遍历序列,可以唯一确定一棵二叉树
  • 已知后序遍历序列和中序遍历序列,可以唯一确定一棵二叉树

知道前序和后序遍历是无法唯一确定二叉树,为什么呢?
原因也很简单,比如前序序列是ABC,后序序列是CBA。我们可以确定A一定是根结点,但接下来,我们无法知道,哪个结点是左子树,哪个是右子树。这棵树可能有如图所示的四种可能。
多种可能


红黑树
定义

王洋 wechat
我的微信号,欢迎交流~

热评文章