数据结构递归

#include

using namespace std;

void fun(int i){

if(i>0) fun(i/2);

cout<

}

int main( ){ fun(10); return 0;}

例2：

#include

using namespace std;

void conversion(int n)

{

if(n==0) return ;

else {

int i=n%2; conversion(n/2);

cout<

}

int main()

{conversion(13); return 0;}

例3：

#include

using namespace std;

void conversion(int n)

{

if(n==0) return ;

else

{ n=n/2; conversion(n);

cout<

}

int main()

{conversion(13); return 0;}

#include

using namespace std;

void Display(int n)

{ int i;

for(i = 1; i <= n; i++)

cout<<' '<

cout<

if(n > 0) Display(n - 1);

}

例5

int main()

{Display(4); return 0;}

#include

using namespace std;

float f(int A[],int i){

int m;

if (i==0) return A[0];

else{

m=f(A,i-1);

if (m>A[i]) return A[i];

else return m;}

}

int main()

{ int A[5]={5,3,1,4,2};

cout<

return 0;}

例6：

//假设链表已经创建，链表中有三个结点，数据域为整数，分别为：1、2 、3 //调用下面函数时，参数指针p指向首元结点1，参数n为链表长度，即3 //根据上述已知，给出此函数的递归执行过程和返回结果

double GetAverage(LinkList p , int n)

{

if(!p->next) return p->data;

else

{

double ave=GetAverage(p->next,n-1);

return (ave*(n-1)+p->data)/n;

}

}

//假设链表已经创建，链表中有三个结点，数据域为整数，分别为：1、2 、3 //调用下面函数时，参数指针p指向首元结点1

// n为全局变量，初值为3

//根据上述已知，给出此函数的递归执行过程和返回结果

double GetAverage(LinkList p )

{

if(!p->next) return p->data;

else

{

n--;

double ave=GetAverage(p->next);

return (ave*n+p->data)/(n+1);

}

}

例8：

#include

int fact( )

{ static int i=5;

if(i==0) return 1;

else

{ i--;

return(fact( )*(i+1)); }

}

int main( )

{ printf("factor of 5!=%d\n",fact());

return 0;}

例9：

#include

int fact( )

{ static int i=5;

if(i==0) return 1;

else

{ i--;

return((i+1)*fact( )); }

}

int main( )

{ printf("factor of 5!=%d\n",fact());

return 0;}

数据结构二叉树的递归算法实验报告

齐鲁工业大学实验报告成绩 课程名称数据结构指导教师单健芳实验日期 院（系）信息学院专业班级计科（嵌入）14-1 实验地点 学生姓名高晨悦学号 201403071007 同组人无 实验项目名称二叉树的递归算法 一、实验目的和要求 1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。 2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 二、实验环境 微型计算机vc 6.0 三、实验内容 1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。 2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 四、实验步骤 一．实验内容 1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。 2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 二．程序的设计思想 1实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。 先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则输入上一层右字树。 （1）二叉树的非递归遍历是用显示栈来存储二叉树的结点指针，先序遍历时，按二叉树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并将其指针入栈，如此反复执行则为非递归操作。 （2）二叉树的递归遍历：若二叉树为空，则空操作 先序遍历： （a）访问根结点； （b）先序遍历左子树； （c）先序遍历右子树。

中序遍历： （a）中序遍历左子树； （b）访问根结点； （c）中序遍历右子树 后序遍历： （a）后序遍历左子树； （b）后序遍历右子树； （c）访问根结点。 2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 （1）求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个数，再计算出两者之和即为二叉树的叶子结点数。 （2）二叉树的结点个数之和：先分别求得左子树右子树中结点之和，再计算两者之和即为所求。 （3）二叉树的高度：首先判断二叉树是否为空，若为空则此二叉树高度为0,。否则，就先分别求出左右子树的深度进行比较，取较大的树加一即为所求。 （4）二叉树的度为2的结点个数：计算有左右孩子的结点个数，即为度为2的结点个数。 三．编程过程中遇到的问题及解决办法 （1）后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简单，所以形成了死循环，总是在最后的节点处不停地循环，后改成回溯后，该问题得到解决。 （2）计算二叉树中度为2的结点个数中，返回循环的时候不论根结点有没有左右子树，但个人设计时，根总是会将自己默认为有左右子树，自行增加1.后在同学帮助下才看到自己的这个失误。 四．程序的闪光点(自我评价) 1.程序模块化，各个函数分开描述，方便观察 2.关键处有注释 3.建立二叉树时，用先序提示输入，比较人性化。 五．程序源代码(以文件为单位提供) #include #include #define Maxsize 100 typedef struct TREE{ struct TREE *lTree;

数据结构——二叉树的操作(遍历及树形输出)

/*实验三：二叉树遍历操作验证*/ #include #include #include #include #include

if(T) //若非空 { if(T->data) { //输出 printf("%c",T->data); } preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); } } //递归方法中序遍历二叉树 void inOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T->lchild); if(T->data) { //输出 printf("%c",T->data); } preOrderTraverse(T->rchild); } } //递归方法后序遍历二叉树 void postOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); if(T->data) { //输出 printf("%c",T->data); } } } //层序遍历二叉树 void LevelTraverse(BiTree T) { queue q;//建队 q.push(T);//根节点入队

数据结构算法背诵版

数据结构算法背诵 一、线性表 1.逆转顺序表中的所有元素 算法思想：第一个元素和最后一个元素对调，第二个元素和倒数第二个元素对调，……，依此类推。 void Reverse(int A[], int n) { int i, t; for (i=0; i < n/2; i++) { t = A[i]; A[i] = A[n-i-1]; A[n-i-1] = t; } } 2.删除线性链表中数据域为 item的所有结点 算法思想：先从链表的第 2个结点开始，从前往后依次判断链表中的所有结点是否满足条件，若某个 结点的数据域为 item，则删除该结点。最后再回过头来判断链表中的第 1个结点是否满足条件，若 满足则将其删除。 void PurgeItem(LinkList &list) { LinkList p, q = list; p = list->next; while (p != NULL) { if (p->data == item) { q->next = p->next; free(p); p = q->next;

} else { q = p; p = p->next; } } if (list->data == item) { q = list; list = list->next; free(q); } }

3.逆转线性链表 void Reverse(LinkList &list) { LinkList p, q, r; p = list; q = NULL; while (p != NULL) { r = q; q = p; p = p->next; q->next = r; } list = q; } 4.复制线性链表（递归） LinkList Copy(LinkList lista) { LinkList listb; if (lista == NULL) return NULL; else { listb = (LinkList)malloc(sizeof(LNode)); listb->data = lista->data; listb->next = Copy(lista->next); return listb; } }

数据结构利用栈实现递归

利用栈实现递归参考程序1（Turbo2.0环境）： #define MAXSIZE 100 #include struct stack{ int data[MAXSIZE]; int top; }; void init(struct stack *s){ s->top=-1; } int empty(struct stack *s){ if(s->top==-1) return 1; else return 0; } void push(struct stack *s,int i){ if(s->top==MAXSIZE-1){ printf("Stack is full\n"); return; } s->top++; s->data[s->top]=i; } int pop(struct stack *s){ if(empty(s)){ printf("stack is empty"); return -1; } return(s->data[s->top--]); } void trans(int num){ struct stack s; int k; init(&s); while(num){ k=num%16; push(&s,k); num=num/16; } while(!empty(&s)){ k=pop(&s); if(k<10)

printf("%d",k); else printf("%c",k+55); } printf("\n"); } main(){ int num; clrscr(); printf("Input a num,-1 to quit:\n"); scanf("%d",&num); while(num!=-1){ trans(num); scanf("%d",&num); } } 参考程序2：（C＋＋/VC环境） #define STACK_INIT_SIZE 100//存储空间初始分配量 #define OVERFLOW -1 #define OK 1 #define STACKINCREMENT 10//存储空间分配增量 #define ERROR 0 #define TRUE 1 #define FALSE 0 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #include "iostream.h" typedef int status; typedef char SElemType; typedef struct{//顺序栈的定义 SElemType *base; SElemType *top; int stacksize; }SqStack; status InitStack(SqStack &S){//构造一个空栈S S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW);//存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }

