首页 湖北理工(黄石理工)数据结构实验 实验四 二叉树的基本操作

湖北理工(黄石理工)数据结构实验 实验四 二叉树的基本操作

举报
开通vip

湖北理工(黄石理工)数据结构实验 实验四 二叉树的基本操作实验四 二叉树的基本操作 实验课程名:数据结构 专业班级: 09计科一班 学号: ** 姓名: ***** 实验时间:12.2—12.9 实验地点: k4--206 指导教师: 祁文青 一、实验目的 1、进一步掌握指针变量、动态变量的含义。 2、掌握二叉树的结构特性,以及各种存储结构的特点和适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。 二、实验内容 1、以二叉链表作存储结...

湖北理工(黄石理工)数据结构实验 实验四  二叉树的基本操作
实验四 二叉树的基本操作 实验课程名:数据结构 专业班级: 09计科一班 学号: ** 姓名: ***** 实验时间:12.2—12.9 实验地点: k4--206 指导教师: 祁文青 一、实验目的 1、进一步掌握指针变量、动态变量的含义。 2、掌握二叉树的结构特性,以及各种存储结构的特点和适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。 二、实验内容 1、以二叉链 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 作存储结构,试编程实现前序、中序、后序及层次顺序遍历二叉树的算法。 #include #include #include #include #define ClearBiTree DestroyBiTree typedef struct BiTNode { int data; BiTNode *lchild,*rchild; }BiTNode,*BiTree; void visit(int e) { printf("%d ",e); } void InitBiTree(BiTree &T) { T=NULL; } void CreateBiTree(BiTree &T) { int number; scanf("%d",&number); if(number==0) T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); if(!T) exit(OVERFLOW); T->data=number; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } void DestroyBiTree(BiTree &T) { if(T) { DestroyBiTree(T->lchild); DestroyBiTree(T->rchild); T=NULL; } } void PreOrderTraverse(BiTree T,void(*Visit)(int)) { if(T) { Visit(T->data); PreOrderTraverse(T->lchild,Visit); PreOrderTraverse(T->rchild,Visit); } } void InOrderTraverse(BiTree T,void(*Visit)(int)) { if(T) { InOrderTraverse(T->lchild,Visit); Visit(T->data); InOrderTraverse(T->rchild,Visit); } } void PostOrderTraverse(BiTree T,void(*Visit)(int)) { if(T) { PostOrderTraverse(T->lchild,Visit); PostOrderTraverse(T->rchild,Visit); Visit(T->data); } } void main() { BiTree T; InitBiTree(T); printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0\n"); CreateBiTree(T); printf("先序递归遍历二叉树:\n"); PreOrderTraverse(T,visit); printf("\n中序递归遍历二叉树:\n"); InOrderTraverse(T,visit); printf("\n后序递归遍历二叉树:\n"); PostOrderTraverse(T,visit); } 运行结果 2、以二叉链表作存储结构,试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法。 #include "iostream.h" #include "stdlib.h" #include "stdio.h" typedef int ElemType; typedef struct BTNode { ElemType data; struct BTNode *lchild,*rchild; }BTNode,* BiTree; void CreateBiTree(BiTree &T) { int ch; cin>>ch; if(ch==0) T=NULL; else { if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!"; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } int BTDepth(BiTree T) { if(!T) return 0; else { int h1=BTDepth(T->lchild); int h2=BTDepth(T->rchild); if(h1>h2) return h1+1; else return h2+1; } } int Leaf(BiTree T) { if(!T) return 0; else if(!T->lchild&&!T->rchild) return 1; else return(Leaf(T->lchild)+Leaf(T->rchild)); } int NodeCount(BiTree T) { if(!T) return 0; else return NodeCount(T->lchild)+NodeCount(T->rchild)+1; } int onesoncount(BiTree T) { if (T==NULL) return(0); else if ((T->lchild==NULL && T->rchild!=NULL) || (T->lchild!=NULL && T->rchild==NULL)) return(onesoncount(T->lchild)+onesoncount(T->rchild)+1); else return(onesoncount(T->lchild)+onesoncount(T->rchild)); } int twosoncount(BiTree T) { if (T==NULL) return 0; else if (T->lchild==NULL || T->rchild==NULL) return(twosoncount(T->lchild)+twosoncount(T->rchild)); else if (T->lchild!=NULL && T->rchild!=NULL) return(twosoncount(T->lchild)+twosoncount(T->rchild)+1); return 1; } void main() { BiTree T; T=NULL; cout<<"按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0"<data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } void NRPreOrder(BiTree bt) { BiTree stack[MaxLength],p; int top; if (bt!=NULL){ top=0;p=bt; while(p!=NULL||top>0) { while(p!=NULL) { cout<data; stack[top]=p; top++; p=p->lchild; } if (top>0) { top--; p=stack[top]; p=p->rchild; } } } } int NRInOrder(BiTree bt) { BiTree stack[MaxLength],p; int top; if (bt!=NULL){ top=0;p=bt; while(p!=NULL||top>0) { while(p!=NULL) { stack[top]=p; top++; p=p->lchild; } if (top>0) { top--; p=stack[top];cout<data; p=p->rchild; } } } return 0; } typedef struct { BiTree ptr; int tag; }stacknode; void NRPostOrder(BiTree bt) { stacknode s[MaxLength],x; BiTree p=bt; int top; if(bt!=NULL){ top=0;p=bt; do { while (p!=NULL) { s[top].ptr = p; s[top].tag = 1; top++; p=p->lchild; } while (top>0 && s[top-1].tag==2) { x = s[--top]; p = x.ptr; cout<data; } if (top>0) { s[top-1].tag =2; p=s[top-1].ptr->rchild; } }while (top>0);} } void main() { BiTree T; T=NULL; CreateBiTree(T); cout<<"先序遍历:"; NRPreOrder(T); cout<
本文档为【湖北理工(黄石理工)数据结构实验 实验四 二叉树的基本操作】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_788212
暂无简介~
格式:doc
大小:3MB
软件:Word
页数:9
分类:理学
上传时间:2012-05-31
浏览量:63