五章树和二叉树.pptVIP

带权路径长度 ( Weighted Path Length, WPL ) 树的带权路径长度是树的各叶结点所带的权值 与该结点到根的路径长度的乘积的和。 * 第五章 树和二叉树 二叉树在一般情况下无法直接找到某结点在 某种遍历序列中的前驱和后继结点。若增加指针 域来存放前驱和后继结点信息，将大大降低存储 空间的利用率（密度）。考察 n 个结点的二叉树， 其中有 n+1 个空指针域，它们可以被用来存放“线 索”加了线索的二叉树称为线索二叉树。 一、线索二叉树 线索二叉树结点的描述 typedef int datatype; typedef struct node { int ltag,rtag; datatype data; struct node *lchild,*rchild; } bithptr; bithptr *pre; lchild ltag rtag data rchild 标志位如果为0，表示指针指向孩子结点，为1表示指针为线索 0 A 0 0 B 0 0 E 1 1 C 1 1 D 1 1 F 0 0 G 0 1 H 1 1 I 1 NULL NULL t 中序线索化算法 INTHREAD(bithptr *p,bithptr *pre) // p为当前结点，pre为p的前驱结点，开始调用时p为根结点指针，pre为NULL { if (p!=NULL) { INTHREAD(p-lchild,pre); // 左子树线索化 // 若当前结点的左子树为空，则建立指向其前驱结点的前驱线索 if (p-lchild = = NULL) { p-ltag＝1; p-lchild＝pre; } else p-ltag＝0; // 若前驱结点不为空，且其右孩子为空，则建立该前驱结点指向当前结点的后续线索 if (pre!=NULL pre-rchild = = NULL) { pre-rtag＝1; pre-rchild＝p; } else p-rtag＝0; pre＝p; // 中序向前遍历一个结点 INTHREAD(p-rchild, pre); } } 1、若 *p 的右子树为空，则 p-rchild 为右线 索，直接指向 *p 的中序后继结点。 2、若 *p 的右子树非空，则 *p 的中序后继必是 其右子树中第一个遍历到的结点，也就是从 *p的右孩子开始，沿左指针链往下查找，直 到找到一个没有左孩子的结点为止。 中序线索二叉树中，查找指定结点*p的中序后继结点 p R1 R2 Rk 最左下结点 中序线索二叉树中求中序后继结点的算法 bithptr *INORDERNEXT(bithptr *p) { bithptr *q; if (p-rtag==1) return(p-rchild); else { q＝p-rchild; while (q-ltag==0) q＝q-lchild; return(q); } } 1、若 *p 的左子树为空，则 p-lchild 为左线 索，直接指向 *p 的中序前驱结点。 2、若 *p 的左子树非空，则从 *p 的左孩子出发 ，沿右指针链往下查找，直到找到一个没有右 孩子的结点为止。 中序线索二叉树中，查找指定结点*p的中序前驱结点 p R1 R2 Rk 最右下结点 线索二叉树的遍历算法 TRAVERSEINTHREAD(bithptr *p) { if (p!=NULL) { while (p-ltag==0) p＝p-lchild; do { printf(“\t%d\n”,p-data); p＝INORDERNEXT(p); } while(p!=NULL); } } 线索二叉树的结点插入算法 INSERTRIGHT(bithptr *p,bithptr *q) { bithptr *s; s＝INORDERNEXT(p); q-ltag＝1; q-lchild＝p; q-rtag＝p-rtag; q-rchild＝p-rchild; p-rtag＝0; p-rchild＝q; if ((s!=NULL)(s-ltag==1)) s-lchild＝q; } 二叉排序树又称为二叉查找树，其定义为： 二叉排序树或者是一棵空树，或者是具有如下性质的二叉树： 1、若它的左子树非空，则左子树