数据结构（19）：二叉树的三叉链表表示

程序代码//二叉树的三叉链表存储#includestdio.h#includestdlib.h#definemax(a, b) a b ? a : b#defineClearBiTree DestroyBiTreetypedefcharTElemType;// 二叉树的三叉链表存储表示typedefstructBiTPNode{TElemType data;structBiTPNode*parent,*lchild,*rchild;// 双亲、左右孩子指针}BiTPNode,*BiPTree;typedefBiPTree QElemType;// 设队列元素为二叉树的指针类型typedefstructQNode{QElemType data;//数据域structQNode*next;//指针域}QNode,*QueuePtr;typedefstruct{QueuePtr front,//队头指针指针域指向队头元素rear;//队尾指针指向队尾元素}LinkQueue;TElemType Nil#;// 字符型以空格符为空// 构造空二叉树TintInitBiTree(BiPTree*T){*TNULL;return1;}// 销毁二叉树TvoidDestroyBiTree(BiPTree*T){if(*T)// 非空树{if((*T)-lchild)// 有左孩子DestroyBiTree((*T)-lchild);// 销毁左孩子子树if((*T)-rchild)// 有右孩子DestroyBiTree((*T)-rchild);// 销毁右孩子子树free(*T);// 释放根结点*TNULL;// 空指针赋0}}// 按先序次序输入二叉树中结点的值可为字符型或整型在主程中定义// 构造仅缺双亲指针的三叉链表表示的二叉树T。变量Nil表示空子树voidCreate(BiPTree*T)// CreateBiTree()调用{TElemType ch;scanf(%c,ch);if(chNil)// 空*TNULL;else{*T(BiPTree)malloc(sizeof(BiTPNode));if(!*T)exit(0);(*T)-datach;// 生成根结点Create((*T)-lchild);// 构造左子树Create((*T)-rchild);// 构造右子树}}// 构造一个空队列QintInitQueue(LinkQueue*Q){(*Q).front(*Q).rear(QueuePtr)malloc(sizeof(QNode));//动态分配一个空间if(!(*Q).front)exit(0);(*Q).front-nextNULL;//队头指针指向空无数据域这样构成了一个空队列return1;}// 若Q为空队列,则返回1,否则返回0intQueueEmpty(LinkQueue Q){if(Q.frontQ.rear)return1;elsereturn0;}// 插入元素e为Q的新的队尾元素intEnQueue(LinkQueue*Q,QElemType e){QueuePtr p(QueuePtr)malloc(sizeof(QNode));if(!p)// 存储分配失败exit(0);//生成一个以为e为数据域的队列元素p-datae;p-nextNULL;//将该新队列元素接在队尾的后面(*Q).rear-nextp;(*Q).rearp;return1;}// 若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0intDeQueue(LinkQueue*Q,QElemType*e){QueuePtr p;if((*Q).front(*Q).rear)return0;p(*Q).front-next;//队头元素*ep-data;(*Q).front-nextp-next;if((*Q).rearp)(*Q).rear(*Q).front;free(p);return1;}// 按先序次序输入二叉树中结点的值可为字符型或整型在主程中定义// 构造三叉链表表示的二叉树TintCreateBiTree(BiPTree*T){LinkQueue q;QElemType a;Create(T);// 构造二叉树(缺双亲指针)if(*T)// 非空树{(*T)-parentNULL;// 根结点的双亲为空InitQueue(q);// 初始化队列EnQueue(q,*T);// 根指针入队while(!QueueEmpty(q))// 队不空{DeQueue(q,a);// 出队,队列元素赋给aif(a-lchild)// 有左孩子{a-lchild-parenta;// 给左孩子的双亲指针赋值EnQueue(q,a-lchild);// 左孩子入队}if(a-rchild)// 有右孩子{a-rchild-parenta;// 给右孩子的双亲指针赋值EnQueue(q,a-rchild);// 右孩子入队}}}return1;}// 若T为空二叉树,则返回1,否则0intBiTreeEmpty(BiPTree T){if(T)return0;elsereturn1;}// 返回T的深度intBiTreeDepth(BiPTree T){inti,j;if(!T)return0;if(T-lchild)iBiTreeDepth(T-lchild);elsei0;if(T-rchild)jBiTreeDepth(T-rchild);elsej0;returnij?i1:j1;}// 返回T的根TElemTypeRoot(BiPTree T){if(T)returnT-data;elsereturnNil;}// 返回p所指结点的值TElemTypeValue(BiPTree p){returnp-data;}// 给p所指结点赋值为valuevoidAssign(BiPTree p,TElemType value){p-datavalue;}// 返回二叉树T中指向元素值为e的结点的指针BiPTreePoint(BiPTree T,TElemType e){LinkQueue q;QElemType a;if(T)// 非空树{InitQueue(q);// 初始化队列EnQueue(q,T);// 根结点入队while(!QueueEmpty(q))// 队不空{DeQueue(q,a);// 出队,队列元素赋给aif(a-datae)returna;if(a-lchild)// 有左孩子EnQueue(q,a-lchild);// 入队左孩子if(a-rchild)// 有右孩子EnQueue(q,a-rchild);// 入队右孩子}}returnNULL;}// 若e是T的非根结点,则返回它的双亲,否则返回空TElemTypeParent(BiPTree T,TElemType e){BiPTree a;if(T)// 非空树{aPoint(T,e);// a是结点e的指针if(aa!T)// T中存在结点e且e是非根结点returna-parent-data;// 返回e的双亲的值}returnNil;// 其余情况返回空}// 返回e的左孩子。若e无左孩子,则返回空TElemTypeLeftChild(BiPTree T,TElemType e){BiPTree a;if(T)// 非空树{aPoint(T,e);// a是结点e的指针if(aa-lchild)// T中存在结点e且e存在左孩子returna-lchild-data;// 返回e的左孩子的值}returnNil;// 其余情况返回空}// 返回e的右孩子。若e无右孩子,则返回空TElemTypeRightChild(BiPTree T,TElemType e){BiPTree a;if(T)// 非空树{aPoint(T,e);// a是结点e的指针if(aa-rchild)// T中存在结点e且e存在右孩子returna-rchild-data;// 返回e的右孩子的值}returnNil;// 其余情况返回空}// 返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回空TElemTypeLeftSibling(BiPTree T,TElemType e){BiPTree a;if(T)// 非空树{aPoint(T,e);// a是结点e的指针// T中存在结点e且e存在左兄弟if(aa!Ta-parent-lchilda-parent-lchild!a)returna-parent-lchild-data;// 返回e的左兄弟的值}returnNil;// 其余情况返回空}// 返回e的右兄弟。若e是T的右孩子或无右兄弟,则返回空TElemTypeRightSibling(BiPTree T,TElemType e){BiPTree a;if(T)// 非空树{aPoint(T,e);// a是结点e的指针// T中存在结点e且e存在右兄弟if(aa!Ta-parent-rchilda-parent-rchild!a)returna-parent-rchild-data;// 返回e的右兄弟的值}returnNil;// 其余情况返回空}// 根据LR为0或1,插入c为T中p所指结点的左或右子树。p所指结点// 的原有左或右子树则成为c的右子树。intInsertChild(BiPTree p,intLR,BiPTree c){if(p)// p不空{if(LR0){c-rchildp-lchild;if(c-rchild)// c有右孩子(p原有左孩子)c-rchild-parentc;p-lchildc;c-parentp;}else// LR1{c-rchildp-rchild;if(c-rchild)// c有右孩子(p原有右孩子)c-rchild-parentc;p-rchildc;c-parentp;}return1;}return0;// p空}// 根据LR为0或1,删除T中p所指结点的左或右子树intDeleteChild(BiPTree p,intLR){if(p)// p不空{if(LR0)// 删除左子树ClearBiTree(p-lchild);else// 删除右子树ClearBiTree(p-rchild);return1;}return0;// p空}// 先序递归遍历二叉树TvoidPreOrderTraverse(BiPTree T,int(*Visit)(BiPTree)){if(T){Visit(T);// 先访问根结点PreOrderTraverse(T-lchild,Visit);// 再先序遍历左子树PreOrderTraverse(T-rchild,Visit);// 最后先序遍历右子树}}// 中序递归遍历二叉树TvoidInOrderTraverse(BiPTree T,int(*Visit)(BiPTree)){if(T){InOrderTraverse(T-lchild,Visit);// 中序遍历左子树Visit(T);// 再访问根结点InOrderTraverse(T-rchild,Visit);// 最后中序遍历右子树}}// 后序递归遍历二叉树TvoidPostOrderTraverse(BiPTree T,int(*Visit)(BiPTree)){if(T){PostOrderTraverse(T-lchild,Visit);// 后序遍历左子树PostOrderTraverse(T-rchild,Visit);// 后序遍历右子树Visit(T);// 最后访问根结点}}// 层序遍历二叉树T(利用队列)voidLevelOrderTraverse(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);}}}intvisitT(BiPTree T){if(T)// T非空printf(%c是,T-data);if(T-parent)// T有双亲{printf(%c,T-parent-data);if(T-parent-lchildT)printf(的左孩子\n);elseprintf(的右孩子\n);}elseprintf(根结点\n);return1;}intmain(){inti;BiPTree T,c,q;TElemType e1,e2;InitBiTree(T);printf(构造空二叉树空否%d(1:是 0:否) 树的深度 %d\n,BiTreeEmpty(T),BiTreeDepth(T));e1Root(T);if(e1!Nil)printf(二叉树的根为: %c\n,e1);elseprintf(树空无根\n);printf(请按先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)\n);CreateBiTree(T);printf(建立二叉树后,树空否%d(1:是 0:否) 树的深度%d\n,BiTreeEmpty(T),BiTreeDepth(T));e1Root(T);if(e1!Nil)printf(二叉树的根为: %c\n,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);cPoint(T,e1);// c为e1的指针printf(结点的值为%c\n,Value(c));printf(欲改变此结点的值请输入新值: );scanf(%c%*c,e2);Assign(c,e2);printf(层序遍历二叉树:\n);LevelOrderTraverse(T,visitT);e1Parent(T,e2);if(e1!Nil)printf(%c的双亲是%c\n,e2,e1);elseprintf(%c没有双亲\n,e2);e1LeftChild(T,e2);if(e1!Nil)printf(%c的左孩子是%c\n,e2,e1);elseprintf(%c没有左孩子\n,e2);e1RightChild(T,e2);if(e1!Nil)printf(%c的右孩子是%c\n,e2,e1);elseprintf(%c没有右孩子\n,e2);e1LeftSibling(T,e2);if(e1!Nil)printf(%c的左兄弟是%c\n,e2,e1);elseprintf(%c没有左兄弟\n,e2);e1RightSibling(T,e2);if(e1!Nil)printf(%c的右兄弟是%c\n,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%d,e1,i);qPoint(T,e1);InsertChild(q,i,c);printf(先序递归遍历二叉树:\n);PreOrderTraverse(T,visitT);printf(删除子树,请输入待删除子树的双亲结点 左(0)或右(1)子树: );scanf(%*c%c%d,e1,i);qPoint(T,e1);DeleteChild(q,i);printf(先序递归遍历二叉树:\n);PreOrderTraverse(T,visitT);DestroyBiTree(T);system(pause);return0;}运行结果