数据结构C语言版-二叉树的三叉链表存储表示.doc

《数据结构C语言版-二叉树的三叉链表存储表示.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构C语言版二叉树的三叉链表存储表示.txt大悲无泪，大悟无言，大笑无声。我们手里的金钱是保持自由的一种工具。女人在约会前，一定先去美容院；男人约会前，一定先去银行。/*数据结构C语言版二叉树的三叉链表存储表示编译环境：Dev-C++4.9.9.2日期：2011年2月13日*/#include#includetypedefcharTElemType;//二叉树的三叉链表存储表示typedefstructBiTPNode{TElemTypedata;structBiTPNode*parent,*lchild,*rchild;//双亲、左右孩子指针}

2、BiTPNode,*BiPTree;typedefBiPTreeQElemType;//设队列元素为二叉树的指针类型typedefstructQNode{QElemTypedata;//数据域structQNode*next;//指针域}QNode,*QueuePtr;typedefstruct{QueuePtrfront,//队头指针，指针域指向队头元素rear;//队尾指针，指向队尾元素}LinkQueue;TElemTypeNil='';//字符型以空格符为空//构造空二叉树TintInitBiTree(BiPTree*T){*T=NULL;return1;}//销毁二叉树Tvoi

3、dDestroyBiTree(BiPTree*T){if(*T)//非空树{if((*T)->lchild)//有左孩子DestroyBiTree(&(*T)->lchild);//销毁左孩子子树if((*T)->rchild)//有右孩子DestroyBiTree(&(*T)->rchild);//销毁右孩子子树free(*T);//释放根结点*T=NULL;//空指针赋0}}#defineClearBiTreeDestroyBiTree//按先序次序输入二叉树中结点的值（可为字符型或整型，在主程中定义），//构造仅缺双亲指针的三叉链表表示的二叉树T。变量Nil表示空（子）树voidC

4、reate(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=(QueuePtr)malloc(

5、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(QNode));if(!p)//存储分配失败e

6、xit(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).front->next=p->next;if((*Q).rear==p)(*Q)

7、.rear=(*Q).front;free(p);return1;}//按先序次序输入二叉树中结点的值（可为字符型或整型，在主程中定义），//构造三叉链表表示的二叉树TintCreateBiTree(BiPTree*T){LinkQueueq;QElemTypea;Create(T);//构造二叉树(缺双亲指针)if(*T)//非空树{(*T)->parent=NULL;//根结点的双亲为＂空＂InitQueue(&q);//初始化