2022年2022年郝斌数据结构视频学习总结 .pdf

《2022年2022年郝斌数据结构视频学习总结 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年郝斌数据结构视频学习总结 .pdf（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构资料- 1 - 郝斌数据结构视频学习总结郝斌数据结构视频学习总结 . - 1 - 0 教材 . - 2 - 1 数据结构概述 . - 2 - 1.1、定义（研究是数据结构的存储和数据的操作的）. - 2 - 1.2、算法 . - 2 - 1.3、数据结构的地位 . - 2 - 2 预备知识 . - 3 - 2.1、指针 . - 3 - 2.2、结构体 . - 3 - 2.3、动态内存的分配和释放 . - 4 - 3 模块一：线性结构把所有的结点用一条直线穿起来 . - 5 - 3.1、连续存储 数组 . - 5 - 3.1.1 什么叫做数组 . - 5 - 3.1.2.数组的优缺点（相

2、对于链表）. - 5 - 3.2、离散存储 链表 . - 5 - 3.2.1.定义及专业术语 . - 5 - 3.2.2.分类 . - 6 - 3.2.3.算法（ typedef/动态分配内存实例） . - 6 - 3.2.4.链表的优缺点（相对于数组）. - 9 - 3.2.5.小结： . - 9 - 3.3、线性结构的两种常见应用之一栈. - 11 - 3.3.1.定义：一种可以实现“ 先进后出 ” 的存储结构 . - 11 - 3.3.2 分类 . - 11 - 3.3.3.算法 . - 11 - 3.3.4 应用 . - 11 - 3.3.5 栈操作代码 . - 11 - 3.4、线性

3、结构的两种常见应用之一队列 . - 15 - 3.4.1.定义：一种可以实现“ 先进先出 ” 的存储结构 . - 15 - 3.4.2.分类 . - 15 - 3.4.3.算法 . - 16 - 3.4.4 应用及代码 . - 16 - 3.5、专题：递归（使用栈实现的）. - 19 - 3.5.1.定义 :一个函数自己直接或间接调用自己. - 19 - 3.5.2.函数的调用前后的准备工作. - 19 - 3.5.3 递归必须满足的三个条件：. - 20 - 3.5.4.循环和递归之间的关系 . - 20 - 3.5.5.举例： . - 21 - 3.5.6.递归的应用 . - 23 - 4

4、 模块二：非线性结构 . - 23 - 4.1、树 . - 23 - 4.1.1.定义及专业术语 . - 23 - 4.1.2.分类 . - 24 - 4.1.3.存储（解决非线性结构用线性结构表示的问题）. - 25 - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 35 页 - - - - - - - - - 数据结构资料- 2 - 4.1.4 操作 (重点 ) . - 28 - 4.1.4 应用及代码 . - 31 - 4.2、图（视频中未讲解） . - 34 -

5、 5 模块三：查找和排序 . - 34 - 6、Java中容器和数据结构相关知识（视频中未讲解） . - 35 - 0 教材教材： 数据结构严蔚敏 吴伟民 清华大学出版社数据结构算法实现及解析高一凡 西安电子科技大学出版社1 数据结构概述1.1、定义（研究是数据结构的存储和数据的操作的）如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫做算法。数据结构= 个体的存储（从某个角度而言，可忽略）+ 个体与个体之间关系的存储（核心）算法 = 对存储

6、数据的操作1.2、算法解题的方法和步骤衡量算法的标准时间复杂度大概程序要执行的次数，而非执行的时间空间复杂度算法执行过程中大概所占用的最大内存难易程度（即可读性）健壮性1.3、数据结构的地位数据结构是软件中最核心的内容名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 35 页 - - - - - - - - - 数据结构资料- 3 - 程序 = 数据的存储+ 数据的操作+ 可以被计算机执行的语言2 预备知识2.1、指针指针的重要性：指针是C 语言的灵魂定义：地址：内存单元的

