下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
本文为二叉链存储结构的二叉树操作实现,实现了二叉树的定义、插入数据、删除数据、撤销以及二叉树的打印、前序遍历、中序遍历、后序遍历等。本项目工程包含2个头文件(BiTree.h、BiTreeTraverse.h)和一个源文件(BiTree.cpp)。头文件1BiTree.htypedefstructNode{DataTypedata; 〃数据域structNode*leftChild; 〃左子树指针structNode*rightChild;〃右子树指针}BiTreeNode; 〃结点的结构体定义/*初始化创建二叉树的头结点*/voidInitiate(BiTreeNode**root){*root=(BiTreeNode*)malloc(sizeof(BiTreeNode));(*root)->leftChild=NULL;(*root)->rightChild=NULL;}/*若当前结点curr非空,在curr的左子树插入元素之为x的新结点*//*原curr所指结点的左子树成为新插入结点的左子树*//*插入成功则返回新插入结点的指针,否则返回空指针*/BiTreeNode*InsertLeftNode(BiTreeNode*curr,DataTypex){BiTreeNode*s,*t;if(curr==NULL)returnNULL;t=curr->leftChild; /*保留原curr所指结点的左子树指针*/s=(BiTreeNode*)malloc(sizeof(BiTreeNode));s->data=x;s->leftChild=t; /*新插入结点的左子树为原curr的左子树*/s->rightChild=NULL;curr->leftChild=s; /*新结点成为curr的左子树*/returncurr->leftChild;/*返回新插入结点的指针*/}/*若当前结点curr非空,在curr的右子树插入元素之为x的新结点*//*原curr所指结点的右子树成为新插入结点的左子树*//*插入成功则返回新插入结点的指针,否则返回空指针*/BiTreeNode*InsertRightNode(BiTreeNode*curr,DataTypex){BiTreeNode*s,*t;if(curr==NULL)returnNULL;t=curr->rightChild; /*保留原curr所指结点的右子树指针*/s=(BiTreeNode*)malloc(sizeof(BiTreeNode));s->data=x;s->rightChild=t; /*新插入结点的右子树为原curr的左子树*/s->leftChild=NULL;curr->rightChild=s; /*新结点成为curr的右子树*/returncurr->rightChild;/*返回新插入结点的指针*/}voidDestory(BiTreeNode**root){//二叉树撤销操作if((*root)!=NULL&&(*root)->leftChild!=NULL)Destory(&(*root)->leftChild);if((*root)!=NULL&&(*root)->rightChild!=NULL)Destory(&(*root)->rightChild);free(*root);}/*若curr非空,删除curr所在结点的左子树*//*删除成功则返回删除结点的双亲指针,否则返回空*/BiTreeNode*DeleteLeftTree(BiTreeNode*curr){if(curr==NULLIIcurr->leftChild==NULL)returnNULL;Destory(&curr->leftChild);curr->leftChild=NULL;returncurr;}/*若curr非空,删除curr所在结点的右子树*//*删除成功则返回删除结点的双亲指针,否则返回空*/BiTreeNode*DeleteRightTree(BiTreeNode*curr){if(curr==NULLIIcurr->rightChild==NULL)returnNULL;Destory(&curr->rightChild);curr->rightChild=NULL;returncurr;}头文件2BiTreeTraverse.hvoidPreOrder(BiTreeNode*t,voidVisit(DataTypeitem)){//前序遍历二叉树t,访问操作为Visit()函数if(t!=NULL){Visit(t->data);PreOrder(t->leftChild,Visit);PreOrder(t->rightChild,Visit);}}voidInOrder(BiTreeNode*t,voidVisit(DataTypeitem)){//中序遍历二叉树t,访问操作为Visit()函数if(t!=NULL){PreOrder(t->leftChild,Visit);Visit(t->data);PreOrder(t->rightChild,Visit);}}voidPostOrder(BiTreeNode*t,voidVisit(DataTypeitem)){//后序遍历二叉树t,访问操作为Visit()函数if(t!=NULL){PreOrder(t->leftChild,Visit);PreOrder(t->rightChild,Visit);Visit(t->data);}}测试主函数BiTree・cpp#include<stdlib.h>#include<stdio.h>typedefcharDataType;#include"BiTree.h"#include"BiTreeTraverse.h"voidVisit(DataTypeitem){//定义访问函数printf("%c",item);}voidPrintBiTree(BiTreeNode*bt,intn){//定义打印函数,递归调用inti;if(bt==NULL)return; 〃递归出口PrintBiTree(bt->rightChild,n+l);〃遍历打印右子树〃访问根结点for(i=0;ivn;i++)printf(” ");if(n>=0){printf("---");printf(”%c\n",bt->data);}PrintBiTree(bt->leftChild,n+1);〃遍历打印左子树}voidmain(void){//测试主函数BiTreeNode*root,*p,*pp;〃遍历二叉树Initiate(&root);p=InsertLeftNode(root,'A');p=InsertLeftNode(p,'B');p=InsertLeftNode(p,'D');p=InsertRightNode(p,'G');p=InsertRightNode(root->leftChild,'C');pp=p;InsertLeftNode(p,'E');InsertRightNode(pp,'F');PrintBiTree(root,0);printf("前序遍历:”);P
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 土地整治项目施工方案
- 类风湿关节炎病历模板
- 危大工程安全管理措施
- 2026年一级造价工程师职业资格考试(建设工程技术与计量、安装工程)模拟试题及答案(河北张家口)
- 2026年度初级、中级经济师资格考试人力资源综合练习题及答案
- 2026年柳州勘察设计注册电气工程师考试(公共基础)全真题库及答案
- 2026年初级中级经济师考试建筑经济综合训练题库及答案
- 2026年护理查房七要素解析
- 2026年机关工具钳工技师考评模拟试题
- 2026年食品药品抽样员岗位考试题库含答案
- 传化物流工作制度规定
- 国标图集22K311-5《防排烟系统设备及部件选用与安装》解读
- 2025版建筑工程建筑面积计算规范
- 代建单位内部控制制度
- 猝死科普教学课件
- YB-T5034-2024《履带用热轧型钢》
- 气象公园施工方案(3篇)
- 按摩技师合作合同协议书
- 安省g1驾照考试题库及答案
- 华润万家顾客服务培训
- 2025公基题库(附答案解析)
评论
0/150
提交评论