西南科技大学：《数据结构》课程教学资源（教案讲义）实验四 树（二）

,试验目的 1.进一步掌握指针变量,动态变量的含义 2.掌握二叉树的结构特征,以及各种存储结构的特点及使用范围 掌握用指针类型描述,访问二叉树的运算 ,试验内容 1.编写交换以二叉树连表作存储结构的二茬树中所有节点的左右子树的算法 [基本思想]设二叉树的根指针为t,且以二又树连表表示,可以利用一个类型为 seqstack 的指针来实现,且设栈单元包含两个域,一个为data,一个为top, 整个栈容量为 maxsize,当树为非空,将当前的树根节点入栈,同时将当前栈顶当作跟 节点,然后依据当前的根节点是否具有孩子节点来判断是否将其左右指针交换:;在间交 换后的左指针或右指针入栈,这样反复进行,直到栈为空 算法实现] #define null o typedef struct node int data struct node lchild rchild typedef int datatype;/栈元素的数据类型 define maxsize64∥栈可能达到的最大容量 typedef struct i datatype data maxsize; int top; } seqstack/顺序栈类型定义 seqstack*s;∥顺序栈类型指针 bitree *creat∥/建立二叉树 scanf(“&x) if(x==0) t=null: t=malloc(sizeof(bitree)) t->lchild=creato t->rchild=creato return t: void inorder(t)/中序遍历二叉树 bitree *t:

一，试验目的 1． 进一步掌握指针变量，动态变量的含义。 2． 掌握二叉树的结构特征，以及各种存储结构的特点及使用范围 3． 掌握用指针类型描述，访问二叉树的运算 二，试验内容 1． 编写交换以二叉树连表作存储结构的二茬树中所有节点的左右子树的算法。 [基本思想]设二叉树的根指针为 t，且以二叉树连表表示，可以利用一个类型为 seqstack 的指针来实现，且设栈单元包含两个域，一个为 data，一个为 top， 整个栈容量为 maxsize，当树为非空，将当前的树根节点入栈，同时将当前栈顶当作跟 节点，然后依据当前的根节点是否具有孩子节点来判断是否将其左右指针交换；在间交 换后的左指针或右指针入栈，这样反复进行，直到栈为空 [算法实现] #define null o typedef struct node { int data; struct node lchild ,rchild; }bitree; typedef int datatype ;//栈元素的数据类型 #define maxsize 64 //栈可能达到的最大容量 typedef struct { datatype data[maxsize]; int top; }seqstack//顺序栈类型定义 seqstack *s;// 顺序栈类型指针 bitree *creat()//建立二叉树 { bitree *t; int x; scanf(“&x); if(x==0) t=null; else { t=malloc(sizeof(bitree)); t->data=x; t->lchild=creat(); t->rchild=creat(); } return t; } void inorder(t)//中序遍历二叉树 bitree *t;

if(tl=null) inorder(t->lchild); inorder(t->rchild); exchange(t)/对二叉树t所有结点左右子树进行交换 bitree *t p seqstack*s;/为一指针栈,类型为 seqstack if(t) S->top=l; > data s->topl=t;/跟指针t进栈 t=s> datas->topl;/栈顶元素退栈 if((t->lchild! =null(t->rchild: =null)) p=t->lehd;/节点的左右指针交换 t->lchild=t->rchild t->rchild=p: if(t- . lchild!=nu)交换后的左孩子指针入栈 s->data s->topl=t->lchild if( t->rchild!=nu)交换后的右孩子指针入栈 s->data s->top=t->rchild; } while(s>top==0)栈空结束 no