7、编号从零开始的非负整数范围： 0-FFFFFFFF（即 0-4G-1）指针：指针就是地址，地址就是指针指针变量是存放内存单元地址的变量指针的本质是一个操作受限的非负整数（只能进行减运算）分类：1.基本类型的指针2.指针和一维数组的关系2.2、结构体为什么会出现结构体为了表示一些复杂的数据，而普通的基本类型变量无法满足要求什么叫结构体结构体是用户根据实际需要自己定义的数据类型如何使用结构体两种方式：struct Student st = 1000, zhangsan, 20 struct Student * pst = &st; 1.st.sid 2.pst-sid pst 所指向的结构体变量中

8、的sid 这个成员注意事项名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 35 页 - - - - - - - - - 数据结构资料- 4 - 结构体变量不能加减乘除，但可以相互赋值普通结构体变量和结构体指针变量作为函数传参问题2.3、动态内存的分配和释放假设动态构造一个int 型的一位数组int len；int * pArr = (int *)malloc (sizeof(int) * len); 本语句分配了两块内存，一块内存是动态分配的，总共len 个字节；另一块是

9、静态分配的，是 pArr 变量本身所占的内存，总共4 个字节。malloc 只有一个 int 型的形参，表示要求系统分配的字节数malloc 函数的功能是请求系统分配len 个字节的内存空间， 如果分配成功， 则返回第一个字节的地址，如果分配不成功，则返回NULL malloc 函数能且只能返回第一个字节的地址，所以我们需要把这个无任何实际意义的第一个字节的地址（俗称干地址）转化为一个有实际意义的地址，因此，malloc 函数前面必须加强制类型转换（数据类型*） ，表示把这个无实际意义的第一个字节的地址转化为相应类型的地址。free（* pArr ）表示把 pArr 所指向的内存给释放掉pAr

10、r 本身的内存是静态的， 不能有程序员手动释放， 只能在 pArr 变量所在的函数运行终止时有系统自动释放跨函数使用内存静态内存不可以跨函数使用：静态内存在函数执行期间可以被其它函数使用静态内存在函数执行完毕之后就不能在被其它函数使用动态内存可以跨函数使用动态内存在函数执行完毕之后仍然可以被其它函数使用,除非使用 free（）方法释放动态非配的内存名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 35 页 - - - - - - - - - 数据结构资料- 5 - 3 模块

11、一：线性结构把所有的结点用一条直线穿起来 3.1、连续存储 数组 3.1.1 什么叫做数组元素类型相同，大小相等确定一个数组需要三个参数：数组大小，数组有效存储量，数组首地址3.1.2. 数组的优缺点（相对于链表）优点：存取速度快缺点：实现必须知道数组的长度需要大块连续的内存块插入和删除元素很慢空间通常是有限制的3.2、离散存储 链表 3.2.1. 定义及专业术语N 个结点离散分配彼此通过指针相连每个结点只有一个前驱结点，每个结点只有一个后续结点首结点没有前驱结点，尾结点没有后续结点专业术语：首结点：第一个存放有效数据的结点尾结点：最后一个存放有效数据的结点头结点：头结点的数据类型和首结点的类

12、型是一样的首结点之前的结点头结点并不存放有效数据加头结点的目的是为了方便对链表的操作头指针：指向头结点的指针变量尾指针：指向尾结点的指针变量名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 35 页 - - - - - - - - - 数据结构资料- 6 - 确定一个链表需要几个参数：（如果希望通过一个函数来对链表进行处理，我们至少需要接受链表的那些参数）只需要一个参数，即 头指针 ，因为我们通过头指针可以推算出链表的其它所有的信息typedef 为数据类型起别名：3.2.

