第六章树与森林2.ppt

数据结构第六章树与森§、概述1、问题提出◆遍历是二叉树最基本的运算,为避免再次遍历的麻烦,可将首次遍历得到的信息存于一个线性结构中。◆具有n个结点的链式存贮的二叉树中,有n+1个链域是空的,能否充分利用这些空的链域来存放结点的前趋指针和后继指针呢?2、实现策略◆结点中增加两个标记域◆两标记域取值范围是0,1。各只占一个二进制位,只增加很少的额外空间开销。rightChildleftChildleftThreaddatarightThread指向左孩子0指向前驱1指向右孩子0指向后继13、线索二叉树◆指向前驱和指向后继的指针叫做线索(Thread)。◆具有线索的二叉树叫做线索二叉树。◆因遍历的次序有三种,所以线索二叉树也分前、中、后序这三种。◆中序遍历线索二叉树结构示例◆若根的左子树不空,则其最左下角的结点为中序遍历的第一个结点,否则根为中序遍历的第一个结点。◆若根的右子树不空,侧其最右下角的结点为中序遍历的最后一个结点,否则根为中序遍历的最后一个结点。0E00B01F00D11G11C11A1ULLNULL0E00B01F00D11G11C11A1root01Rt中序线索二叉树及其存储结构二、中序线索二叉树的类定义1、类型定义typedefenum{Link,Thread}PointerTag;TypedefstructBiThNode{TElemTypedata;structBiThNode*lchild,*rchild;PointerTagLtag,Rtag;}BiThrNode,*BiThTree;中序遍历二叉线索树T的非递归算法:voidInOrderTraverse_Thr(BiThTreeT){p=T->lchild;while(p!=T){while(p->Ltag==Link)p=p->lchild;printf(p->data);while(p->Rtag==Thread&&p->rchild!=T){p=p->rchild;printf(p->data);}P=p->rchild;}}?StatusInOrderThreading(BiThTree&Thrt,BiThrTreeT){if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);Thrt->Ltag=Link;Thrt->Rtag=Thread;Thrt->rchild=Thrt;if(!T){Thrt->lchild=Thrt;else{Thrt->lchild=T;Pre=Thrt;InThreading(T);Pre->rchild=Thrt;Pre->Rtag=Thread;Thrt->rchild=pre;}ReturnOK;}01thrt若为空树01thrt若为非空树0E0TPre始终指向刚刚访问的结点VoidInThreading(BiThTreep){if(p){InThreading(p->lchild);if(!p->lchild){p->Ltag=Thread;p->lchild=pre;}if(!pre->rchild){pre->Rtag=Thread;pre->rchild=p;}Pre=p;InThreading(p->rchild);}}0E00B01F00D11G11C11A1root01中序线索二叉树及其存储结构preT§、双亲表示法#defineMAX_TREE_SIZE100TypedefstructPTNode{TElemTypedata;intparent;}PTNode;Typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;}Ptree;