第7章树形结构4.pptVIP

第七章 树和二叉树;7.7 线索二叉树;A; ;7.7.2 线索化二叉树 为了实现线索化二叉树,将前面二叉树结点的类型定义修改如下： typedef struct node { ElemType data; /*结点数据域*/ int ltag,rtag; /*增加的线索标记*/ struct node *lchild; /*左孩子或线索指针*/ struct node *rchild; /*右孩子或线索指针*/ } TBTNode; /*线索树结点类型定义*/ ;typedef struct node { ElemType data; int ltag,rtag; //增加的线索标记 struct node *lchild; struct node *rchild; } TBTNode; TBTNode * CreateTBTNode(char *str) //建立二叉树（二叉链表的方式） TBTNode * CreaThread(TBTNode *b) //中序线索化二叉树;算法设计;TBTNode *CreaThread(TBTNode *b) /*中序线索化二叉树*/ { TBTNode *root; root=(TBTNode *)malloc(sizeof(TBTNode)); /*创建头结点*/ root-ltag=0;root-rtag=1; root-lchild=b; { pre=root; Thread(b); pre-lchild=root; pre-rtag=1; root-rchild=pre; } return root; } ; Thread(p)算法思路是： *p 指向当前访问的结点 *pre指向前一访问的结点 采用中序遍历的方式 Thread (b-lchild); printf(%c ,b-data); Thread (b-rchild); ;TBTNode *pre; /*全局变量*/ void Thread(TBTNode *p) /*对二叉树b进行中序线索化*/ { if (p!=NULL) { Thread(p-lchild); /*左子树线索化*/ if (p-lchild==NULL) /*前驱线索*/ { p-lchild=pre; p-ltag=1;} /*建立当前结点的前驱线索*/ else p-ltag=0; if (pre-rchild==NULL) /*后继线索*/ { pre-rchild=p;pre-rtag=1;}/*建立前驱结点的后继线索*/ else pre-rtag=0; pre=p; Thread(p-rchild); /*递归调用右子树线索化*/ } } ;7.8 哈夫曼树与哈夫曼编码 ;树的带权路径长度WPL：设树中有M个叶结点，每个叶结点带一个权值WK，树根到每一个叶结点K的路径长度为LK则WPL =。;哈夫曼树：WPL最小的树称为最优二叉树，又称哈夫曼树;哈夫曼树的构造过程;哈夫曼算法（构造哈夫曼树）;哈夫曼树的构造过程;;哈夫曼编码;对应的哈夫曼编码如下： 1：000 3：001 5：01 7：1;哈夫曼???码举例;例题;7.9 树和森林;树的双亲表示法;双亲孩子表示法;孩子兄弟表示法;孩子兄弟表示法举例;7.9.1 树与二叉树的转换;树与二叉树的转换方式一;树与二叉树的转换方式二;例题;7.9.3 森林与二叉树的转换;A;（2）二叉树转换成森林的方法 (1)将根结点和其左子树作为森林的一棵树，并将其右子树作为森林的其他子树。 （2）重复上面的直到某结点的右子树为空。