【数据结构与算法】树3.ppt

《【数据结构与算法】树3.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6．4树和森林6.4.1树的存储结构一、双亲表示法（顺序存储）//-----------树的双亲表存储表示----------//#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intparent;//双亲位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//结点数}PTree;双亲表示法举例RADEFCBGKHR-1A0B0C0D1E1F3G6H6K60123456789数组下标:*便于涉及双亲的操作；*求结点的孩子时需要遍历整棵树。6.4.1树的存储结构

2、二、孩子表示法（顺序存储）#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intchild1;//第1个孩子位置域intchild2;//第2个孩子位置域......intchildd;//第d个孩子位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//结点数}PTree;孩子表示法举例RADEFCBGKH0123456789数组下标:*便于涉及孩子的操作；求双亲不方便；*采用同构的结点，空间浪费。R1A4B0C6D0E0F7G0H0K0235000000

3、00089000000孩子链表存储表示（链式存储）typedefstructCTNode{//孩子结点intchild;structCTNode*next;}*ChildPtr;typedefstruct{TElemTypedata;ChildPtrfirstchild;//孩子链表头指针}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//结点数和根的位置}CTree;孩子链表存储表示举例RADEFCBGKH0123456789数组下标:*便于涉及孩子的操作；*求结点的双亲时不方便。RAB/CD/E/FG/H/K/123/45

4、/6/789/T.nodes[];T.n=10;T.r=0;例1:设树T以孩子链表为存储结构,寻找值为x的双亲结点的算法如下:Statusparent(CtreeT,TElemTypex){//当值为x的结点不存在时返回-2;//当值为x的结点为根结点时返回-1,//否则返回x结点的双亲结点的下标值.if(T.nodes[T.r].data==x)return–1;//值为x的结点为根结点;for(i=0;ichild].data!=x)p=p->next;if(p)retur

5、n(i);//找到x的双亲结点}return–2;//值为x的结点不存在}例2:删除值为x的结点的第i棵子树的算法delete如下：voiddeletej(Ctree&T,intj){//删除树T的第j号结点及其子树if(!T.nodes[j].firstchild){//删除叶结点for(i=j;i

6、child){T.nodes[j].firstchild=s->next;i=s->child;free(s);deletej(T,i);//递归删除第i号结点及其子树}}}Statusdelete(Ctree&T,TElemTypex,inti){//当值为x的结点不存在时返回-2;当值为x的结点为//叶结点或无第i棵子树时返回-1,否则返回1.for(k=0;k=T.n)return–2;//值为x的结点不存在p=T.nodes[k].firstchild;j=1;if(!p)r

7、eturn–1;//x结点为叶结点if(i==1){//删除长子时,特殊处理j=p->child;//记住要删除子树的下标T.nodes[k].firstchild=p->next;free(p);}else{while(p->next&&jnext;j++;}if(j>i-1

8、

9、!p->next)return–1;//无第i棵子树//p指向第i-1个儿子j=p->next->child;//记住要删除子树的下标s=p->