数据结构讲义10col tree计算机系

族谱、社会 构B B

GX JKL§6.1一、树的递归定义：(有序)树是由一个或(2)除根以外的集合(T—{root})中的其余结点可被划分为m个不相交的子集T1，T2，…，Tm，其中每个子集都是树，并且其相应的根结点k1，k2，…，km是root的子结可如下排序：Ti排在Tj之前，当且仅当i<j树是一个二元组关系T=(K,N)，其中K是包含n个结点的有穷集合(n≥0)，且在K上定(1k0∈K，(2)除根结点k0外，其余结点都有且只有一个(3)对任意结点k∈K，都能找到从根k0到k的一条路径k0，k1，…，ks，使得0就是树根，无向树是n个结点，n-1 B

E G JKbc便于计算机扫描处理，把“”化为(d1

父结点、子结点、兄弟结点：<，k’>∈N，则称k是k’的父结点，而k’是k的子结点。若<k，k’>∈N<k，k”>∈N，k和k互为兄叶结点：没有非 分支结点：至少有一个非空边：两个结点的有序对，称为连路径、路径长度：若有x=x0祖先结点、子孙结点：若有一条由k到达k‘的路径，则称k是k’的祖先，k‘是k结点M的深度(层数)：从根结点到结点M的路径的长度。根结点层数为0，其它结点的层数等于其父结点的层数加1树的高度：等于最深的结点的深度+1森林(树林)：零棵或多棵树的有 §6.21 凡是兄弟就用线连起来，当作二 去掉父结点到子结点的连线，只。A GX JKLA G JKA F LG2C F LGC F GI E GX JKL§6.3classGTNode{ELEM //ELEMvalue(); //Returnnode'svalueboolisLeaf();//TRUEifnodeisaleafGTNode*parent();//Returnnode'sparentGTNode*leftmost_child();//Retfirst_childGTNode*right_sibling();//Retright_sibvoidsetValue(ELEM);//Setnode'svaluevoidinsert_first(GTNode*n);//asl_sonvoidinsert_next(GTNode*n);//asr_sibvoidremove_first();//Removefirstchildvoidremove_next();//Remover_sibclassGenTree{GTNode*rt; // //void //Allnodes GTNode*root(); //Returntherootofthetreevoidnewroot(ELEM,GTNode*,GTNode*);§6.4周游：系统地 E G JK1 没有对应于二叉树的后序周游的森林周首先依次层数为0后依次层数为1的结点，…，直到完最下一层结点。深度次序voidprint(GTNode*rt)if(rt->isLeaf())cout<<"Leaf:";elsecout<<"Internal:";//Printortakeotheractioncout<<rt->value()<<"\n";GTNode*temp=rt-while(temp!={print(temp);temp=>right_sibling();} C GX JKL

GI 2 3每个内部结点均其子结点按一定顺序形成的一个表(静态)。图的方法这是图的 问题?：怎么建立 内容，怎rlinkltag0,没有子结点为下标012345678rlinkCltag

534-16-1-19-EJKLFGDX01111101(有子结点为0,rlink-ltag表示法中ltag 有rlink指向，其序列前驱的ltag必 保持一定的冗余可以简化算法，并既然ltag冗余，考虑简化rlink的下 012345678rtag0000101101CEJKLFGDXI 101(有子结点为0,每个 扫描到一个ltag为1的结点就从栈，并使它的右指针指向当前llink-rtag,llink是静态指针rtag有子结点为0,1,257CDEF257CDEFGXIJKL0100101001typedefstruct{BELEMinfo;intltag, }voidlevel_create(BinNode*&rt,levelNode*tree,intn){BinNode*p, QueuepnewBinNode;rtpfor(inti=0;i<n-1;i++)p->element=tree[i].info;if(tree[i].ltag==0)elsep->right=

p1=new if(tree[i].rtag==0)p->right=p1;elsep-