13、2. 分类单链表双链表：每一个结点有两个指针域循环链表：能通过任何一个结点找到其它所有的结点非循环链表3.2.3. 算法（ typedef/ 动态分配内存实例）遍历 / 查找 / 清空 / 销毁 / 求长度 / 排序 / 删除结点/ 插入结点插入结点： (伪算法 ) r = p-pNext; p-pNext = q; q-pNext = r; q-pNext = p-pNext; p-pNext = q;(这两行代码不能倒过来 ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6

14、页，共 35 页 - - - - - - - - - 数据结构资料- 7 - 删除结点：（伪算法）r = p-pNext; p-pNext = p-pNext-pNext; free(r); /释放所删除结点的内存，因为C 中不能自动回收垃圾名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 35 页 - - - - - - - - - 数据结构资料- 8 - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名

15、师精心整理 - - - - - - - 第 8 页，共 35 页 - - - - - - - - - 数据结构资料- 9 - 排序: 3.2.4. 链表的优缺点（相对于数组）优点：空间没有限制插入和删除元素很快缺点：存取的速度很慢3.2.5. 小结：数据结构狭义：数据结构是专门研究数据存储的问题数据的存储包含两个方面：个体的存储+ 个体关系的存储广义：数据结构既包含数据的存储也包含数据的操作对存储数据的操作就是算法算法狭义：算法是和数据的存储方式密切相关广义：算法和数据的存储方式无关这就是泛型思想泛型：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -

16、 - - - - - 名师精心整理 - - - - - - - 第 9 页，共 35 页 - - - - - - - - - 数据结构资料- 10 - 利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的同一种逻辑结构（包括线性结构和非线性结构，其中非线性结构包括树和图），无论该逻辑结构物理存储（包括数组和链表）是什么样子的，我们都可以对它执行相同的操作数据的存储结构有几种线性：数组连续存储优点：存取速度很快缺点：事先必须知道数组的长度插入删除元素很慢空间通常是有限制的需要大块连续的内存块链表离散存储优点：空间没有限制插入、删除元素很快缺点：存取速度很慢线性结构的应用栈线性结构的应用

17、队列非线性：树图#include #include void f(int i) int m; double *q = (double *)malloc(sizeof(doule); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 35 页 - - - - - - - - - 数据结构资料- 11 - int main(void) int i=10; int * p = (int *) malloc(200) ；return 0; 3.3、线性结构的两种常见应用之一栈3.

18、3.1. 定义：一种可以实现 “ 先进后出 ” 的存储结构栈类似于箱子3.3.2 分类静态栈：以数组为内核动态栈：以链表为内核 (最常用 ) 3.3.3. 算法出栈 / 入栈3.3.4 应用函数调用/ 中断 / 表达式求值/内存分配/ 缓冲处理/ 迷宫3.3.5 栈操作代码名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 35 页 - - - - - - - - - 数据结构资料- 12 - /链式 动态栈#include #include #include typede

19、f struct Node int data; Node * pNext; NODE,*PNODE; typedef struct Stack PNODE pTop;/压入、弹出操作均在pTop一端进行PNODE pBottom;/不存储有效数据，仅仅作为记录STACK, *PSTACK; void init(PSTACK); void push(PSTACK,int); bool pop(PSTACK,int *); void clear(PSTACK); void travese(PSTACK); pTop pBottom 不 存 储 有效数据压 栈 、 出栈 均 在 此位置名师资料总结

20、- - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 35 页 - - - - - - - - - 数据结构资料- 13 - int main(void) STACK s; int val; init(&s); push(&s,1); push(&s,6); travese(&s); clear(&s); travese(&s); push(&s,2); push(&s,7); travese(&s); if(pop(&s,&val) printf(pop success! pop: %d

21、,val); printf(n); else printf(pop fail!) ; printf(n); travese(&s); return 0; /初始化栈void init(PSTACK pStack) PNODE pNew = (PNODE)malloc(sizeof(NODE); if(NULL = pNew) printf( 动态分配内存失败 ); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 35 页 - - - - - - - - - 数据结构资料

22、- 14 - pNew-pNext = NULL; pNew-data = -123456; pStack-pTop = pNew; pStack-pBottom = pNew; /压入操作void push(PSTACK pStack,int val) PNODE pNew = (PNODE)malloc(sizeof(NODE); pNew-data = val; pNew-pNext = pStack-pTop; pStack-pTop = pNew; /遍历操作void travese(PSTACK pStack) PNODE pRec = pStack-pTop;/ 遍历时不能改变

23、pTop的值。while(pRec != pStack-pBottom) printf(%d ,pRec-data); pRec = pRec-pNext; printf(n); /弹出操作bool pop(PSTACK pStack,int *pVal) if(pStack-pTop != pStack-pBottom) PNODE temp = pStack-pTop; *pVal = temp-data; pStack-pTop = temp-pNext; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

24、- - - - - - 第 14 页，共 35 页 - - - - - - - - - 数据结构资料- 15 - free(temp); return true; else return false; /清空操作void clear(PSTACK pStack) PNODE temp = NULL; while(pStack-pTop != pStack-pBottom) temp = pStack-pTop; pStack-pTop = temp-pNext; free(temp); 3.4、线性结构的两种常见应用之一队列3.4.1. 定义：一种可以实现 “ 先进先出 ” 的存储结构队列类似

25、于排队买票3.4.2. 分类链式队列- 用链表实现front(从这端出队 ) ，rear(从这端入队 ) 静态队列- 用数组实现静态队列通常都必须是循环队列循环队列的讲解：静态队列为什么必须是循环队列普通数组队列的参数front 和 rear只增不减，导致空余部分的内存浪费名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 35 页 - - - - - - - - - 数据结构资料- 16 - 循环队列需要几个参数来确定需要两个参数： front / rear 循环队列各个

26、参数的含义两个参数在不同的场合有不同的含义队列初始化front 和 rear 的值都为零队列非空front 代表的是队列的第一个元素rear 代表的是队列的最后一个有效元素的下一个元素队列空front 和 rear 的值相等，但不一定是零循环队列入队伪算法讲解(在尾部入队 ) 第一步：将值存入rear所指向的位置第二步： rear = (rear + 1)%数组的长度循环队列出队伪算法讲解（在头部出队）front = (front +1)% 数组的长度如何判断循环队列为空如果 front 与 rear的值相等，则该队列一定为空如何判断循环队列为满第一种方法：多增加一个标识参数，即数组的长度第二

27、种方法 （常用） ：少用一个元素，如果front = (rear + 1)%数组的长度，则循环队列已满3.4.3. 算法出队 / 入队3.4.4 应用及代码所有和时间有关的操作都有队列的影子#include #include 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 35 页 - - - - - - - - - 数据结构资料- 17 - typedef struct Queue int * pBase; int front; int rear; QUEUE,*PQ

28、UEUE; bool init(PQUEUE); /初始化bool en_queue(PQUEUE,int); /入队bool out_queue(PQUEUE,int *); /出队void traverse_queue(PQUEUE); / 遍历int main(void) /不能直接定义 PQUEUE pQueue, 后面在直接使用pQueue, 运行时有错误。QUEUE queue; int val; init(&queue); en_queue(&queue,5); en_queue(&queue,2); en_queue(&queue,8); en_queue(&queue,7);

29、 en_queue(&queue,3); en_queue(&queue,1); traverse_queue(&queue); if(out_queue(&queue,&val) printf(out: %d n,val); traverse_queue(&queue); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 35 页 - - - - - - - - - 数据结构资料- 18 - bool init(PQUEUE pQueue) pQue

30、ue-pBase = (int *)malloc(sizeof(int)*6); if(pQueue-pBase = NULL) printf(failed); return false; else pQueue-front = 0; pQueue-rear = 0; return true; bool en_queue(PQUEUE pQueue,int val) if(pQueue-front = (pQueue-rear)+1)%6) return false; else /等价于 pQueue-pBasepQueue-rear = val; *(pQueue-pBase)+pQueue

31、-rear) = val; pQueue-rear = (pQueue-rear+1)%6; return true; void traverse_queue(PQUEUE pQueue) int temp = pQueue-front; if(temp = pQueue-rear) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 35 页 - - - - - - - - - 数据结构资料- 19 - return ; while(temp != pQueue-rear

32、) printf(%d ,*(pQueue-pBase)+temp); temp = (temp+1)%6; printf(n); return ; bool out_queue(PQUEUE pQueue,int * pVal) if(pQueue-front = pQueue-rear) return false; else *pVal = pQueue-pBasepQueue-front; pQueue-front = (pQueue-front + 1)%6; return true; 3.5、专题：递归（使用栈实现的）3.5.1. 定义:一个函数自己直接或间接调用自己3.5.2. 函

33、数的调用前后的准备工作当在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事：a、将所有的实际参数、返回地址等信息传递给被调函数保存b、为被调函数的局部变量（包括形参）分配存储空间c、将控制转移到被调函数的入口从被调函数返回主调函数之前，系统也要完成三件事：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 35 页 - - - - - - - - - 数据结构资料- 20 - a、保存被调函数返回结果b、释放被调函数所占的存储空间c、依照被调函数保

34、存的返回地址将控制转移到调用函数当有多个函数相互调用时，按照“ 后调用先返回 ” 的原则，上述函数之间的信息传递和控制转移必须借助 “ 栈” 来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就在栈顶分配一个存储区，进行压栈操作；每当一个函数退出时，就释放它的存储区，进行出栈操作，当前运行的函数永远都在栈顶位置。A 函数调用 A 函数与 A 函数调用 B 函数在计算机看来是没有任何区别的，只不过用我们日常的思维方式理解比较怪异而已。#include int f(int n) int k; k = n + 1; return k; int main(void) in

35、t i; i = f(5); printf(%d n,i); return 0; 3.5.3 递归必须满足的三个条件：a、递归必须得有一个明确的终止条件b、该函数处理的数据规模必须在递减c、这个转化必须是可解的3.5.4. 循环和递归之间的关系理论上循环能解决的问题，肯定可以转化为递归解决，但是这个过程是复杂的数学转化过程，递归能解决的问题不一定能转化为循环解决递归的优缺点：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 35 页 - - - - - - - - - 数

36、据结构资料- 21 - 优点易于理解（针对复杂问题时就会表现出来）缺点（从调用前的三个工作分析）速度慢运行需要的存储空间大循环的优缺点：优点速度快运行需要的存储空间小缺点不易理解3.5.5. 举例：1.1+2+3+4+.+100 的和; 2.求阶乘 ; 使用 for 循环实现：求和求阶乘# include # include int main(void) int main(void) long sum = 0; long mult = 1; for（int i = 1;i = 100;i + ）int val; sum = sum + i; printf( 请输出整数： ) printf(1

37、到 100 的和是： %ld, sum); scanf (%d,&val); return 0; for (int i = 1; i = val; i +) mult = mult * i; printf(%d 的阶乘是 %ld, val, mult); return 0; 使用递归实现：#include #include long sum (int val) long mult (int val) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 35 页 - - -

38、- - - - - - 数据结构资料- 22 - if(1 = val) if(1 = val) return 1; return 1; else else return val+sum(val - 1); return val*mult(val-1); int man(void) int main(void) printf(1 到 100的和是： %ld,sum(100); printf( 请输出整数： ) return 0; scanf (%d,&val); printf(%d 的阶乘是 %ld, val, mult(val); return 0; 3.汉诺塔伪算法：if（1 = n）直接

39、将盘子从 A 移动到 C else （三步）第一步：将 A 上的前 n - 1 个盘子借助 B 移动到 C 第二步：将 A 上的第 n 个盘子直接移动到C 第三步：将 B 上的 n - 1 个盘子借助 A 移动到 C #include void hnt(int n,char a,char b,char c) if(1 = n) printf(move num. %d disk from %c to %c n,n,a,c); else hnt(n-1,a,c,b); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

40、 - - - - - - 第 22 页，共 35 页 - - - - - - - - - 数据结构资料- 23 - printf(move num. %d disk from %c to %c n,n,a,c); hnt(n-1,b,a,c); int main(void) hnt(10,a,b,c); return 0; 4.走迷宫3.5.6. 递归的应用树和森林就是以递归的方式定义的树和图的很多算法都是以递归来实现的很多数学公式就是以递归的方式定义的（例如：斐波拉契序列）4 模块二：非线性结构4.1、树4.1.1. 定义及专业术语（专业定义）有且只有一个称为根的结点；有若干个互不相交的子树

41、，这些子树本身也是一棵树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 35 页 - - - - - - - - - 数据结构资料- 24 - （通俗定义）树是由结点和边（即指针）组成；每一个结点只有一个父结点但可以有多个子结点；但是有一个结点例外，该结点没有父结点，此结点称为根结点专业术语结点 / 父结点（只有一个）/ 子结点 / 子孙 / 堂兄弟深度:从根结点到最底层结点的层数（根结点是第一层）叶子结点：没有子结点的结点非终端结点：实际就是 非叶子结点 ，即有子结点

42、的结点度：子结点的个数（即每个结点的子结点数，树的度指所有结点中的最大度）4.1.2. 分类一般树：任意一个结点的子结点的个数都不受限制二叉树：任意一个结点的子结点的个数最多两个，且子节点的位置（左右顺序）不可更改，二叉树是有序的二叉树的分类：一般二叉树满二叉树：在不增加树的层数的情况下， 无法再多添加一个结点的二叉树就是满二叉树完全二叉树：如果只是删除满二叉树最底层最右边的连续 若干个结点，这样形成的二叉树就是完全二叉树满二叉树是完全二叉树的特例，完全二叉树包含满二叉树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整

43、理 - - - - - - - 第 24 页，共 35 页 - - - - - - - - - 数据结构资料- 25 - 一般二叉树满二叉树完全二叉树森林： n 个互不相交的树的集合4.1.3. 存储（解决非线性结构用线性结构表示的问题）二叉树的存储连续存储 完全二叉树 一般二叉树要以数组的方式存储，要先转化成完全二叉树，因为如果只存有效节点（无论以哪种规则：先序，中序，后序） ，则无法知道这个树的原本样子。优点：查找某个结点的父结点和子结点（也包括判断有没有子结点）速度很快缺点：耗用内存空间过大链式存储存储方式左子结点指针+ 右子结点指针+ 有效数据（或者再 + 父结点指针）名师资料总结 -

44、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 25 页，共 35 页 - - - - - - - - - 数据结构资料- 26 - 一般树的存储双亲表示法（求父结点方便）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 26 页，共 35 页 - - - - - - - - - 数据结构资料- 27 - 孩子表示法（求子结点方便）孩子双亲表示法（求父结点和子结点都方便）二叉树表示法把一棵普

45、通树转化成二叉树来存储具体转化方法：设法保证任意一个结点的左指针域指向它的第一个孩子，右指针域指向它的下一个兄弟名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 27 页，共 35 页 - - - - - - - - - 数据结构资料- 28 - 一棵普通树转化为的二叉树一定没有右子树森林的存储先把森林转化为二叉树，再存储二叉树具体方式为：根节点之间可以当成是兄弟来看待4.1.4 操作(重点)树的遍历（面试必考）名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

46、- - - - - - - - - - 名师精心整理 - - - - - - - 第 28 页，共 35 页 - - - - - - - - - 数据结构资料- 29 - 先序遍历 先访问根结点 先访问根结点，再先序访问左子树，后先序访问右子树中序遍历 中间访问根结点 先中序遍历左子树，再访问根节点，后中序访问右子树后序遍历 最后访问根结点 先后序遍历左子树，再后序遍历右子树，后访问根结点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 29 页，共 35 页 - - - - - -

47、- - - 数据结构资料- 30 - 已知两种遍历求原始二叉树（面试必考）通过 先序遍历和中序遍历或者 中序遍历和后序遍历我们可以还原出原始的二叉树，但是通过 先序遍历和后序遍历是无法还原出原始的二叉树的。换种说法：只有通过先序遍历和中序遍历或者 中序遍历和后序遍历我们才可以唯一的确定一个二叉树的。先序遍历和中序遍历名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 30 页，共 35 页 - - - - - - - - - 数据结构资料- 31 - 中序遍历和后序遍历4.1.4 应用及

48、代码树是数据库中数据组织的一种重要形式操作系统子父进程的关系本身就是一棵树面向对象语言中类的继承关系本身就是一棵树赫夫曼树#include #include struct BTNode * createBTree(void); /先序遍历void PreTraveseBTree(struct BTNode *); /中序遍历void InTraveseBTree(struct BTNode *); /后序遍历void PostTraveseBTree(struct BTNode *); struct BTNode char data; struct BTNode * pLChild; stru

49、ct BTNode * pRChild; ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 31 页，共 35 页 - - - - - - - - - 数据结构资料- 32 - int main(void) struct BTNode * pT = createBTree(); / PreTraveseBTree(pT); / InTraveseBTree(pT); PostTraveseBTree(pT); return 0; struct BTNode * createBTre

50、e(void) struct BTNode * pA = (struct BTNode *)malloc(sizeof(BTNode); struct BTNode * pB = (struct BTNode *)malloc(sizeof(BTNode); struct BTNode * pC = (struct BTNode *)malloc(sizeof(BTNode); struct BTNode * pD = (struct BTNode *)malloc(sizeof(BTNode); struct BTNode * pE = (struct BTNode *)malloc(siz