全国计算机二级考试 数据结构与算法

全国计算机二级考试 第一章数据结构与算法 1.一个算法一般都可以用_____、_____ 、 _____三种控制结构组合完成。 [解析]顺序、选择（分支）、循环（重复） 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是________。 [解析]算法的控制结构 在一般的计算机系统中，有算术运算、逻辑运算、关系运算和________四类基本的操作和运算。 [解析]数据传输 2.常用于解决“是否存在”或“有多少种可能”等类型的问题（例如求解不定方程的问题）的算法涉及基本方法是（） A．列举法 B.归纳法 C.递归法 D.减半递推法 [解析]列举就是列举出所有可能性，将所有可能性统统列举出来，然后解决问题的方法。所以A 3.根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的，这是算法设计基本方法中的____。 [解析]列举法

4.通过列举少量的特殊情况，经过分析，最后找出一般的关系的算法设计思想是（） A．列举法 B.归纳法 C.递归法 D.减半递推法 [解析]B 5.在用二分法求解方程在一个闭区间的实根时，采用的算法设计技术是（） A．列举法 B.归纳法 C.递归法 D.减半递推法 [解析]二分法就是从一半处比较，减半递推技术也称分治法，将问题减半。所以D 6.将一个复杂的问题归结为若干个简单的问题，然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止，这是算法设计基本方法中的___。如果一个算法P显式地调用自己则称为___。如果算法P调用另一个算法Q,而算法Q又调用算法P，则称为_____. [解析]递归法直接递归间接递归调用 7.算法中各操作之间的执行顺序称为_____。描述算法的工具通常有_____、_____ 、 _____。 [解析]控制结构传统流程图、N-S结构化流程图、算法描述语言 8.从已知的初始条件出发，逐步推出所要求的各中间结果和最后结果，这