{ if(t!=null) { inorder(t->lchild); prinrf(t->data); inorder(t->rchild); } exchange(t)//对二叉树 t 所有结点左右子树进行交换 bitree *t { bitree *p; seqstack *s;//为一指针栈，类型为 seqstack if(t) { s->top=1; s->data[s->top]=t;//跟指针 t 进栈 do { t=s->data[s->top];//栈顶元素退栈 s->top--; if((t->lchild!=null)||(t->rchild!=null)) { p=t->lchild;//节点的左右指针交换 t->lchild=t->rchild; t->rchild=p; } if(t->lchild!=null)//交换后的左孩子指针入栈 { s->top++; s->data[s->top]=t->lchild; } if(t->rchild!=null)//交换后的右孩子指针入栈 { s->top++; s->data[s->top]=t->rchild; } }while(s->top==0)/栈空结束 } } main()

bitree "root: hange(root); inorder(root); 对于 exchange算法也可以利用以下的地归算法 bitree*t: (bitree*p; if(tl=null) p=t->lchild; t->lchild=t->rchild; t->rchild=p: exchange(t->rchild); 2已知以二叉表做存储结构,试编写安层次顺序便历二叉树的算法 算法思想|本算法要采用一个队列q,先将二叉树根节点入队列,然后退队列,输出该 节点,若它有左子树,便将左子树根节点入队列,若它有右子树,边将右子树根节点 入队列,如此直到队列为空为止,因为对列的特点是先进先出,从而达到安层次顺序 遍历二叉树的目的 算法实现! typedef struct node struct node lchild, rchild bitree*quem; int front=0, rear=0; t=null

{ bitree *root; root=creat(); inorder(root); exchange(root); inorder(root); } 对于 exchange 算法也可以利用以下的地归算法 void exchange(t) bitree *t; {bitree *p; if(t!=null) { p=t->lchild; t->lchild=t->rchild; t->rchild=p; exchange(t->lchild); exchange(t->rchild); } } 2.已知以二叉表做存储结构，试编写安层次顺序便历二叉树的算法 [算法思想]本算法要采用一个队列 q，先将二叉树根节点入队列，然后退队列，输出该 节点，若它有左子树，便将左子树根节点入队列，若它有右子树，边将右子树根节点 入队列，如此直到队列为空为止，因为对列的特点是先进先出，从而达到安层次顺序 遍历二叉树的目的 [算法实现] #define m 100 #define null 0 typedef struct node { int data; struct node lchild ,rchild; }bitree; bitree *que[m]; int front=0,rear=0; bitree *creat() { bitree *t; int x; scanf(&x); if(x==0) t=null; else

t=malloc(sizeof(bitree)) t->rchild=creat(; return t: bitree*t: if(t!=null) inorder(t->lchild); printf(t->data); inorder(t->rchild) void enqueue(t) if(front!=(rear+1)%m) rear(rear+1)%m; quelrearl=t; bitree*dequeue if(front==rear) front=(front+1)%m return(quel front) void leborder(t) (bitree"p; if(t=null) hile(front =rear) p=dequeue

{ t=malloc(sizeof(bitree)); t->data=x; t->lchild=creat(); t->rchild=creat(); } return t; } void inorder(t) bitree *t; { if(t!=null) { inorder(t->lchild); printf(t->data); inorder(t->rchild); } } void enqueue(t) bitree *t; { if(front!=(rear+1)%m) { rear=(rear+1)%m; que[rear]=t; } } bitree *delqueue() { if(front==rear) return null; front=(front+1)%m; return (que[front]); } void leborder(t) bitree *t; {bitree *p; if(t!=null) { enqueue(t); while(front!=rear) { p=delqueue(); printf(p->data);

if(p->lchild:=null) eue(p if(p- enqueue(p->rchild); t bitree *root; printf("In”); levorder(root); 也可以用非递归写出 desorder算法。可以用一个对列que遍历过程中的各个节点。由 于二叉树以二叉连表存储,所以que为一个指向数据类型为bire指针数组最大容 量为 maxsize,下标从1开始,同层结点从左到右存放。其中 front为队头指针,rear为 尾指针 levlorder(t)∥安层遍历二叉树t bitree*t;二叉树t为类型 bitree bitree*quelmaxsizel 队列que为一个指向类型指针数组,下标从1开始 front; if(t) front=0;/置空对列 assize+;/出列 printf(t->data); of(t->rchd!=nu)/左子树的根结点入队 rearrear%maxsize +1: quelrearl=t->lchild

if(p->lchild!=null) enqueue(p->lchild); if(p->rchild!=null) enqueue(p->rchild); } } } main() {bitree *root; printf(“\n”); root=creat(); inorder(root); printf(“\n”); levorder(root); } 也可以用非递归写出 levorder 算法。可以用一个对列 que 遍历过程中的各个节点。由 于二叉树以二叉连表存储，所以 que 为一个指向数据类型为 bitree 的指针数组最大容 量为 maxsize,下标从 1 开始，同层结点从左到右存放。其中 front 为队头指针，rear 为 尾指针 levlorder(t)//安层遍历 二叉树 t bitree *t;//二叉树 t 为类型 bitree { bitree *que[maxsize] //队列 que 为一个指向类型指针数组，下标从 1 开始 int rear, front; if(t) { front=0;//置空对列 rear=1; que[1]=t; do{ front=front%maxsize+1;//出列 t=que[front]; printf(t->data); of(t->rchild!=null)//左子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->lchild; }

if( t->rchild!=nul)/右子树的根结点入队 ear=rear%maxsize+1; quelrearl=t->rchild 3.已知叉排序树一二叉表作为存储结构,试编写安从达到小的顺序输出二叉排序树的 各结点算法 「算法思想可以先建立一颗二叉排序树,一二叉连表表示,由于安中序遍历二叉排 序树即为安递增次序遍历,所以要按从达到小的顺序输出二叉排序树的各结点的 值,可以对二叉排序树从树根结点右子树中最右下结点开始进行遍历,先遍历右 子树,在访问根结点,最后遍历左子树 这样就可以得到一个安从大到小的顺序输出的序列。 算法实现 #define null 0 typedef struct node/二叉树连表类型定义 Rint dat struct node *lchild. "rchild void destorder(t)从右子树开始遍历二叉树 bitree *insertbst(t,s)/将新结点插入到t所指的二叉树中 hile(p! =null (f=p; f(s->data==p->data)return t; >data)p=p->lchild

if(t->rchild!=null) //右子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->rchild; } }while(rear==front); } } 3． 已知叉排序树一二叉表作为存储结构，试编写安从达到小的顺序输出二叉排序树的 各结点算法。 [算法思想]可以先建立一颗二叉排序树，一二叉连表表示，由于安中序遍历二叉排 序树即为安递增次序遍历，所以要按从达到小的顺序输出二叉排序树的各结点的 值，可以对二叉排序树从树根结点右子树中最右下结点开始进行遍历，先遍历右 子树，在访问根结点，最后遍历左子树 这样就可以得到一个安从大到小的顺序输出的序列。 [算法实现] #define m 100 #define null 0 typedef struct node//二叉树连表类型定义 {int data; struct node *lchild,*rchild; }bitree; void destorder(t)//从右子树开始遍历二叉树 bitree *t; { if(t!=null) {destorder(t->rchild); printf(t->data); destorder(t->lchild); } bitree *insertbst(t,s)//将新结点插入到 t 所指的二叉树中 bitree *s,*p; { bitree *f,*p; p=t; while(p!=null) {f=p; if(s->data==p->data)return t; if(s->datadata) p=p->lchild;

f(t=nullreturn s: (s->keykey)f->lchild=s f->rchild=s: return t; bitree*creatordo/返回二叉树 while(x!=0) smalloc(sizeof( bitree)) s->lchild=null: t=inserts(t, s) scanf(&x) return t: bitree *root: printf("In”); destorder(root); printf("In”);

else p=p->rchild; } if(t==null)return s; if(s->keykey)f->lchild=s; else f->rchild=s; return t; } bitree *creatord()//返回二叉树 ｛bitree *t, *s; int x; t=null; scanf(&x); while(x!=0) { s=malloc(sizeof(bitree)); s->data=x; s->lchild=null; s->rchild=null; t=insertbst(t,s); scanf(&x); } return t; } main() { bitree *root; printf(“\n”); root=creatord(); destorder(root); printf(“\n”); }