《数据结构C语言版-二叉树的三叉链表存储表示》由会员分享，可在线阅读，更多相关《数据结构C语言版-二叉树的三叉链表存储表示（12页珍藏版）》请在金锄头文库上搜索。
1、数据结构C语言版 二叉树的三叉链表存储表示.txt大悲无泪，大悟无言，大笑无声。我们手里的金钱是保持自由的一种工具。女人在约会前，一定先去美容院；男人约会前，一定先去银行。/*数据结构C语言版 二叉树的三叉链表存储表示日期：2021年2月13日 */#include #include typedef char TElemType;/ 二叉树的三叉链表存储表示typedef struct BiTPNodeTElemType data;struct BiTPNode *parent,*lchild,*rchild; / 双亲、左右孩子指针 BiTPNode,*BiPTree;typedef BiP
2、Tree QElemType; / 设队列元素为二叉树的指针类型 typedef struct QNodeQElemType data;/数据域struct QNode *next;/指针域QNode,*QueuePtr;typedef structQueuePtr front,/队头指针，指针域指向队头元素 rear; /队尾指针，指向队尾元素LinkQueue;TElemType Nil= ; / 字符型以空格符为空 / 构造空二叉树T int InitBiTree(BiPTree *T) *T=NULL;return 1;/ 销毁二叉树T void DestroyBiTree(BiPTr
3、ee *T)if(*T) / 非空树 if(*T)-lchild) / 有左孩子 DestroyBiTree(&(*T)-lchild); / 销毁左孩子子树 if(*T)-rchild) / 有右孩子 DestroyBiTree(&(*T)-rchild); / 销毁右孩子子树 free(*T); / 释放根结点 *T=NULL; / 空指针赋0 #define ClearBiTree DestroyBiTree/ 按先序次序输入二叉树中结点的值可为字符型或整型，在主程中定义， / 构造仅缺双亲指针的三叉链表表示的二叉树T。变量Nil表示空子树 void Create(BiPTree *T)
4、 / CreateBiTree()调用 TElemType ch;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); / 构造右子树 / 构造一个空队列Qint InitQueue(LinkQueue *Q) (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode);/动态
5、分配一个空间if(!(*Q).front)exit(0);(*Q).front-next=NULL;/队头指针指向空，无数据域，这样构成了一个空队列return 1;/ 假设Q为空队列,那么返回1,否那么返回0 int QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)return 1;elsereturn 0;/ 插入元素e为Q的新的队尾元素int EnQueue(LinkQueue *Q,QElemType e) QueuePtr p=(QueuePtr)malloc(sizeof(QNode);if(!p) / 存储分配失败 exit(0);/生成一个以为
6、e为数据域的队列元素p-data=e;p-next=NULL;/将该新队列元素接在队尾的后面(*Q).rear-next=p;(*Q).rear=p;return 1;/ 假设队列不空,删除Q的队头元素,用e返回其值,并返回1,否那么返回0 int DeQueue(LinkQueue *Q,QElemType *e)QueuePtr p;if(*Q).front=(*Q).rear)return 0;p=(*Q).front-next;/队头元素*e=p-data;(*Q).front-next=p-next;if(*Q).rear=p)(*Q).rear=(*Q).front;free(p)
7、;return 1;/ 按先序次序输入二叉树中结点的值可为字符型或整型，在主程中定义， / 构造三叉链表表示的二叉树T int CreateBiTree(BiPTree *T)LinkQueue q;QElemType a;Create(T); / 构造二叉树(缺双亲指针) if(*T) / 非空树 (*T)-parent=NULL; / 根结点的双亲为空 InitQueue(&q); / 初始化队列 EnQueue(&q,*T); / 根指针入队 while(!QueueEmpty(q) / 队不空 DeQueue(&q,&a); / 出队,队列元素赋给a if(a-lchild) / 有左
8、孩子 a-lchild-parent=a; / 给左孩子的双亲指针赋值 EnQueue(&q,a-lchild); / 左孩子入队 if(a-rchild) / 有右孩子 a-rchild-parent=a; / 给右孩子的双亲指针赋值 EnQueue(&q,a-rchild); / 右孩子入队 return 1;/ 假设T为空二叉树,那么返回1,否那么0 int BiTreeEmpty(BiPTree T) if(T)return 0;elsereturn 1;/ 返回T的深度 int BiTreeDepth(BiPTree T)int i,j;if(!T)return 0;if(T-lch
9、ild)i=BiTreeDepth(T-lchild);elsei=0;if(T-rchild)j=BiTreeDepth(T-rchild);elsej=0;return ij ? i+1 : j+1;/ 返回T的根 TElemType Root(BiPTree T) if(T)return T-data;elsereturn Nil;/ 返回p所指结点的值 TElemType Value(BiPTree p)return p-data;/ 给p所指结点赋值为valuevoid Assign(BiPTree p,TElemType value) p-data=value;/ 返回二叉树T中指
10、向元素值为e的结点的指针BiPTree Point(BiPTree T,TElemType e) LinkQueue q;QElemType a;if(T) / 非空树 InitQueue(&q); / 初始化队列 EnQueue(&q,T); / 根结点入队 while(!QueueEmpty(q) / 队不空 DeQueue(&q,&a); / 出队,队列元素赋给a if(a-data=e)return a;if(a-lchild) / 有左孩子 EnQueue(&q,a-lchild); / 入队左孩子 if(a-rchild) / 有右孩子 EnQueue(&q,a-rchild);
11、/ 入队右孩子 return NULL;/ 假设e是T的非根结点,那么返回它的双亲,否那么返回空TElemType Parent(BiPTree T,TElemType e) BiPTree a;if(T) / 非空树 a=Point(T,e); / a是结点e的指针 if(a&a!=T) / T中存在结点e且e是非根结点 return a-parent-data; / 返回e的双亲的值 return Nil; / 其余情况返回空 / 返回e的左孩子。假设e无左孩子,那么返回空 TElemType LeftChild(BiPTree T,TElemType e)BiPTree a;if(T)
12、/ 非空树 a=Point(T,e); / a是结点e的指针 if(a&a-lchild) / T中存在结点e且e存在左孩子 return a-lchild-data; / 返回e的左孩子的值 return Nil; / 其余情况返回空 / 返回e的右孩子。假设e无右孩子,那么返回空TElemType RightChild(BiPTree T,TElemType e) BiPTree a;if(T) / 非空树 a=Point(T,e); / a是结点e的指针 if(a&a-rchild) / T中存在结点e且e存在右孩子 return a-rchild-data; / 返回e的右孩子的值 r
13、eturn Nil; / 其余情况返回空 / 返回e的左兄弟。假设e是T的左孩子或无左兄弟,那么返回空TElemType LeftSibling(BiPTree T,TElemType e) BiPTree a;if(T) / 非空树 a=Point(T,e); / a是结点e的指针 / T中存在结点e且e存在左兄弟if(a&a!=T&a-parent-lchild&a-parent-lchild!=a)return a-parent-lchild-data; / 返回e的左兄弟的值 return Nil; / 其余情况返回空 / 返回e的右兄弟。假设e是T的右孩子或无右兄弟,那么返回空TElemType RightSibling(BiPTree T,TElemType e) BiPTree a;
