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

数据结构C语言版 二叉树的三叉链表存储表示.txt大悲无泪，大悟无言，大笑无声。我们手里的金钱是保持自由的一种工具。女人在约会前，一定先去美容院；男人约会前，一定先去银行。/*数据结构C语言版 二叉树的三叉链表存储表示编译环境：Dev-C+ 4.9.9.2日期：2011年2月13日 */#include #include typedef char TElemType;/ 二叉树的三叉链表存储表示typedef struct BiTPNodeTElemType data;struct BiTPNode *parent,*lchild,*rchild; / 双亲、左右孩子指针 BiTPNode,*BiPTree;typedef BiPTree 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(BiPTree *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) / 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);/动态分配一个空间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);/生成一个以为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);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) / 有左孩子 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-lchild)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中指向元素值为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); / 入队右孩子 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) / 非空树 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的右孩子的值 return 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;if(T) / 非空树 a=Point(T,e); / a是结点e的指针 / T中存在结点e且e存在右兄弟if(a&a!=T&a-parent-rchild&a-parent-rchild!=a) return a-parent-rchild-data; / 返回e的右兄弟的值 return Nil; / 其余情况返回空 / 根据LR为0或1,插入c为T中p所指结点的左或右子树。p所指结点 / 的原有左或右子树则成为c的右子树。 int InsertChild(BiPTree p,int LR,BiPTree c)if(p) / p不空 if(LR=0)c-rchild=p-lchild;if(c-rchild) / c有右孩子(p原有左孩子) c-rchild-parent=c;p-lchild=c;c-parent=p;else / LR=1 c-rchild=p-rchild;if(c-rchild) / c有右孩子(p原有右孩子) c-rchild-parent=c;p-rchild=c;c-parent=p;return 1;return 0; / p空 / 根据LR为0或1,删除T中p所指结点的左或右子树int DeleteChild(BiPTree p,int LR) if(p) / p不空 if(LR=0) / 删除左子树 ClearBiTree(&p-lchild);else / 删除右子树 ClearBiTree(&p-rchild);return 1;return 0; / p空 / 先序递归遍历二叉树T void PreOrderTraverse(BiPTree T,int(*Visit)(BiPTree) if(T)Visit(T); / 先访问根结点 PreOrderTraverse(T-lchild,Visit); / 再先序遍历左子树 PreOrderTraverse(T-rchild,Visit); / 最后先序遍历右子树 / 中序递归遍历二叉树Tvoid InOrderTraverse(BiPTree T,int(*Visit)(BiPTree) if(T)InOrderTraverse(T-lchild,Visit); / 中序遍历左子树 Visit(T); / 再访问根结点 InOrderTraverse(T-rchild,Visit); / 最后中序遍历右子树 / 后序递归遍历二叉树T void PostOrderTraverse(BiPTree T,int(*Visit)(BiPTree)if(T)PostOrderTraverse(T-lchild,Visit); / 后序遍历左子树 PostOrderTraverse(T-rchild,Visit); / 后序遍历右子树 Visit(T); / 最后访问根结点 / 层序遍历二叉树T(利用队列)void LevelOrderTraverse(BiPTree T,int(*Visit)(BiPTree) LinkQueue q;QElemType a;if(T)InitQueue(&q);EnQueue(&q,T);while(!QueueEmpty(q)DeQueue(&q,&a);Visit(a);if(a-lchild!=NULL)EnQueue(&q,a-lchild);if(a-rchild!=NULL)EnQueue(&q,a-rchild);int visitT(BiPTree T)if(T) / T非空 printf(%c是,T-data);if(T-parent) / T有双亲 printf(%c,T-parent-data);if(T-parent-lchild=T)printf(的左孩子n);elseprintf(的右孩子n);elseprintf(根结点n);return 1;int main()int i;BiPTree T,c,q;TElemType e1,e2;InitBiTree(&T);printf(构造空二叉树后,树空否？%d(1:是 0:否) 树的深度=%dn,BiTreeEmpty(T),BiTreeDepth(T);e1=Root(T);if(e1!=Nil)printf(二叉树的根为: %cn,e1);elseprintf(树空，无根n);printf(请按先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)n);CreateBiTree(&T);printf(建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%dn,BiTreeEmpty(T),BiTreeDepth(T);e1=Root(T);if(e1!=Nil)printf(二叉树的根为: %cn,e1);elseprintf(树空，无根n);printf(中序递归遍历二叉树:n);InOrderTraverse(T,visitT);printf(后序递归遍历二叉树:n);PostOrderTraverse(T,visitT); printf(层序遍历二叉树:n);LevelOrderTraverse(T,visitT);printf(请输入一个结点的值: );scanf(%*c); scanf(%c%*c,&e1);c=Point(T,e1); / c为e1的指针 printf(结点的值为%cn,Value(c);printf(欲改变此结点的值，请输入新值: );scanf(%c%*c,&e2);Assign(c,e2);printf(层序遍历二叉树:n);LevelOrderTraverse(T,visitT);e1=Parent(T,e2);if(e1!=Nil)printf(%c的双亲是%cn,e2,e1);elseprintf(%c没有双亲n,e2);e1=LeftChild(T,e2);if(e1!=Nil)printf(%c的左孩子是%cn,e2,e1);elseprintf(%c没有左孩子n,e2);e1=RightChild(T,e2);if(e1!=Nil)printf(%c的右孩子是%cn,e2,e1);elseprintf(%c没有右孩子n,e2);e1=LeftSibling(T,e2);if(e1!=Nil)printf(%c的左兄弟是%cn,e2,e1);elseprintf(%c没有左兄弟n,e2);e1=RightSibling(T,e2);if(e1!=Nil)printf(%c的右兄弟是%cn,e2,e1);elseprintf(%c没有右兄弟n,e2);InitBiTree(&c);printf(构造一个右子树为空的二叉树c:n);printf(请先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)n);CreateBiTree(&c);printf(先序递归遍历二叉树c:n);PreOrderTraverse(c,visitT);printf(树c插到树T中,请输入树T中树c的双亲结点 c为左(0)或右(1)子树: );scanf(%*c%c