《《二叉树的建立》ppt课件》由会员分享，可在线阅读，更多相关《《二叉树的建立》ppt课件（42页珍藏版）》请在金锄头文库上搜索。
1、1,二叉树的建立,循 环 链 表,文 件 操 作,2,二叉树的建立,3,二叉树的建立,建立二叉树的过程是一个“插入”过程，下面我们用一个例子来讲解这一过程。 我们想建立这样一棵二叉树，树中的每一个结点有一个整数数据名为data，有两个指针：左指针L，右指针R，分别指向这个结点的左子树和右子树，显然可以用如下名为TREE的结构来描述这种结点： struct TREE int data; struct TREE *L, *R; ,4,对二叉树最重要的是根，它起定位的作用，因此，首先建立的是根结点。也就是说，如果从键盘输入数据来建立二叉树，第一个数据就是这棵树的根的数据，之后再输入的数据，每一个都要
2、与根中的数据作比较，以便确定该数据所在结点的插入位置。假定我们这里依然用图1的中序遍历的方式。即如果待插入结点的数据比根结点的数据小，则将其插至左子树，否则插入右子树。 定义一个递归函数 void insert(struct TREE *proot, struct TREE *p) 其中，指针p指向含有待插入数据的结点。 proot为树的根指针的地址。 insert函数棵理解为将p结点插入到*proot所指向的树中。,5,insert(proot, p)可用下列与或结点图来描述,6,注意在上图中proot是被调用函数的形参。从前面对它的定义看，proot是指针的指针，实际上是指向二叉树根结点的
3、指针的指针，或者说是指向二叉树根结点的指针的地址。如下图。因此，在主程序调用insert函数时，,根结点,proot,实参,&root,实参为 &root, p 形参为 proot, p 下面是建立二叉树的参考程序。,7,#include / 预编译命令 #include / 内存空间分配 #define null 0 / 定义空指针常量 #define LEN sizeof(struct TREE) / 定义常量，表示结构长度 struct TREE / 结构声明 int data; / 整型数 struct TREE *L,*R; / TREE结构指针 ;,8,/ 被调用函数insert，
4、将结点插入二叉树 void insert (struct TREE *proot, struct TREE* p) / 函数体开始 if (*proot=null) / 如果根结点为空 *proot = p; / 将结点p插入根结点 return; / 返回 else / 根结点不为空 / 如果p结点数据小于等于根结点数据 if (p-data data) insert( / 插入右子树 / 函数体结束,9,/ 被调用函数，形参为TREE结构指针，输出二叉树内容 void print(struct TREE *root) / 函数体开始 if (root = null) / 根或子树根结点为空
5、 return; / 返回 print(root-L); / 输出左子树内容 printf(“%d“,root-data);/ 输出根结点内容 print(root-R); / 输出右子树内容 / 被调用函数结束 void main() / 主函数开始 / 函数体开始 struct TREE *root, *p; / TREE型结构指针 int temp; / 临时变量，用于用户输入数据 root = null; / 初始化二叉树根结点为空 p = null; / 初始化待插入结点的指针为空 printf(“请输入待插入结点的数据n“); / 提示信息 printf(“如果输入-1表示插入过程
6、结束n“);/ 提示信息 scanf(“%d“, / 输入待插入结点数据,10,while(temp != -1) / 当型循环，-1为结束标志 / 循环体开始 / 为待插入结点分配内存单元 p = (struct TREE *) malloc(LEN); p-data = temp; / 将temp赋值给p结点的数据域 p-L = p-R = null; / 将p结点的左右指针域置为空 insert( / 调用print函数，输出二叉树内容 / 主函数结束,11,循 环 链 表,12,循环链表,例：猴子选大王。 n只猴子围成一圈，顺时针方向从1到n编号。之后从1号开始沿顺时针方向让猴子从1，
7、2，m依次报数，凡报到m的猴子，都让其出圈，取消候选资格。然后不停地按顺时针方向逐一让报出m者出圈，最后剩下一个就是猴王。,13,起始位置,猴 王,1,2,3,4,5,6,7,8,3,6,1,5,2,8,4,猴子被淘汰的顺序,演示：n=8, m=3,14,说明： 如图1所示有8只猴子围成一圈，m=3。从1#猴的位置开始，顺时针1至3报数，第一个出圈的是3#；第二个出圈的是6#，第3个出圈的是1#；第4个出圈的是5#；第5个是2#，第6个是8#；第7个是4#。最后剩下一个是7#，它就是猴王。 我们用循环链表来模拟这个选择过程。,15,1、定义一个名为mon的结构 struct mon int n
8、um; / 整数，表示猴子的编号 struct mon *next; / 指针，指向相邻的下一只猴子 2、将链表的头指针head定义为全局变量。 struct mon*head; 3、主函数 用键盘输入猴子数n，输入数m，调用函数create建立一个循环链表，模拟众猴围成一圈的情况。该函数的实参为n。调用函数select，模拟1至m报数，让n-1只猴子逐一出列的过程。即在具有n个结点的循环链表按报数m删除结点的过程。该函数的实参为m，最后输出猴王的编号。,16,4、建立循环链表的函数create(int nn) 其中nn为形式参数。要从编号1到编号nn。思路是 （1）先做第1个结点，让其中的数
9、据域p-num赋值为1，让指针域赋值为null。之后让链头指针head指向第1个结点。利用指针q记住这个结点，以便让指针p去生成下面的结点。 （2）利用一个计数循环结构，做出第2个结点到第nn个结点。并将相邻结点一个接一个链接到一起。 （3）最后一个结点要和头结点用下一语句链接到一起 tail = q; tail-next = head;,head,tail,q,17,5、删结点的函数select(int mm) mm为形式参数，从1至m报数，凡报到mm者删除其所在的结点。 设计两个指针p和q。一开始让q指向链表的尾部q=tail。让p指向q的下一个结点。开始时让p指向1#猴所在的结点。用一个
10、累加器x，初始时x=0，从1#猴所在结点开始让x=x+1=1，如果mm是1的话，1#猴所在的p结点就要被删除。有三条语句 printf(“被删掉的猴子号为%d号n”,p-num); q-next = p-next; free(p);,head,tail,q,p,演示,18,这里free(p)是释放p结点所占用的内存空间的语句。如果mm不是1而是3，程序会在do-while循环中，让x加两次1，q和p一起移动两次，p指向3#所在结点，q指向2#所在结点，之后仍然用上述三条语句删去3#所在的结点。,head,q,p,q,p,p,q,演示,19,这个do-while循环的退出条件是q=q-next。
11、即当只剩下一个结点时才退出循环。当然猴王非其莫属了。这时，让头指针head指向q，head是全局变量，在主程序最后输出猴王时要用head-num。,参考程序如下：,head,q,20,#include / 预编译命令 #include / 内存空间分配 #define null 0 / 定义空指针常量 / 定义常量，表示结构长度 #define LEN sizeof(struct mon) struct mon / 结构声明 int num; / 整型数，用于记录猴子号 struct mon *next; / mon结构指针 ; struct mon *head, *tail; / mon结构
12、指针，全局变量,21,void create(int nn) / 被调用函数 / 函数体开始 int i; / 整型变量i，用于计数 struct mon *p,*q; / 声明mon结构指针p，q / 为p分配内存空间 p=(struct mon *) malloc(LEN); p-num=1; / 初始化p结点num域为1 p-next=null; / 初始化p结点next域为空 head=p; / 链表头指针head赋值为p q=p; / q赋值为p,22,for(i=2;inum=i; / 初始化p结点num域为i，表示猴子号 q-next=p; / 将p结点加到链表尾部 q=p; /
13、 让q指向链表尾部结点 p-next=null; / 链表尾部指向空 / 循环体结束 tail = q; / 链表尾 tail-next=head; / 链表尾部指向链表头， / 形成循环链表 / 函数体结束,23,/ 被调用函数select，mm表示结点删除间隔 void select(int mm) / 函数体开始 int x=0; / 声明整型值x，并初始化为0 struct mon *p,*q; / 声明结构指针p，q q=tail; / q赋值为tail，指向循环链表尾部 do / 直到型循环，用于循环删除指定间隔的结点 / 循环体开始 p=q-next; / p赋值为q相邻的下一个
14、结点 x=x+1; / x加1 if(x % mm=0) / x是否整除mm， / 表示是否跳过指定间隔 / 输出被删掉的猴子号 printf(“被删掉的猴子号为%d号n“,p-num); q-next=p-next; / 删除此结点 free(p); / 释放空间 else q=p; / q指向相邻的下一个结点p while(q!=q-next); / 剩余结点数不为1，则继续循环 head = q; / head指向结点q，q为链表中剩余的一个结点 / 函数体结束,24,void main() / 主函数开始 / 函数体开始 int n,m; / 声明整型变量n,m head = null
15、; / 初始化head为空 printf(“请输入猴子数n“); / 提示信息 scanf(“%d“, / 输出猴王 / 函数体结束,25,第十三讲 文件,26,有关文件的概念和名词,文件是信息的集合，是信息存放在外存中的一种形式。可以长期保存。 EOF文件的结束符。 C语言中的文件视为信息流，文件的读写是按顺序进行的。可以以字符为单位读写，也可以以“行”为单位读写。一行是以“n”为结束的一串字符。 文件指针是指向含有文件信息结构的指针。文件指针又称内部文件名。 对文件进行操作，先要将文件打开。所谓“打开文件”，就是在内存中为文件建立一个缓冲区，文件指针就要指向缓冲区的首地址。,27,标准文件,C语言中规定的标准文件有三个： 1、标准输入文件（键盘），文件指针为stdin; 2、标准输出文件（显示屏幕），文件指针为stdout; 3、标准出错信息文件，文件指针为stderr。 特点是这些文件在操作前或后，系统会自动将其打开或关闭，程序不需管。,28,一般文件,特点：操作前需打开，操作后需关闭。开和闭均是通过函数进行的。 打开文件就是要在内存中建立缓冲区，如打开成功，打开函数返回一个内存地址值，由一个文件指针接收。以后的操作使用这个指针。如内存不
