数据结构-树(4)

上一章我们讲解了二叉树的创建和遍历,这一章就可以放开手脚大干一场了

线索二叉树

什么是线索二叉树:二叉链表中有2n个指针域,其中n+1个指针域存放的都是NULL,我们要把这些指针域利用起来,存放节点的前驱和后继。

用处:对二叉树遍历的过程实质上是对一个非线性结构进行线性化的操作,以二叉链表为存储结构时,结点的左右孩子可以直接找到,但不能直接找到结点的前驱和后继,而结点的前驱和后继只有在遍历二叉树的过程中才能得到,效率低下。在后面的中序查找和平衡二叉树中会非常有用。

结点结构

我们在原有节点的基础上又添加了LeftThread和RightThread两个标志位,因为我们需要区分每个节点的指针域内的指针究竟是指向它的孩子还是指向它的前驱或者后继。虽然增加了空间,但是减少了时间

LeftThread=0, LeftChild指向左孩子
LeftThread=1, LeftChild指向前驱
RightThread=0, RightChild指向右孩子
RightThread=1, RightChild指向后继

//
typedef enum {Link,Thread} PointerTag;

typedef struct Node
{
    char val;
    struct Node *lChild,*rChild;
    PointerTag lThread = Link,rThread = Link;//c11标准才允许初始化
} BiTreeNode,*BiTree;
//

 

二叉树线索化

不同的遍历顺序,每个节点的前驱和后继自然也不一样

中序线索化二叉树

后继:结点标志为1时,其右指针为其后继;结点标志为0时,其右子树最左下结点为其后继。
前驱:结点标志为1时,其左指针为其前驱;结点标志为0时,其左子树最右下结点为其前驱。

//
//pre是一个全局变量,时刻指向当前节点的前驱元素
void inThreadBiTree(BiTree T)
{
    if(T == NULL) return;//空树返回


//中序线索化左子树
    if(T->lChild)//可以不加,前面有判空
        inThredBiTree(T->lChild);



//线索化根节点
    if(!T->lChild)//该节点如果左孩子为NULL
    {
        T->lThread = Thread;//更改标志位
        T->lChild = pre;//左指针指向前驱元素
    }
    if(!pre->rChild)//如果前驱元素的右孩子为NULL
    {
        pre->rThread = Thread;//更改标志位
        pre->rChild = T;//右孩子指向后继元素
    }
    pre = T;//该节点成为下一个节点的前驱元素



//中序线索化右子树
    if(T->rChild)
        inThreadBiTree(T->rChild);
}
//

我们根据下图来看一下上面代码的思路,中序线索化和中序遍历思路一样一样的,我们其实只需要修改中序遍历中的visit也就是访问函数即可,具体来看一下 继续阅读

数据结构-树(3)

二叉树的存储结构

第一篇博客里已经大概讲述了一下连续存储和顺序存储,下面我们再来具体看一下

链式存储

对于二叉树来说,每个节点的度都小于等于二,所以我们在定义节点时并不会造成大量的浪费,我们完全可以用链式结构来存储,同时类比单链表和双向链表,我们可以添加一个指针域来指向它的父节点

//
typedef struct Node{
    char val;
    struct Node *lChid,*rChild;
}BiTreeNode,*BiTree;
//

 

同样类比静态链表,三叉链表也有静态形式

 

连续存储

第一篇博客里讲到了如果要连续存储一棵树需要把它转换成完全二叉树,可以是从普通二叉树转化而来,也可以是一颗普通的树通过孩子兄弟表示法转化成的二叉树转化而来 继续阅读

数据结构-树(2)

树的存储

树中的每个节点之间都有着不同的关系,如双亲,孩子,兄弟等等,我们在存储一棵树的同时也要把他们之间的关系存储进去。下面我们就要介绍四种表示方法:孩子表示法  双亲表示法   双亲孩子表示法   孩子兄弟表示法

孩子表示法

顾名思义,孩子表示法就是在每一个节点中都包含了它的孩子的信息。比如孩子的地址或者下标。

对于所有的树来说,我们都可以用链式存储,但是我们在定义节点的时候会遇到一个问题,这个节点中我们究竟需要几个指针域?一种方法就是,遍历整棵树,求出最大的度,(不知道度的看上一章),在定义节点的时候定义同样数量的的指针域,但是很明显这样会造成大量浪费。

 

同样我们可以用静态链表,也就是数组的方式来表示,但同样也会造成大量浪费,那有没有什么好的办法呢?当然有,有这么一种看着就很牛逼的方法,数组和链表相结合,虽然也有浪费,但是其实浪费是很少的

数据结构=个体+个体关系,我们要对给定的数据进行存储,其实就是存储这两部分,个体和他们之间的关系,我们把每一个个体存放到数组中,同时又对每一个个体添加了一个链表,来存放它和其它个体的关系,也就是存放它的孩子的下标。

