数据结构4树与二叉树

《数据结构4树与二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树和二叉树线索二叉树（ThreadedBinary）-+/-a*cdefb一棵具有n个结点二叉树，用二叉链表表示时，树中存在空指针域的个数为：n+1利用空指针域指向结点的前驱或后继结点结构lchildrchildltagdatartag其中：ltag=0lchild指向结点的左孩子ltag=1lchild指向结点的前驱rtag=0rchild指向结点的右孩子rtag=1rchild指向结点的后继以这种结构构成的二叉链表叫线索链表，其中指向前驱和后继的指针称作线索，加上线索的二叉树成为线索二叉树。二叉树的二叉线索存储表示Typedefenum{Link,Thread}PointerTa

2、g;TypedefstructBiThrNode{TElemTypedata;structBiThrNode*lchild,*rchild;PointerTagLTag,RTag;}BiThrNode,*BiThrTree;-+/-a*cdefb01-00+00/00e11a11*00f11b11-00c11d11thrtbt例如：中序序列：a+b*c-d-e/fStatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TElemTypee)){P=T->lchild;while(p!=T){while(p->LTag==Link)p=p->l

3、child;if(!Visit(p->data))returnERROR;while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);}p=p->rchild;}returnOK}中序序列：a+b*c-d-e/f01-00+00/00e11a11*00f11b11-00c11d11thrtbt线索化二叉树01thrt空线索化二叉树StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){if(!(Thrt=(BiThrTree)malloc(sizeof(BithrNode))))

4、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}voidInThreading(BiThrTreep){if(p){InThreading(p->lchild);if(!p->lchild){p->LTag=Thread;p->lchild=pre;}

5、if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}pre=p;InThreading(p->rchild);}}01-00+00/00e11a11*00f11b11-00c11d11thrtbt例：求中序线索树中给定结点的后继结点BiThrTreeinordernext(BiThrTreep){if(p->RTag==Thread)return(p->rchild);else{q=p->rchild;while(q->LTag==Link)q=q->lchild;return(q);}}6.6赫夫曼(Huffman)树及其应用一、赫夫曼(Hu

6、ffman)树---最优树路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径路径长度：路径上的分支数树的路径长度：从树根到每一个结点的路径长度之和结点的带权路径长度：该结点到根的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。n记作：wpl=∑wklkk=1定义：给定一组权w1w2……wn,且w1≤w2≤……≤wn，设有一个二叉树，共有n片叶子，分别带权w1w2……wn，该二叉树称为带权二叉树。最优二叉树或Huffman树——设有n个权值w1w2……wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的那棵二叉树叫最优二叉树

7、或Huffman树.例有4个结点,权值分别为7,5,2,4,构造有4个叶子结点的二叉树abcd7524(1)WPL=7*2+5*2+2*2+4*2=36dcab2475(2)WPL=4*2+7*3+5*3+2*1=46abcd7524(3)WPL=7*1+5*2+2*3+4*3=35例：将百分制成绩转换成5级分制成绩if(a<60)b=“bad”;elseif(a<70)b=“pass”;elseif(a<80)b=“g