数据结构(C语言版)树、二叉树详细举例介绍.pptVIP

三.如何建立线索链表？在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。voidInThreading(BiThrTreep){if(p){//对以p为根的非空二叉树进行线索化InThreading(p-lchild);//左子树线索化if(!p-lchild)//建前驱线索{p-LTag=Thread;p-lchild=pre;}if(!pre-rchild)//建后继线索{pre-RTag=Thread;pre-rchild=p;}pre=p;//保持pre指向p的前驱InThreading(p-rchild);//右子树线索化}//if}单击此处添加大标题内容……StatusInOrderThreading(BiThrTreeThrt,BiThrTreeT){//构建中序线索链表if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;Thrt-rchild=Thrt;//添加头结点returnOK;}//InOrderThreadingif(!T)Thrt-lchild=Thrt;else{Thrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;//处理最后一个结点pre-RTag=Thread;Thrt-rchild=pre;}6.6树和森林的

表示方法单击此处添加小标题双亲表示法单击此处添加小标题孩子链表表示法单击此处添加小标题树的二叉链表(孩子-兄弟）存储表示法单击此处添加小标题树的三种存储结构ABCDEFG0A-11B02C03D04E25F26G5r=0n=7dataparent一.双亲表示法C语言的类型描述:#defineMAX_TREE_SIZE100dataparent结点结构:typedefstructPTNode{Elemdata;intparent;//双亲位置域}PTNode;intDepth(BiTreeT){//返回二叉树的深度if(!T)depthval=0;else{depthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);}returndepthval;}3.复制二叉树（参见习题6.46）其基本操作为:生成一个结点。添加标题左子树添加标题右子树添加标题(后序遍历)添加标题根元素添加标题T添加标题左子树添加标题右子树添加标题根元素添加标题NEWT添加标题左子树添加标题右子树添加标题BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr){if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(1);T-data=item;T-lchild=lptr;T-rchild=rptr;returnT;}生成二叉树的一个结点(其数据域为item,左指针域为lptr,右指针域为rptr)单击此处添加大标题内容若用先序框架，应如何修改？BiTNode*CopyTree(BiTNode*T)