继续阅读

数据结构-链表(2)

约瑟夫问题

n 个人围成一个圆圈,首先第1个人从1开始一个人一个人顺时针报数, 报到第m个人,令其出列。然后再从下一个人开始,从1顺时针报数,报到第m个人,再令其出列,…,如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。
例如 n = 8 m = 3

对于这个问题我们用完全可以用循环队列来解决,但是这里我们为了加深一下对链表的操作,我们来用单循环链表来解决。很好类比,单循环链表也是一个圈,我们完全可以用它来模拟这个队伍。

定义结点、

//
typedef struct Node
{
    int data;
    struct Node* pNext;
} Node,*PNODE;
//

为了还原,这里我就没有添加头结点,同时也避免了循环时对头结点的判断,避免了产生与普通数据结点不同的操作,保证所有结点都一样,操作没有差别。

继续阅读

数据结构-链表(1)

定义

链表是线性表的链接存储方式,相比于数组的连续存储

既然说到了线性表就来简单介绍一下,以便和后面的树,图等非线性结构区分开来

同一线性表中元素具有相同特性。
相邻数据元素之间存在序偶关系。
除第一个元素外,其他每一个元素有一个且仅有一个直接前驱元素。
除最后一个元素外,其他每一个元素有一个且仅有一个直接后继元素。

优缺点

优点

对于插入和删除元素,数组的时间复杂度为O(n),而链表为O(1)
链表长度可变,而数组长度不可变

缺点

按序号查找时,数组可以随机访问,时间复杂度为O(1),而链表不支持随机访问,时间复杂度为O(n)
存储密度(结点数据本身所占的存储量/结点结构所占的存储总量)<1
需要动态申请管理内存,处理不当会造成内存泄漏

分类

单链表
静态链表
循环链表
双向链表

专业术语

头节点:第一个有效节点之前的节点数据域不存放数据加头节点的目的主要是方便对链表的操作
首节点:第一个存放数据的节点
尾节点:最后一个存放数据的节点
头指针:指向头节点的指针
尾指针:指向尾节点的指针

继续阅读

数据结构-树(1)

这是一篇讲述概念的博客,但是如果你能看完,那么恭喜你,你已经知道什么是树了

定义:有且只有一个称为根的节点,有若干个互不相交的子树,这些子树本身也是一棵树。通俗来讲树就是由节点和边组成,一个节点只能有一个父节点,但是可以有多个子节点。根节点没有父节点。

专业术语:

  • 度:节点拥有的子树的个数。如1的度为3;4的度为0
  • 路径:从一个节点顺着边走到另一个节点,所经过的节点的顺序就叫做路径
  • 叶节点:没有子节点的节点称为叶子节点(度为零),简称叶节点,也叫终端节点如4,5,6,7
  • 非叶节点(非终端节点):度不为0
  • 双亲:父节点
  • 子孙:以该节点为根节点的所有节点,如:除了1之外都是1的子孙
  • 兄弟:有相同的的父节点,如:5,6
  • 堂兄弟:父节点是兄弟,如:5和7,6和7
  • 深度:从根节点到最底层节点的层数称为深度,根节点是第一层,深度也叫最大层次,或者高。如:该树深度为3

继续阅读

排序

稳定排序:当两个元素相同时,排序后这两个元素相对位置不变则称为稳定排序,我们一般需要的都是稳定排序

排序和查找的关系:排序是搜索的前提,排序是重点

五种最常见的排序

冒泡排序
选择排序
插入排序
快速排序
归并排序

快速排序

以下gif来自该视频,虽然是java,但是讲的很棒bilibili
我们假设有一个队人,要让他们按照从小到大排队站好,我们可以这样做,先让最左边的人当作基准点,把队伍分成比他高的和比他矮的两部分这样56号的位置已经确定了,我们先看他的左边,是比他矮的小队,我们依然是让最左边的当作基准点,也就是8号,针对于它的小队,不再是全体小队,让比八号矮的站到他的左边,高的站到他的右边。

完成之后我们再对56号右边的小队进行同样的操作,其实就是递归

我们来看看每个元素的归位顺序

我们来看一下快排的伪算法

//
quickSort(int* arr,int left, int right)
//这里的left和right参数表示对一个闭区间内的元素进行排序
{
   如果left >= right 排序结束

   基准点为arr[left]
   
   把小的放到左边,大的放到右边//重点实现部分

   对左边队伍再次进行快排
  
   对右边队伍再次进行快排
}

接下来我们就看一下如何实现,我们先定义两个变量i和j分别指向头部和尾部,我们先让j向左移动,直到遇到一个比p也就是基准点小的值,停止移动,我们再让i向右移动,直到遇到一个比p大的值停止移动,然后交换i和j的值

