欢迎来到天天文库
浏览记录
ID:17417422
大小:48.00 KB
页数:19页
时间:2018-08-31
《数据结构c语言版 二叉树的三叉链表存储表示》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、数据结构C语言版二叉树的三叉链表存储表示数据结构C语言版二叉树的三叉链表存储表示.txt/*数据结构C语言版二叉树的三叉链表存储表示编译环境:Dev-C++4.9.9.2日期:2011年2月13日*/#include#includetypedefcharTElemType;//二叉树的三叉链表存储表示typedefstructBiTPNode{TElemTypedata;structBiTPNode*parent,*lchild,*rchild;//双亲、左右孩子指针}BiTPNode,*BiPTree;typedefBiP
2、TreeQElemType;//设队列元素为二叉树的指针类型typedefstructQNode{QElemTypedata;//数据域structQNode*next;//指针域}QNode,*QueuePtr;typedefstruct{QueuePtrfront,//队头指针,指针域指向队头元素rear;//队尾指针,指向队尾元素}LinkQueue;TElemTypeNil='';//字符型以空格符为空//构造空二叉树TintInitBiTree(BiPTree*T){*T=NULL;return1;}//销毁二叉树TvoidDestroyBiTree(
3、BiPTree*T){if(*T)//非空树{if((*T)->lchild)//有左孩子DestroyBiTree(&(*T)->lchild);//销毁左孩子子树if((*T)->rchild)//有右孩子DestroyBiTree(&(*T)->rchild);//销毁右孩子子树free(*T);//释放根结点*T=NULL;//空指针赋0}}#defineClearBiTreeDestroyBiTree//按先序次序输入二叉树中结点的值(可为字符型或整型,在主程中定义),//构造仅缺双亲指针的三叉链表表示的二叉树T。变量Nil表示空(子)树voidCre
4、ate(BiPTree*T)//CreateBiTree()调用{TElemTypech;scanf("%c",&ch);if(ch==Nil)//空*T=NULL;else{*T=(BiPTree)malloc(sizeof(BiTPNode));if(!*T)exit(0);(*T)->data=ch;//生成根结点Create(&(*T)->lchild);//构造左子树Create(&(*T)->rchild);//构造右子树}}//构造一个空队列QintInitQueue(LinkQueue*Q){(*Q).front=(*Q).rear=(Queue
5、Ptr)malloc(sizeof(QNode));//动态分配一个空间if(!(*Q).front)exit(0);(*Q).front->next=NULL;//队头指针指向空,无数据域,这样构成了一个空队列return1;}//若Q为空队列,则返回1,否则返回0intQueueEmpty(LinkQueueQ){if(Q.front==Q.rear)return1;elsereturn0;}//插入元素e为Q的新的队尾元素intEnQueue(LinkQueue*Q,QElemTypee){QueuePtrp=(QueuePtr)malloc(sizeof
6、(QNode));if(!p)//存储分配失败exit(0);//生成一个以为e为数据域的队列元素p->data=e;p->next=NULL;//将该新队列元素接在队尾的后面(*Q).rear->next=p;(*Q).rear=p;return1;}//若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0intDeQueue(LinkQueue*Q,QElemType*e){QueuePtrp;if((*Q).front==(*Q).rear)return0;p=(*Q).front->next;//队头元素*e=p->data;(*Q).fro
7、nt->next=p->next;if((*Q).rear==p)(*Q).rear=(*Q).front;free(p);return1;}//按先序次序输入二叉树中结点的值(可为字符型或整型,在主程中定义),//构造三叉链表表示的二叉树TintCreateBiTree(BiPTree*T){LinkQueueq;QElemTypea;Create(T);//构造二叉树(缺双亲指针)if(*T)//非空树{(*T)->parent=NULL;//根结点的双亲为"空"InitQueue(&q);//初始化队列EnQueue(&q,*T);//根指针入队while
8、(!QueueEmpty
此文档下载收益归作者所有