数据结构中二叉树各种题型详解及程序

树是一种比较重要的数据结构，尤其是二叉树。二叉树是一种特殊的树，在二叉树中每个节点最多有两个子节点，一般称为左子节点和右子节点（或左孩子和右孩子），并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树是递归定义的，因此，与二叉树有关的题目基本都可以用递归思想解决，当然有些题目非递归解法也应该掌握，如非递归遍历节点等等。本文努力对二叉树相关题目做一个较全的整理总结，希望对找工作的同学有所帮助。 二叉树节点定义如下： structBinaryTreeNode { intm_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }; 相关链接： 轻松搞定面试中的链表题目 题目列表： 1. 求二叉树中的节点个数 2. 求二叉树的深度 3. 前序遍历，中序遍历，后序遍历 4.分层遍历二叉树（按层次从上往下，从左往右） 5. 将二叉查找树变为有序的双向链表 6. 求二叉树第K层的节点个数 7. 求二叉树中叶子节点的个数 8. 判断两棵二叉树是否结构相同 9. 判断二叉树是不是平衡二叉树 10. 求二叉树的镜像 11. 求二叉树中两个节点的最低公共祖先节点 12. 求二叉树中节点的最大距离 13. 由前序遍历序列和中序遍历序列重建二叉树 14.判断二叉树是不是完全二叉树 详细解答 1. 求二叉树中的节点个数 递归解法： （1）如果二叉树为空，节点个数为0 （2）如果二叉树不为空，二叉树节点个数= 左子树节点个数+ 右子树节点个数+ 1 参考代码如下： 1.int GetNodeNum(BinaryTreeNode * pRoot) 2.{ 3.if(pRoot == NULL) // 递归出口 4.return 0; 5.return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1; 6.}

数据结构知识点整理

数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号（数值、字符等）的集合。 数据元素（数据成员）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等 数据对象具有相同性质的数据元素（数据成员）的集合 数据结构由某一数据对象及该对象中所有数据成员之间的关系组成。记为Data_Structure = {D, R}其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 数据类型是指一种类型，以及定义在这个值集合上的一组操作的总称。 判断一个算法的优劣主要标准：正确性、可使用性、可读性、效率、健壮性、简单性。 算法效率的衡量方法：后期测试，事前估计 算法分析是算法的渐进分析简称 数据结构包括“逻辑结构”和“物理结构”两个方面(层次): 逻辑结构是对数据成员之间的逻辑关系的描述，它可以用一个数据成员的集合和定义在此集合上的若干关系来表示物理结构是逻辑结构在计算机中的表示和实现，故又称“存储结构” 线性表的定义：n（3 0）个表项的有限序列L =（a1, a2, …, an）ai是表项，n是表长度。第一个表项是表头，最后一个是表尾。 线性表的特点：表中元素的数据类型相同；线性表中，结点和结点间的关系是一对一的，有序表和无序表线性表的存储方式。一，顺序存储方式，二，链表存储方式。 顺序表的存储表示有2种方式：静态方式和动态方式。 顺序表的定义是：把线性表中的所有表项按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始的一块连续的存储空间中。 顺序表的特点：用地址连续的一块存储空间顺序存放各表项，各表项的逻辑顺序与物理顺序一致，对各个表项可以顺序访问，也可以随机访问。 单链表是一种最简单的链表表示，也叫线性链表，用她来表示线性表时，用指针表示结点间的逻辑关系。特点：是长度可以很方便地进行扩充。 连续存储方式（顺序表）特点：存储利用率高，存取速度快缺点：插入、删除等操作时需要移动大量数据： 链式存储方式（链表）特点：适应表的动态增长和删除。缺点：需要额外的指针存储空间

用递归和非递归算法实现二叉树的三种遍历

○A ○C ○D ○B ○E○F G 《数据结构与算法》实验报告三 ——二叉树的操作与应用 一.实验目的 熟悉二叉链表存储结构的特征，掌握二叉树遍历操作及其应用 二. 实验要求（题目） 说明：以下题目中（一）为全体必做，（二）（三）任选其一完成 （一）从键盘输入二叉树的扩展先序遍历序列，建立二叉树的二叉链表存储结构；（二）分别用递归和非递归算法实现二叉树的三种遍历； （三）模拟WindowsXP资源管理器中的目录管理方式,模拟实际创建目录结构,并以二叉链表形式存储,按照凹入表形式打印目录结构（以扩展先序遍历序列输入建立二叉链表结构），如下图所示: (基本要求:限定目录名为单字符;扩展:允许目录名是多字符组合) 三. 分工说明 一起编写、探讨流程图，根据流程图分工编写算法，共同讨论修改，最后上机调试修改。 四. 概要设计 实现算法，需要链表的抽象数据类型： ADT Binarytree { 数据对象：D是具有相同特性的数据元素的集合 数据关系R： 若D为空集，则R为空集，称binarytree为空二叉树；

若D不为空集，则R为{H}，H是如下二元关系； （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D－{root}不为空，则存在D－{root}＝{D1，Dr}，且D1∩Dr为空集； （3）若D1不为空，则D1中存在唯一的元素x1，∈H，且存在D1上的关系H1是H的子集；若Dr不为空集，则Dr中存在唯一的元素 Xr，∈H，且存在Dr上的关系Hr为H的子集；H={,,H1,Hr}; (4) (D1,{H1})是一颗符合本定义的二叉树，称为根的左子树，(Dr,{Hr}) 是一颗符合本定义的二叉树，称为根的右子树。 基本操作: Creatbitree(&S，definition) 初始条件：definition给出二叉树S的定义 操作结果：按definition构造二叉树S counter(T) 初始条件：二叉树T已经存在 操作结果：返回二叉树的总的结点数 onecount(T) 初始条件：二叉树T已经存在 操作结果：返回二叉树单分支的节点数 Clearbintree(S) 初始条件：二叉树S已经存在 操作结果：将二叉树S清为空树 Bitreeempty(S) 初始条件：二叉树S已经存在 操作结果：若S为空二叉树，则返回TRUE，否则返回FALSE Bitreedepth(S,&e) 初始条件：二叉树S已经存在 操作结果：返回S的深度 Parent(S) 初始条件：二叉树S已经存在，e是S中的某个结点 操作结果：若e是T的非根结点，则返回它的双亲，否则返回空Preordertraverse(S) 初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。 操作结果：先序遍历S，对每个结点调用函数visit一次且仅一次。 一旦visit失败，则操作失败。 Inordertraverse (S,&e) 初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。

c语言数据结构总结

数据结构大全 一、概论 二、线性表 三、栈和队列 四、串 五、多维数组和广义表 十、文件 六、树 七、图 八、排序 九、查找

一、概论 1、评价一个算法时间性能的主要标准是( 算法的时间复杂度)。 2、算法的时间复杂度与问题的规模有关外，还与输入实例的( 初始状态)有关。 3、一般，将算法求解问题的输入量称为( 问题的规模)。 4、在选择算法时，除首先考虑正确性外，还应考虑哪三点? 答：选用的算法首先应该是"正确"的。此外，主要考虑如下三点：①执行算法所耗费的时间；②执行算法所耗费的存储空间，其中主要考虑辅助存储空间；③算法应易于理解，易于编码，易于调试等等。 6、下列四种排序方法中，不稳定的方法是( D ) A、直接插入排序 B、冒泡排序 C、归并排序 D、直接选择排序 7、按增长率由小至大的顺序排列下列各函数： 2100, (3/2)n，(2/3)n，n n,n0.5 , n! ，2n，lgn ,n lgn, n3/2 答：常见的时间复杂度按数量级递增排列,依次为: 常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(n k)、指数阶0(2n)。显然，时间复杂度为指数阶0(2n)的算法效率极低，当n值稍大时就无法应用。先将题中的函数分成如下几类： 常数阶：2100 对数阶：lgn K次方阶：n0.5、n3/2 指数阶(按指数由小到大排)：n lgn、(3/2)n、2n、n!、n n 注意：(2/3)n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。 根据以上分析按增长率由小至大的顺序可排列如下： (2/3)n <2100 < lgn < n0.5< n3/2 < n lgn <(3/2)n < 2n < n! < n n 8、常用的存储表示方法有哪几种? 常用的存储表示方法：顺序存储方法、链接存储方法、索引存储方法、散列存储方法。 9、设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要（15）。 二、线性表 1、以下关于线性表的说法不正确的是( C )。 A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。 C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。 2、线性表是一种典型的( 线性)结构。 3、线性表的逻辑结构特征是什么? 答：对于非空的线性表:①有且仅有一个开始结点A1，没有直接前趋，有且仅有一个直接后继A2； ②有且仅有一个终结结点AN，没有直接后继，有且仅有一个直接前趋AN-1；③其余的内部结点AI （2≤I≤N-1）都有且仅有一个直接前趋AI-1和一个AI+1。 4、线性表的顺序存储结构是一种( 随机存取)的存储结构。线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续 5、在顺序表中，只要知道( 基地址和结点大小)，就可在相同时间内求出任一结点的存储地址。 6、在等概率情况下，顺序表的插入操作要移动( 一半)结点。

数据结构—— 树和二叉树知识点归纳

第6章树和二叉树 6.1 知识点概述 树（Tree）形结构是一种很重要的非线性结构，它反映了数据元素之间的层次关系和分支关系。在计算机科学中具有广泛的应用。 1、树的定义 树（Tree）是n（n≥0）个数据元素的有限集合。当n＝0时，称这棵树为空树。在一棵非空树T中： （1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。 （2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。 2、树的基本存储结构 （1）双亲表示法 由于树中的每一个结点都有一个唯一确定的双亲结点，所以我们可用一组连续的 存储空间（即一维数组）存储树中的结点。每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。 （2）孩子表示法 将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单 链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。 （3）双亲孩子表示法 双亲表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。 （4）孩子兄弟表示法 这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。 3、二叉树的定义 二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。 4、满二叉树 定义：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。 5、完全二叉树 定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。 6、二叉树的性质

数据结构与算法—递归与非递归转换

递归与非递归转换的基础知识是能够正确理解三种树的遍历方法：前序，中序和后序，第一篇就是关于这三种遍历方法的递归和非递归算法。 一、为什么要学习递归与非递归的转换的实现方法? 1>并不是每一门语言都支持递归的。 2>有助于理解递归的本质。 3>有助于理解栈，树等数据结构。 二、三种遍历树的递归和非递归算法 递归与非递归的转换基于以下的原理：所有的递归程序都可以用树结构表示出来。需要说明的是，这个”原理”并没有经过严格的数学证明，只是我的一个猜想，不过在至少在我遇到的例子中是适用的。学习过树结构的人都知道，有三种方法可以遍历树：前序，中序，后序。理解这三种遍历方式的递归和非递归的表达方式是能够正确实现转换的关键之处，所以我们先来谈谈这个。需要说明的是，这里以特殊的二叉树来说明，不过大多数情况下二叉树已经够用，而且理解了二叉树的遍历，其它的树遍历方式就不难了。 1>前序遍历 a>递归方式： void preorder_recursive(Bitree T> /* 先序遍历二叉树的递归算法 */ { if (T> { visit(T>。 /* 访问当前结点 */ preorder_recursive(T->lchild>。 /* 访问左子树 */ preorder_recursive(T->rchild>。 /* 访问右子树 */ } } b>非递归方式 void preorder_nonrecursive(Bitree T> /* 先序遍历二叉树的非递归算法 */

initstack(S>。 push(S,T>。 /* 根指针进栈 */ while(!stackempty(S>> { while(gettop(S,p>&&p> { /* 向左走到尽头 */ visit(p>。 /* 每向前走一步都访问当前结点 */ push(S,p->lchild>。 } pop(S,p>。 if(!stackempty(S>> { /* 向右走一步 */ pop(S,p>。 push(S,p->rchild>。 } } } 2>中序遍历 a>递归方式 void inorder_recursive(Bitree T> /* 中序遍历二叉树的递归算法 */ { if (T> { inorder_recursive(T->lchild>。 /* 访问左子树 */ visit(T>。 /* 访问当前结点 */ inorder_recursive(T->rchild>。 /* 访问右子树 */

数据结构课程总结

课程总结(提要) 一、数据结构和抽象数据类型ADT 定义：一个数学模型以及定义在该模型上的一组操作。 构成一个抽象数据类型的三个要素是： 数据对象、数据关系、基本操作 数据结构(非数值计算程序设计问题中的数学模型) ·逻辑结构（描述数据元素之间的关系） 线性结构——线性表、栈、队列、串、数组、广义表 非线性结构——树和森林、二叉树、图 集合结构——查找表、文件 ·存储结构（逻辑结构在存储器中的映象） 按“关系”的表示方法不同而分： 顺序结构—以数据元素在存储器中的一个固定的相对位置来表示“关系” 链式结构—以指针表示数据元素的“后继”或“前驱” ·基本操作(三类) 结构的建立和销毁 查找——引用型操作（不改变元素间的关系） 按“关系”进行检索 按给定值进行检索 遍历——访问结构中的每一个数据元素，且对每个元素只访问一次修改——加工型操作（改变元素间的关系） 插入 删除 更新（删除+插入）

二、线性结构 ·线性表和有序表 ——不同存储结构的比较 顺序表：可以实现随机存取；O(1) 插入和删除时需要移动元素；O(n) 需要预分配存储空间; 适用于“不常进行修改操作、表中元素相对稳定”的场合。 链表：只能进行顺序存取；O(n) 插入和删除时只需修改指针; O(1) 不需要预分配存储空间; 适用于“修改操作频繁、事先无法估计最大表长”的场合。 ——应用问题的算法时间复杂度的比较 例如，以线性表表示集合进行运算的时间复杂度为O(n2), 而以有序表表示集合进行运算的时间复杂度为O(n) ·栈和队列——数据类型的特点及其应用范畴 ·串——和线性表的差异： 数据对象不同（数据元素限定为单个字符）、基本操作集不同（串整体作为操作对象）、存储结构不同 ??串的模式匹配算法 ·数组——只有引用型的操作，∴只需要顺序存储结构 多维到一维的不同映象方法： 以行序为主序（低下标优先） 以列序为主序（高下标优先） ·广义表——多层次的线性结构 特性：次序性、长度、层次性、深度、递归等 独有的特性：共享 存储结构的特点

数据结构习题

树和二叉树习题（39） 1．请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink 法存储。2．假设K1，…，Kn 是n 个关键词，试解答： (1) 试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1， K2，…，Kn 时，用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。 (2) 设计一个算法，打印出该二叉查找树的嵌套括号表示结构。例如，K1=B，K2=A，K3=D，K4=C，K5=E，则用二叉查找树的插入算法建立的二叉查找树为： 该二叉查找树的嵌套括号表示结构为：B（A，D（C，E）） 3．写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针p 所指，其双亲结点由指针 f 所指，并假设被删除结点是其双亲结点的右孩子。用类PASCAL（或C）语言将上述算法写为过程形式。 4. 已知二叉树排序树中某结点指针p,其双亲结点指针为fp,p 为fp 的左孩子，试编写算法，删除p 所指结点。 5．二叉排序树采用二叉链表存储。写一个算法，删除结点值是X 的结点。要求删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的情况）。 6. 设记录R1,R2,…,Rn 按关键字值从小到大顺序存储在数组r[1..n]中,在r[n+1]处设立一个监督哨,其关键字值为+∞; 试写一查找给定关键字k 的算法;并画出此查找过程的判定树, 求出在等概率情况下查找成功时的平均查找长度。 7．设计算法以求解编号为i和j的两个结点的最近的公共祖先结点的编号。 8．元素集合已存入整型数组A[1..n]中，试写出依次取A 中各值A[i](1<=i<=n)构造一棵二叉排序树T 的非递归算法：CSBT(T,A) 9．写出折半查找的算法，并要求它返回整型值i，当查找成功时，返回查找位置，查找不成功时返回0。 10．请编写算法：键树，又称数字查找树。它是一棵度为>=2 的树，树中的每个结点中不

数据结构课程设计之-树与二叉树的转换

衡阳师范学院《数据结构》课程设计题目：树与二叉树的转换 系别：计算机科学系 专业：计算机科学与设计 班级：1302 学生姓名：戴志豪 学号：13190217 指导老师：赵磊 完成日期：2015年1月3号

目录 一．需求分析 (3) 二．概要设析 (3) 三．详细设计 (5) 1.树的建立 (5) 2.一般树转化成二叉树 (6) 3.先序遍历树的递归算法 (7) 4.后序遍历树的递归算法 (7) 5.先序遍历树的非递归算法 (7) 6.后序遍历树的非递归算法 (8) 7.层次序非递归的算法 (9) 四．设计与调试分析 (10) 五．用户手册 (10) 六．测试结果 (11) 七．附录（源程序） (14) 八．总结 (20)

一.需求分析 本程序的功能是对任意树进行递归前序遍历和后序遍历，以及实现树的非递归的前序、 和后序遍历，还有对树的层序遍历以及树与二叉树的转换。 二．概要设计 对于本次设计，需要用到树的建立,树与二叉树的转换算法先序后序二叉树的递归算法; 先序后序非递归算法;层次序遍历算法 1树的建立 用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为2*i+1 的值存入左孩子，为2*i+2的存入右孩子。 BiNode creat()，BiNode stree_creat(char *a,int k)。 开始 Y 参数数组是否空或 N 把数组的值赋给结点的数 返回空指针 递归的给左子树赋值参数变为a[2i+1] 递归的给右子树赋值参数变为a[2i+2] 返回根指针 结束 2一般树转化成二叉树 转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的右孩子。void exchange()，class Tree 3先序遍历树的递归算法 若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序 遍历右子树。void PreOrder(BiNode root)。

数据结构与算法分析论文(递归的讨论)

数据结构与算法分析论文 递归算法的讨论 学号 1415211013 姓名李莉姗 班级 14电子1班 华侨大学电子工程系

递归算法的讨论 所谓递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数)。递归过程一般通过函数或子过程来实现。递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法。递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。递归算法解决问题的特点： (1) 递归就是在过程或函数里调用自身。 (2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 (3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。 (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。下面就让我们结合例子详细讨论一下递归算法。 一、递归算法的原理 递归算法简单的说就是在函数中调用函数自身，不断调用，直到满足函数得出计算结果(某个条件)。因为其需要不断循环的调用自身，所以称为递归调用。递归的原理,其实就是一个栈(stack), 比如求5的阶乘,要知道5的阶乘,就要知道4的阶乘,4又要是到3的,以此类推,所以递归式就先把5的阶乘表示入栈, 在把4的入栈,直到最后一个,之后呢在从1开始出栈, 看起来很麻烦,确实很麻烦,他的好处就是写起代码来,十分的快,而且代码简洁,其他就没什么好处了,运行效率出奇的慢。还有一个十分形象的例子：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事……如此循环往复

数据结构(递归、数组、矩阵)练习题与答案

1、有一个三维数组A[-2..2][-4..5][2..6]，其中元素个数是 （）。 A.144 B.250 C.396 D.60 正确答案：B 解析： B、A的第1维长度为5，第2维长度为10，第3维长度为5，元素个数=5×10×5=250。 2、设C/C++二维数组a[m][n]，每个数组元素占用k个存储单元， 第一个数组元素的存储地址是LOC(a[0][0])，求按行优先顺序存放 的数组元素a[i][j]（0≤i≤m-1，0≤j≤n-1）的存储地址为（）。 A.LOC(a[0][0])+[(j-1)×m+i-1]×k B.LOC(a[0][0])+[i×n+j]×k C.LOC(a[0][0])+[(i-1)×n+j-1]×k D.LOC(a[0][0])+[j×m+i]×k 正确答案：B 解析： B、a[i][j]前面有0～i-1行，计i×n个元素，第i行前 面有j个元素，则a[i][j]前面有i×m+ j个元素，所以a[i][j]的 存储地址=LOC(a[0][0])+[i×n+j]×k。 3、设二维数组a[1..5][1..8]，若按行优先的顺序存放数组的元素，则a[4][6]元素的前面有（）个元素。 A.6 B.40 C.28

D.29 正确答案：D 解析： D、m=5，n=8，a[4][6]元素的前面的元素个数=(4-1) ×8+(6-1)=29。 4、设C/C++二维数组a[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放所有数组元素，a[3][5]的存储地址为1000，则a[0][0]的存储地址是（）。 A.864 B.868 C.860 D.872 正确答案：C 解析： C、C/C++二维数组下标从0开始。a[3][5]前面的元素个数=(3-0)×10+(5-0)=35。所以1000=LOC(a[0][0])+35×4， LOC(a[0][0])=860。 5、一个n阶对称矩阵A采用压缩存储方式，将其下三角部分（含主对角线元素）按行优先存储到一维数组B中，则B中元素个数是（）。 A.n(n+1)/2 B.n*n C.n(n+1)/2+1 D.n 正确答案：A

数据结构与算法课后习题答案

课后习题解答 判断题 1．线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√） 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）7．线性表的链式存储结构优于顺序存储结构。（×） 8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×） 11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×） 12．线性表的特点是每个元素都有一个前驱和一个后继。（×） 算法设计题 1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。 int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/ else {i=*elenum; while (i>=0 && A[i]>x) /*边找位置边移动*/ {A[i+1]=A[i]; i--; } A[i+1]=x; /*找到的位置是插入位的下一位*/ (*elenum)++; return 1; /*插入成功*/ }

数据结构复习重点归纳笔记[清华严蔚敏版]

一、数据结构的章节结构及重点构成 数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。 对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。 按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为： 概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。 线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题。如果有，也是与其它章节内容相结合。 栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。 串：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。 多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与“查找，排序”等章节结合来作为大题考查。 树和二叉树：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。 图：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。 查找：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。 排序：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，如果作为出题，那么常与数组结合来考查。 二、数据结构各章节重点勾划： 第0章概述 本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点：数据结构的基本概念，时间和空间复杂度的概念及度量方法，算法设计时的注意事项。本章考点不多，只要稍加注意理解即可。