交换之后我们继续让j移动,直到遇到比p小的值,再让i移动,直到遇到比p大的值,交换 当最后i和j相等时,i的左边就是比p小的,i的右边就是比p大的,我们就可以把i和p交换位置上代码

//快排
void quickSort(int* arr,int left,int right)
{
    if(left >= right)
        return;
    //把最左边的定为基准点
    int p = arr[left];

    //把大的放到基准点右边,小的放到基准点左边
    int i = left,j = right;
    while(j > i)
    {
        //j向左移找到一个比p小的元素
        while(arr[j]>=p && j>i)
            j--;
        //i向右移找到一个比p大的元素
        while(arr[i]<=p&&j>i)
            i++;
        int temp = arr[i];
        arr[i] =arr[j];
        arr[j] = temp;
    }
    
    //把基准点与i交换
    if(i<j)
    {
       arr[left] = arr[i];
       arr[i] = p;
    }
    
    //对左右两队再进行快排
    quickSort(arr,left,i-1);
    quickSort(arr,i+1,right);

}
int a[5] {2,4,1,5,7};

quickSort(a,0,4);

for(int i = 0; i<5 ; ++i)
{
    cout << a[i];
}
/*输出
12457
*/
  • 还有一种写法,只有一点微小的差别

在寻找基准点位置的时候我们先让j向左移,再让i向右移,最后交换i,j元素,我们也可以在j找到一个比p小的元素后就将他赋值个i,当i找到一个大于p的值的时候就赋值给j,最开始i就是基准点,赋值给了p,所以i的位置实际上已经空出来了,当把j赋值给i时,这个空被填上了,但是j又空了出来,这就是一个不断填坑的过程

//
 while(j > i)
    {
        //j向左移找到一个比p小的元素
        while(arr[j]>=p && j>i)
            j--;
        aar[i] = arr[j];
        //i向右移找到一个比p大的元素
        while(arr[i]<=p&&j>i)
            i++;
        arr[j] = arr[i];
   }
  •  同样当你想用其它位置的数来做基准点也很简单,只要你把它和第一位交换就可以了

    有问题欢迎大家提问哦0。0 可以直接评论😂 也可以QQ🤣

递归(1)汉诺塔

递归是什么

递归就是自己调用自己,我们再来看看函数调用是怎么回事

     当一个函数在运行期间调用另一个函数,运行在被调用函数之前系统需要将被调函数所有的参数,返回地址等传递给被调函数,为被调函数在内存中分配空间,同时将控制转移到被调函数入口
从被调函数返回主函数之前,系统要保存被调函数的返回结果,释放被调函数所占的内存空间,依照地址返回调用函数继续执行、

     当有多个函数互相调用时,如a函数调用了b,b又调用了c,按照后调用先执行的原则,实际上就是栈结构,最后调用的函数处于栈顶,每调用一个函数,就在栈顶分配一块内存空间,每当一个函数执行完毕就会进行出栈操作释放空间,而递归最常出现的问题就是爆栈和超时,著名的StackOverflow.com也是由此而来。

其实对于计算机来说,a调用b 和 a调用a并没有什么不同

递归必须要满足的三个条件

1.递归必须有明确的终止条件,且一定在某一时刻可以满足该条件
2.该函数所处理的数据规模在递减(递归的思想是把问题分解成为规模更小且与原问题有着相同解法的问题
3.这个转化必须是可解的(其实有好多时候,这个问题能不能用递归,该怎么用是个数学问题)

汉诺塔

  • 直接来看一下汉诺塔的伪算法
//
if(n > 1)
{
   将n-1个盘子借助C移动到B
   将第n个盘子移动到C
   将n-1个盘子借助A移动到C
}
  • 上代码
    //
    void fun(int n,char a,char b,char c)
    {
        if(n == 1)
        {
            printf("把第%d个盘子从%c移到%c\n",n,a,c);
        }
        else{
            fun(n-1,a,c,b);
            printf("把第%d个盘子从%c移到%c\n",n,a,c);
            fun(n-1,b,a,c);
        }
    }
    
    int main()
    {
        fun(3,'a','b','c');
        return 0;
    }
    /*输出
    把第1个盘子从a移到c
    把第2个盘子从a移到b
    把第1个盘子从c移到b
    把第3个盘子从a移到c
    把第1个盘子从b移到a
    把第2个盘子从b移到c
    把第1个盘子从a移到c
    */

    唯一需要注意就是这个函数的后三个参数,第一个表示的是当前盘子在哪,第二个表示的是用作辅助的柱子,第三个是目标柱子

  • 并没有深入探讨如何优化递归和太多算法的问题,只是简单的用汉诺塔来说明了递归的使用方法,因为有些问题只能用递归来解决,同时在数据结构中将会有大量使用递归的地方另一个用到递归的问题快速排序
  • 有问题欢迎大家提问哦0。0 可以直接评论😂 也可以QQ🤣