计算机语言与程序设计 (13)

《计算机语言与程序设计 (13)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二叉树的建立循环链表文件操作1二叉树的建立2二叉树的建立建立二叉树的过程是一个“插入”过程，下面我们用一个例子来讲解这一过程。我们想建立这样一棵二叉树，树中的每一个结点有一个整数数据名为data，有两个指针：左指针L，右指针R，分别指向这个结点的左子树和右子树，显然可以用如下名为TREE的结构来描述这种结点：structTREE{intdata;structTREE*L,*R;}3对二叉树最重要的是根，它起定位的作用，因此，首先建立的是根结点。也就是说，如果从键盘输入数据来建立二叉树，第一个数据就是这棵树的根的数据，之后再输入的数据，每一个

2、都要与根中的数据作比较，以便确定该数据所在结点的插入位置。假定我们这里依然用图1的中序遍历的方式。即如果待插入结点的数据比根结点的数据小，则将其插至左子树，否则插入右子树。定义一个递归函数voidinsert(structTREE**proot,structTREE*p)其中，指针p指向含有待插入数据的结点。proot为树的根指针的地址。insert函数棵理解为将p结点插入到*proot所指向的树中。4insert(proot,p)可用下列与或结点图来描述5注意在上图中proot是被调用函数的形参。从前面对它的定义看，proot是指针的指针

3、，实际上是指向二叉树根结点的指针的指针，或者说是指向二叉树根结点的指针的地址。如下图。因此，在主程序调用insert函数时，根结点proot实参&root实参为&root,p形参为proot,p下面是建立二叉树的参考程序。6#include//预编译命令#include//内存空间分配#definenull0//定义空指针常量#defineLENsizeof(structTREE)//定义常量，表示结构长度structTREE//结构声明{intdata;//整型数structTREE*L,*R;//T

4、REE结构指针};7//被调用函数insert，将结点插入二叉树voidinsert(structTREE**proot,structTREE*p){//函数体开始if(*proot==null)//如果根结点为空{*proot=p;//将结点p插入根结点return;//返回}else//根结点不为空{//如果p结点数据小于等于根结点数据if(p->data<=(*proot)->data)insert(&((*proot)->L),p);//插入左子树else//如果p结点数据大于等于根结点数据insert(&((*proot)->R)

5、,p);//插入右子树}}//函数体结束8//被调用函数，形参为TREE结构指针，输出二叉树内容voidprint(structTREE*root){//函数体开始if(root==null)//根或子树根结点为空return;//返回print(root->L);//输出左子树内容printf("%d",root->data);//输出根结点内容print(root->R);//输出右子树内容}//被调用函数结束voidmain()//主函数开始{//函数体开始structTREE*root,*p;//TREE型结构指针inttemp;/

6、/临时变量，用于用户输入数据root=null;//初始化二叉树根结点为空p=null;//初始化待插入结点的指针为空printf("请输入待插入结点的数据");//提示信息printf("如果输入-1表示插入过程结束");//提示信息scanf("%d",&temp);//输入待插入结点数据9while(temp!=-1)//当型循环，-1为结束标志{//循环体开始//为待插入结点分配内存单元p=(structTREE*)malloc(LEN);p->data=temp;//将temp赋值给p结点的数据域p->L=p->R=nul

7、l;//将p结点的左右指针域置为空insert(&root,p);//将p结点插入到根为root的树中，//&root表示二叉树根结点的地址printf("请输入待插入结点的数据");//提示信息printf("如果输入-1表示插入过程结束");//提示信息scanf("%d",&temp);//输入待插入结点数据}//循环体结束if(root==null)//如果根结点为空printf("这是一棵空树。");//输出空树信息else//根结点不为空print(root);//调用print函数，输出二叉树内容}//主函数结束1

8、0循环链表11循环链表例：猴子选大王。n只猴子围成一圈，顺时针方向从1到n编号。之后从1号开始沿顺时针方向让猴子从1，2，…，m依次报数，凡报到m的猴子，都让其出圈，取消候选资格