数据结构第六章 树的查找和应用.pptVIP

第六章:树的查找和树的应用 第一节 查找树 查找树的定义 查找树T是一棵二叉树T，它或是空,或满足下面三个条件： 1.如果树T的根结点的左子树非空，那么左子树中的所有结点的键值都小于T的根结点的键值： 2.如果树T的根结点的右子树非空，那么右子树中的所有结点的键值都大于T的根结点的键值。 3.树T的根结点的左、右子树也都是查找树。 也可以根据中序遍历来定义查找树： 对于一棵给定的二叉树T，如果树T中的结点的中序是排好序的，那么称树T是一棵查找树。 #include stdio.h struct node {char date; struct node *lchild,*rchild; }; typedef struct node NODE; NODE *t , *p, *q; Char a; 查找树t中找出给定键值a的算法： (1)若t为空，那么查找失败，算法结束，否则转（２） (2)若t-data等于a，那么查找成功,算法结束,否则转(3) (3)若t-data小于a, 那么t-lchild=t ;否则t-rchild=t转（１） void search(t,a,p_p,p_q) NODE *t,**p_p,**P_q; char a; { *p_p=NULL; *p_q=t; while(*p_q!=NULL) { if ((*p_q)-data==a) return; *P_P=*p_q; if (a(*p_q)-data) *p_q=(*p_q)-Ichild; else *p_q=(*p_q)-rchild; } } 例：变量t指向树Ｔ的根结点， a是所要查找的键值，q指向被查找的结点，p指向被查找结点的父结点.可用如下的语句调用:search(t,a,p,q) n个结点的查找树Ｔ中找出结点k（k在树中，每次均是成功查找），所需的比较次数是结点k的树枝长度λk加1。 MAX(二叉查找法)=max(1+λk) 树T中的k AVG(二叉查找法)=P(k)是结点k的相对使用频率。 设: p(k)= 则AVG(二叉查找法)= int insert(p_t,a) NODE **p_t; char a; { NODE *p, *q, *r; search(*p_t,a,p,q); if (q!=NULL) return(l); r=(NODE *)malloc(sizeof(NODE)); r-data=a; r-Ichild=NULL; r-rchild=NULL; if (p==NULL) *p_t=r; else if (p-dataa) p-Ichild=r; else p-rchild=r; return(0); } 结点的删除 删除的算法 (1)首先调用serach(),从而确定被删除结点在树中的位置。 (2)若被删结点不在树中，则算法结束。 (3)若被删结点在树中，则进行下面的删除。 (I)若被删结点是根结点 (a)若被删结点无左子结点，则用被删结点的右子树作为删除后的树 (b) 若被删结点有左子结点，则用左子结点作为根，右子树作为被删结点的左子树在中序最后一个结点的右子树 (II)被删结点不是根结点 (a)若被删结点无左子结点，则 1若被删结点是它的父结点的左子结点，那么被删结点的右子树作为被删结点的父结点的左子树。 2如果被删结点是它的父结点的右子结点，那么被删结点的右子树作为被删结点的右子树。 (b)若被结点有左子结点，则把被删结点的右子树作为被删结点左子树按中序最后一个结点的右子树，同时进行。 1如果被删结点是它的父结点的左子结点，那么把被删结点的左子树作为被删结点的父结点的左子树。 2如果被删结点是它的父结点的右子结点，那么被删结点的左子树作为被删结点父结点的右子树。 (III)回收被删结点的存贮单元 int delete(p_t,a) NODE **p_t; char a; { NODE *p, *q, *r; search(*p_t,a,p,q); if (q==NULL) return(1); if (p==NULL) if (q-lchild==NULL) *p_t=q-rchild; else (r=q-lchild; while (r-rchild!=NULL) r=r-rchild; r-rchild=q-rchild; *p_t=q-Ichild; } else if (q-Ichild==NULL) if (q==p-lchild) p-Ichild=q-rchild; else p-rchild=q-rchild; else {r=q-Ichild; while (r-rchild!=NULL) r=r-rch