数据结构_总复习

数据结构_总复习null第一章绪论第一章绪论什么是数据结构一些基本概念和术语算法和算法分析时间复杂度的渐进表示法第一章绪论第一章绪论数据结构的研究对象：非数值数据之间的结构关系，如何表示，如何存储，如何处理的问题。本课程讨论的问题：应用中常用的几种数据结构，以及如何存储, 如何处理它们。null基本概念和术语数据（data)—所有能输入到计算机中去的描述客观事物的符号数据元素（data element）—数据的基本单位，也称节点（node）或记录（record）。有时...

null第一章绪论第一章绪论什么是数据结构一些基本概念和术语算法和算法分析时间复杂度的渐进表示法第一章绪论第一章绪论数据结构的研究对象：非数值数据之间的结构关系，如何表示，如何存储，如何处理的问题。本课程讨论的问题：应用中常用的几种数据结构，以及如何存储, 如何处理它们。null基本概念和术语数据（data)—所有能输入到计算机中去的描述客观事物的符号数据元素（data element）—数据的基本单位，也称节点（node）或记录（record）。有时一个数据元素可以由若干数据项(Data Item)组成。数据项（data item）—有独立含义的数据最小单位，也称域(field) 数据结构（data structure)—数据元素和数据元素关系的集合第一章绪论第一章绪论null6 数据的存储结构：数据结构在计算机内存中的表示。 7 顺序存储结构用一组连续的内存单元存放数据元素，用元素相对的存储位置表示元素之间的结构关系； 8 链式存储结构用任意一组存储单元存储数据元素，对每个数据元素除了保存自身信息外，还保存相关元素的存储位置。数据结构基本操作的实现：基本操作在计算机上的实现（方法）null9 数据结构的表示 1 图示表示 2 二元组表示图示表示：由顶点和边构成的图，其中顶点表示数据，边表示数据之间的结构关系；null10 算法的概念算法是求解问题的操作序列（或操作步骤） 11 时间复杂度T（n）以求解问题的基本操作（原操作）的执行次数作为算法的时间度量空间复杂度用执行算法所需的辅助空间的大小作为算法所需空间的度量null 1.4.1 算法具有以下五个特性：（1）有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。（3）可行性一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 (4）输入一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 (5）输出一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。null1.4.2 算法的评价标准 : (1)正确性(Correctness) 算法应满足具体问题的需求。 (2)可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解。 (3)健壮性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。 (4)效率与存储量需求效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。null例1：求两个矩阵的乘积 C＝A*B for(i=0;idata表示p指向结点的数据域 (*p).nextp->next表示p指向结点的指针域生成新结点：p=(LinkList )malloc(sizeof(LNode)); 系统回收p结点：free(p) 结点中只含一个指针域的链表叫~，也叫单链表null头结点：在单链表第一个结点前附设一个结点叫~ 头结点指针域为空表示线性表为空头结点插入：在线性表两个数据元素a和b间插入x，已知p指向a 插入：在线性表两个数据元素a和b间插入x，已知p指向a s->next=p->next;p->next=s;算法思想: 1.寻找第i-1个元素结点顺指针向后查找，直到p指向第i-1个元素或p为空 2.分配新结点 3.插入新结点null插入操作算法： Status ListInsert_L(LinkList &L, int i, ElemType e){ //在带头结点的线性链表L中第i元素结点之前插入元素e p=L; j=0 while (p&&jnext; ++j;}//寻找第i-1个元素结点 if(!p||j>i-1)return ERROR; // i小于1 则 j>i-1 // i大于表长+1 则p为空 s=(LinkList)malloc(sizeof(LNode)); //分配新结点 s->data=e; s->next=p->next; p->next=s; //插入新结点 return OK; }//LinstInsert_L 算法 2.9null删除：单链表中删除b，设p指向ap->next=p->next->next;算法思想: 1.寻找第i-1个结点顺指针向后查找，直到p指向第i-1个元素或p->next为空 2.删除结点(修改其后继指针) 3.回收（释放）结点空间null删除操作算法： Status ListDelete_L(LinkList &L, int i, ElemType &e){ //在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 p=L; j=0; while (p->next&&jnext; ++j; } if(!p->next)||j>i-1)return ERROR; // 表中无第i个结点(i不合法) // i<1 则 j>i-1 // i>表长则 p->next为空 q=p->next;p->next=q->next; //删除结点 e =q->data; free(q); // 回收（释放）结点空间 return OK; }//LinstDelete_L 算法： 2.10null逆置线性链表a1a2a3Lpa1a2a3基本操作：1）标志后继结点； 2）修改指针（将*p插入在头结点之后）； 3）重置结点*p（p重新指向原表中后继）；nullvoid inverse(LinkList &L) { // 逆置带头结点的单链表 L p=L->next; L->next=NULL; while ( p) { succ=p->next; // succ指向*p的后继 p->next=L->next; L->next=p; // *p插入在头结点之后 p = succ; } }返回nullnull 栈是限定仅能在表尾进行插入删除操作的线性表。栈的特点后进先出一.栈的概念 1 栈的定义 3.1 栈 3.1 栈2 栈的基本操作 1）初始化操作InitStack((&S) 2）销毁栈操作DestroyStack(&S) 3）置空栈操作ClearStack(&S) 4）取栈顶元素操作GetTop(S, &e) 5）进栈操作Push(&S, e) 6）退栈操作Pop(&S, &e） 7）判空操作StackEmpty(S)null二栈的顺序存储和实现 1 栈的顺序存储结构 1）用一组连续的内存单元依次存放自栈底到栈顶的数据元素； 2）栈顶指针； nulltypedef struct{ SElemType *base; //栈底指针 SElemType *top //栈顶指针 int stacksize; //当前分配的栈空间大小 //(以sizeof(SElemType)为单位） }SqStack; 2 顺序栈的类型定义null 顺序栈的图示null栈操作算法 1）进栈操作算法：在栈顶插入元素 Push(SqStack &S, SElemType e) 2）出栈操作算法：在栈顶插入元素 Pop(SqStack &S, SElemType &e ) 4 栈操作主要特点进栈、出栈操作要修改栈顶指针null栈的链式存储和实现栈的链式存储与线性表的链式存储类似，可用带头结点的线性链表存储。注意：栈顶指针就是带头结点的线性链表的头指针Snull１栈是限定仅能在表尾一端进行插入、删除操作的线性表； 2 表尾称为栈顶，表头称为栈底； 3 栈的具有后进先出的特点； 4 栈顶元素的位置由一个栈顶指针指示； 5 进栈、出栈操作要修改栈顶指针； 6 一个栈的输入序列为a,b,c，则所有可能的出栈序列为： abc,acb,bac,bca,cbanull一队列的概念１队列的定义队列是限定仅能在表头删除，表尾插入的线性表。队列的特点先进先出null2 队列的基本操作 1）初始化操作InitQueue( &Q) 2）销毁操作DestroyQueue( &Q) 3）置空操作ClearQueue(&Q) 4）判空操作QueueEmpty(Q) 5）取队头元素操作GetHead(Q,&e) 6）入队操作EnQueue( &Q, e ) 7）出队操作DeQueue( &Q, &e)null二循环队列——队列的顺序存储和实现循环队列——队列的顺序存贮结构（1）在队列的顺序存贮结构中用一组连续存储单元依次存储队列的数据元素（2）队头、队尾元素的位置分别由队头指针和队尾指针指示；（3）将顺序队列设想为首尾相连的环状空间null 2 循环队列的类型定义#define MAXSIZE 100 //最大队列长度 typedef struct{ QElemType *base; 队空间基址 int front; //队头指针 int rear; //队尾指针 }SqQueue;null2 队列操作算法入队操作：在队尾插入元素；出队操作：在队头删除元素； null入队： Q.Base[Q.Rear] = e; Q.Rear = ( Q.Rear + 1 ) % MAXQSIZE; 出队： e = Q.Base[Q.Front]; Q.Front = (Q.Front + 1) % MAXQSIZE; 队满、队空判定条件队空：front==rear 队满：(rear+1)%M==frontnull１队列是限定仅能在表尾一端插入，表头一端删除操作的线性表； 2 表尾称为队头，表头称为队尾 3 队头、队尾元素的位置分别由队头指针和队尾指针指示； 4 队列具有先进先出的特点 5 入队操作要修改队尾指针，出队操作要修改队头指针；nullnull一、串的概念 1 什么是串串是由零个或多个字符组成的有限序列，一般记作 s = ‘a1,a2, a3, ... an’null2 串的基本操作（了解）串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与线性表不同，串的基本操作与线性表有很大差别。串连接操作 Concat( &T,S1,S2) 求子串操作SubString( &Sub,S, pos,len) 求子串位置操作Index( S,T,pos ) 串插入操作 StrInsert( &S,pos,T) 串删除操作 StrDelete( &S,pos,len) null一、串的存储（了解） 1 定长顺序存储结构定长顺序存储结构类似于C语言的字符数组，以一组地址连续的存储单元存放串值字符序列，其类型说明如下： #define MAXSTRLEN 255 Typedef unsigned char SString[MAXSTRLEN+1] null2、堆分配存储　　堆分配存储类似于线性表的顺序存储结构 typedef struct { char *ch; //指向存放串值的存储空间基址 int length; // 整型域：存放串长 }Hstring;null１从逻辑结构上看串是线性数据结构；２ S=‘ababcabcac’, S1=‘abc’， S2=‘isastring’ Concat(Hstring &T,Hstring S1,Hstring S2) T=’abcisastring’ 3 请列举两个线性表所没有的串操作:求子串,求子串位置，nullnull1 数组的逻辑结构 n维数组中的每个元素都受n个线性关系的约束，以二维数组为例：二维数组中的每个元素都受两个线性关系的约束 null2 数组的基本操作（了解）初始化操作 InitArray(&A,n,bound1,…,boundn) 功能：参数合法，构造数组A，并返回OK；销毁操作 DestroyArray(&A) 功能：销毁数组A ； 3 读元素操作 Value(A,&e,index1,…,indexn) 功能：若指定下标不越界，读指定下标的元素，用e返回，并返回OK；写元素操作 Assign(A,e,index1,…,indexn) 功能：若指定下标不越界，将e赋值给A指定的下标元素，并返回OK；null3 数组的顺序存贮结构( 以二维数组为例) 两种方式：以行为主序的方式，以列序为主序的方式 4 数组元素存储地址的计算null1 从逻辑结构来看，二维数组中的每个元素都受两个线性关系的约束２　在行关系中 aij直接前趋是 aij-1， aij直接后继是 aij+1 ；　　在列关系中 aij直接前趋是 ai-1j aij直接后继是 ai+1j ；３　二维数组的两种顺序存贮结构为：１）以行为主序的方式，２）以列序为主序的方式。４数组元素存储地址的计算 n维数组的存储地址计算公式 n维数组的存储地址计算公式 b1,b2,...,bn是n维的维界,数组元素A(j1,j2,...,jn)的存储位置为 LOC[j1,j2,...jn]= LOC[0,0,...,0] + (b2*b3*...*bn*j1 + b3*...*bn*j2 + ...... + bn*jn-1 + jn )*L n-1 n = LOC[0,0,...,0] + (  ji  bk + jn)*L i=1 k=i+1 例: 在C语言中,设数组A[5][6][7][8]的首地址为 2000, 每个元素占2个字节; 求元素A[3][4][5][4]的地址. LOC[3,4,5,4] = 2000 + (6*7*8*3 + 7*8*4 + 8*5 + 4)*2 = 2000 + ( 336*3 + 56*4 + 8*5 + 1*4)*2 = 2000 + (1008 + 224 + 40 + 4)*2 = 45525．2 矩阵的压缩存储5．2 矩阵的压缩存储矩阵压缩存储是指为多个值相同的元素分配一个存储空间，对零元素不分配存储空间一特殊矩阵 1 什么是特殊矩阵值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵 2 特殊矩阵压缩存储特殊矩阵的压缩存储是根据元素的分布规律，确定元素的存储位置与元素在矩阵中的位置的对应关系； null二稀疏矩阵 1 什么是稀疏矩阵有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵。 2 稀疏矩阵的压缩存储（只讨论有较多零元素矩阵的压缩存储）稀疏矩阵的压缩存储只存非零元，对每一非零元，除了要保存非零元素的值外，还要保存非零元素在矩阵中的位置；null3 稀疏矩阵的（非零元）三元组表 A=((1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) ) 4 三元组顺序表用顺序表存储三元组表，非零元三元组以行为主序存储null1 矩阵压缩存储是指为多个值相同的元素分配一个存储空间，对零元素不分配存储空间； 2 特殊矩阵的压缩存储是根据元素的分布规律，确定元素的存储位置与元素在矩阵中的位置的对应关系； 3 (含零元的)稀疏矩阵的压缩存储只存非零元，对每一非零元，除了要保存零元素的值外，还要保存零元素在矩阵中的位置； 4 给出稀疏矩阵，写出对应的（非零元）三元组表 A=((1,2,12),(1,3,9),(3,1,-3),(3,6,14), (4,3,24),(5,2,18),(6,1,15),(6,4,-7) )null1 什么是广义表广义表是数据元素的有限序列。记作：LS= (α1,α2,… ,αn)。其中αi其可以是单个元素，也可以是广义表。 2 广义表的基本操作求表头求表尾表头：广义表的第一个元素表尾：除第一个元素外，起它元素组成的表 null３广义表的存储结构（了解）广义表通常采用链式存储结构。链表中有两种的结点：一种是表结点，用以表示广义表；一种是原子结点，用以表示原子； null１广义表是数据元素的有限序列。其元素可以是单个元素，也可以是广义表。 2表头：广义表的第一个元素表尾：除第一个元素外，其它元素组成的表 GetTail【GetHead【GetTail【((a,b),(c,d))】】】= （d） ;第六章树和二叉树第六章树和二叉树第六章树和二叉树第六章树和二叉树6.1 树的定义和基本概念 6.2 二叉树 6.2.1 树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.5 赫夫曼树及其应用null一树的概念 1 树的逻辑结构树：是一种一对多的结构关系或称为分枝结构关系，除了根之外，每个元素只有一个直接前趋；，但每个元素可以有零个或多个直接后继；null基本术语结点(node)——指树中的一个数据元素，包括数据项及若干指向其子树的分支。一般用一个字母表示。结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点，也叫终端结点。分枝结点——除叶子结点外的所有结点，也叫非终端结点。孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的~ 祖先结点——从根结点到该结点所经过分枝上的所有结点为该结点的祖先，如图6-1c中M的祖先有A，D ，H 。子孙结点——某一结点的子女及子女的子女都为该结点子孙。null基本术语兄弟(sibling)——具有同一个双亲的结点树的度——一棵树中最大的结点度数结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层…… 深度(depth)——树中结点的最大层次数有序树——若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。无序树——若一棵树中所有子树的次序无关紧要，则称为无序树。森林(forest)——m(m0)棵互不相交的树的集合.一棵树可以看成是一个特殊的森林。null结点A的度：3 结点B的度：2 结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D 结点B的孩子：E，F结点I的双亲：D 结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1 结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先null6.2 二叉树 6.2.1定义定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒基本形态null (a)、(b)是不同的二叉树， (a)的左子树有四个结点， (b)的左子树有两个结点，(a)(b) 基本操作：基本操作：InitBiTree( &T ); // 初始化 DestroyBiTree( &T ); // 销毁 CreateBiTree( &T, definition ); // 创建二叉树 ClearBiTree( &T ); // 清空 BiTreeEmpty( T ); // 空？ BiTreeDepth( T ); // 深度 Root( T ); // 根 Value( T, e ); // 求e的值 Assign( T, &e, value ); // 赋值 Parent( T, e ); // 求双亲 LeftChild( T, e ); // 左孩子 RightChild( T, e ); // 右孩子 LeftSibling( T, e) ; // 左兄弟 nullRightSibling( T, e ); // 右兄弟 InsertChild( T, p, LR, c ); // 插入 DeleteChild( T, p, LR ); // 删除 PreOrderTraverse( T, Visit( )); // 先序遍历 InOrderTraverse( T, Visit( )); // 中序遍历 PostOrderTraverse( T, Visit( )); // 后序遍历 LeverOrderTraverse( T, Visit( )); // 层序遍历 } // ADT BinaryTree null6.2.2二叉树性质性质1：null性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1null几种特殊形式的二叉树满二叉树定义：特点：每一层上的结点数都是最大结点数完全二叉树定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为~ 特点叶子结点只可能在层次最大的两层上出现对任一结点，若其右分支下子孙的最大层次为 L，则其左分支下子孙的最大层次必为 L 或 L +1 性质性质4：nullnull性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有： (1) 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2 (2) 如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i (3) 如果2i+1>n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1示意图示意图2i2i+1i2i+22i+3i+1[i/2]j层j+1层nullLCHILD(i)LCHILD(i+1)RCHILD(i)RCHILD(i+1)null二叉树的存储结构顺序存储结构实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树#define MAX_TREE_SIZE 100 // 0号单元存放根结点； typedef TElemType sqBiTree[MAX_TREE_SIZE]; SqBiTree bt;顺序存储结构举例顺序存储结构举例null×二叉树的链式存储结构二叉树的链式存储结构考虑：二叉树的数据元素之间的关系任一个结点，最多有两个孩子（直接后继元素）二叉链表 pLChilddatapRChilddatapLChild pRChild除根结点外，所有结点都有一个双亲结点（直接前驱元素）；三叉链表除根结点外，所有结点都有一个双亲结点（直接前驱元素）；三叉链表 pLChilddatapRChilddatapLChild pRChildpParentpParentnull二叉树链表表示的示例AAABBBCCCDDDFFFEEErootrootroot二叉树二叉链表三叉链表null 二叉链表typedef struct BitNode { TElemType data; struct BitNode *lchild, *rchild; }BiTNode, *BiTree;在n个结点的二叉链表中，有n+1个空指针域^^^^^^^^null三叉链表typedef struct node { Elemtype data; struct node *lchild, *rchild, *parent; };^^^^^^^^^基本操作的函数原型说明(一)基本操作的函数原型说明(一)Status CreateBiTree(BiTree &T); //按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树， //构造二叉链表表示的二叉树T。 Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e)); //采用二叉链表存储结构,Visit是对结点操作的应用函数 //先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。 //一旦Visit( ) 失败，则操作失败。基本操作的函数原型说明(二) 基本操作的函数原型说明(二) Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e)); //采用二叉链表存储结构,Visit是对结点操作的应用函数。 //中序遍历二叉树T，一旦Visit( ) 失败，则操作失败。 Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e)); //采用二叉链表存储结构,Visit是对结点操作的应用函数。 //后序遍历二叉树T，一旦Visit( ) 失败，则操作失败。 Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType e)); //采用二叉链表存储结构,Visit是对结点操作的应用函数。 //层序遍历二叉树T，一旦Visit( ) 失败，则操作失败。null6.3遍历二叉树和线索二叉树 6.3.1二叉树的遍历遍历——按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列由二叉树的递归定义，二叉树的三个基本组成单元是：根结点、左子树和右子树。二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树null方法先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点按层次遍历：从上到下、从左到右访问各结点令：L：遍历左子树 D：访问根结点 R：遍历右子树有六种遍历方法： DLR，LDR，LRD， DRL，RDL，RLD 约定先左后右,有三种遍历方法： DLR、LDR、LRD ，分别称为先序遍历、中序遍历、后序遍历nullD L R先序遍历序列：A B D C先序遍历:nullL D R中序遍历序列：B D A C中序遍历:null L R D后序遍历序列： D B C A后序遍历:null先序遍历：中序遍历：后序遍历：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef表达式（a+b*(c-d)-e/f)的二叉树null这实际上是先序遍历的递归定义，我们知道递归定义包括两个部分：1）基本项（也叫终止项）； 2）递归项若二叉树非空（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；先序遍历递归定义递归项二. 遍历的递归算法上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历方法，以先序为例：先序遍历（DLR）的定义：该定义隐含着若二叉树为空，结束 null上面先序遍历的定义等价于：若二叉树为空，结束 ——基本项（也叫终止项）若二叉树非空 ——递归项（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；下面给出先序、中序、后序遍历递归算法，为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数visit( )访问结点总是成功的。null先序遍历递归算法 void PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e)) { if (T) { //若二叉树为空，结束返回 Visit(T->data)； PreOrderTraverse(T->lchild, Visit); PreOrderTraverse(T->rchild, Visit); }//PreOrderTraverse 最简单的Visit函数是： Status PrintElement(TElemType e) { //输出元素e的值 printf(e); return OK; } 先序遍历二叉树算法先序遍历二叉树算法Status PreOrderTraverse( BiTree T, status ( * visit)(TElemType e)) { if( T ) { if( (*Visit)(T->data )) if( PreOrderTraverse( T->LChild, visit )) if( PreOrderTraverse( T->RChild, visit )) return OK； return ERROR; } else return OK; } // PreOrderTraversenull中序遍历二叉树的递归算法： void inOrderTraverse(BiTree T) { if(T!=NULL) { inOrderTraverse(T->lchild); printf(T->data); inOrderTraverse(T->rchild); } } 后序遍历二叉树的递归算法： void PostOrderTraverse(BiTree T) { if(T!=NULL) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf(T->data); } } null遍历算法应用按先序遍历序列建立二叉树的二叉链表，已知先序序列为： A B C   D E  G   F   ABCΦΦDEΦGFΦΦΦ算法：算法：// 根据先序序列，创建一棵二叉树 Status CreateBiTree( BiTree &T) { scanf( &ch ); if( ch == ‘ ‘ ) T=NULL; else { if( ! (T=(BiTNode *)malloc(sizeof(BiTNode)))) exit( OVERFLOW ); //T=new node() T->data = ch; //生成根结点 CreateBiTree( T->LChild ); //构造左子树 CreateBiTree( T->RChild ); //构造右子树 } return OK; }// CreateBiTree; null例1 编写求二叉树的叶子结点个数的算法输入：二叉树的二叉链表结果：二叉树的叶子结点个数基本思想：遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。所以可在二叉树遍历的过程中，统计叶子结点的个数。void leaf(BiTree T) { //采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点的个数。本算法在先序遍历二叉树的过程中，统计叶子结点的个数 //第一次被调用时，n=0 if(T) { //若二叉树为空，结束返回 //若二叉树不为空，在先序遍历二叉树的过程中，统计叶子结点的个数 if(T->lchild==null&&T->rchild==null) n=n+1; leaf(T->lchild); leaf(T->rchild); }//if }//leafnullvoid leaf(BiTree T) { //采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点,的个数。 //本算法在先序遍历二叉树的过程中，统计叶子结点的个数第一次被调用时，n=0 if(T) { //若二叉树为空，结束返回 //若二叉树不为空，在先序遍历二叉树的过程中，统计叶子结点的个数 if (T->lchild==null&&T->rchild==null) n=n+1; leaf(T->lchild); leaf(T->rchild); }//if }//leaf viod PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e)) { //采用二叉链表存贮二叉树， visit( )是访问结点的函数。本算法先序 //遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit( ) if (T) { //若二叉树为空，返回 // 若二叉树不为空，访问根结点；遍历左子树，遍历右子树 Visit(T->data)； PreOrderTraverse(T->lchild, Visit); PreOrderTraverse(T->rchild, Visit); }//PreOrderTraverse比较先序遍历算法和计算叶子结点算法，有什么相同和不同？结构类似函数名不同访问结点时调用visit( )访问结点时统计叶子结点的个数二叉树的计数二叉树的计数由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例, 前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如下：HBDFEKCGAEKCGABHDFnull前序序列 { ABHFDECKG } KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG小结小结遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树，本课程介绍了三种遍历算法：先序遍历、中序遍历、后序遍历；null编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。分析:1。在先序遍历二叉树的过程中查找每一个元素值为x的结点； 2。修改其双亲结点的相应指针；3。释放以它为根的子树上的所有结点，则应该后序遍历以它为根的子树。nullvoid Delete-X( BiTree &BT, ElemType x){ if (BT) { if (BT->data==x) { disp(BT); //后序遍历释放被删子树中所有结点 BT=NULL; // 修改指针，删除子树 } else { Delete-X(BT->Lchild, x); Delete-X(BT->Rchild, x); } } // if }返回null编写按层次顺序(同一层自左至右)遍历二叉树的算法。分析: 按层次遍历的定义: 若树不空，则首先访问根结点，然后，依照其双亲结点访问的顺序，依次访问它们的左、右孩子结点; 因此，需要一个“队列”保存已被访问的结点nullvoid BFSTraverse(BiTree T) { InitQueue(Q); // 置空的辅助队列Q if (T) EnQueue(Q, T); // 根结点入队列 while (!QueueEmpty(Q)) { DeQueue(Q, p); // 队头元素出队并置为p Visit(p); if (p->Lchild) EnQueue(Q, p->Lchild); // 左子树根入队列 if (p->Rchild) EnQueue(Q, p->Rchild); // 右子树根入队列 } // while }null编写递归算法，交换二叉树中所有结点的左右子树注意：此题不能依中序遍历的次序进行void swap( BiTree BT ) { if (BT) { BT->lchild  BT->rchild; swap( BT->lchild); swap( BT->rchild); } }求一棵二叉树高度的算法求一棵二叉树高度的算法已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; }; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树高度的算法，该高度由函数返回。假定根结点的层次为0，参数BT初始指向这棵二叉树的根结点。 int BTreeHeight ( BinTreeNode* BT );null算法如下 int BTreeHeight ( BinTreeNode* BT ) { if ( BT == NULL ) return –1; //对于空树，返回-1并结束递归，1分 else { int h1 = BTreeHeight ( BT->leftChild ); //计算左子树的高度，2分 int h2 = BTreeHeight (BT->rightChild ); //计算右子树的高度，2分 if ( h1 > h2 ) return h1+1; else return h2+1; //返回树的高度，3分 } }求一棵二叉树中结点总数的算法求一棵二叉树中结点总数的算法已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BTreeNode { char data; BinTreeNode *leftChild, *rightChild; }; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。 int BTreeCount ( BinTreeNode* BT );null算法如下 int BTreeCount ( BinTreeNode* BT ) { if ( BT == NULL ) return 0; //2分 else return BTreeCount ( BT->leftChild ) + BTreeCount ( BT->rightChild ) + 1; //6分 }求一棵二叉树中叶子结点总数求一棵二叉树中叶子结点总数已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; }; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。int BTreeLeafCount ( BinTreeNode* BT );null算法如下 int BTreeLeafCount ( BinTreeNode* BT ) { if ( BT == NULL ) return 0; //1分 else if (BT->leftChild == NULL && BT->rightChild == NULL) return 1; //3分 else return BTreeLeafCount ( BT->leftChild ) + BTreeLeafCount ( BT->rightChild ); //4分 }删除一棵二叉树中所有结点的算法删除一棵二叉树中所有结点的算法已知二叉树中的结点类

                    本文档为【数据结构_总复习】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

数据结构_总复习

你可能还喜欢