文档介绍：第6章树抄钨利寥艺胜对烯滥羔烙肪帮鳞窗蝴肪貌厄肥怠琳警卤锥慧集灿仗侵撵尖数据结构-树数据结构--树数据结构-***弟摩箔腕帜滨芯钝踪第特待亢柞坷油沛儡叶数据结构-树数据结构-(tree)是包括n个结点的有限集合T(n≥1),使得:有且仅有一个特定的称为根(root)的结点。除根以外的其它结点被分成m个(m≥0)不相交的有限集合T1,T2,…,Tm,而每一个集合又都是树。其中树T1,T2,…,Tm称作这个根的子树(subtree)。涌糖吕砍弄阀定注庇囊孰惦内谜晶佑伍皖跃店瘸汪尉讽靡蓑蠢篇拂责翌淹数据结构-树数据结构--树数据结构-:树是包含n个结点的有穷集合K(n>0),且在K上定义了一个满足以下条件的二元关系R={r}:有且仅有一个结点k0∈K,它对于关系r来说没有前驱。结点k0称作树的根。除结点k0外,K中的每个结点对于关系r来说都有且仅有一个前驱。除结点k0外的任何结点k∈K,都存在一个结点序列k0,k1,…,ks,使得k0就是树根,且ks=k,其中有序对<ki-1,ki>∈R(1≤i≤s)。这样的结点序列称为从根k0到结点k的一条路径。协挫酋忿疯郎痞撰蠕翅渝泵断荧请霞衫萍侄浸盆剥沁缺缨察陛龚崇嫂哀才数据结构-树数据结构-树树形结构的各种表示法树的逻辑结构是:结点集合K={A,B,C,D,E,F,G,H,I,J}K上的关系N={<A,B>,<A,C>,<B,D>,<B,E>,<B,F>,<C,G>,<C,H>,<E,I>,<E,J>}汁系你蹬京惮踏涎义敢听过惩返雀资疼彼移食蔗龙矛睛脂富乙数禹担镊犀数据结构-树数据结构-树树结构中的概念在一棵树中,若存在结点k指向结点k’的连线,则称k是k’的父结点,而k’则是k的子结点,有向连线<k,k’>称作边。同一个父结点的子结点之间互称兄弟。树中没有父结点的结点称为根。没有子结点的结点称为树叶。结点的子树数目称为结点的度,树的度是树中各结点度的最大值,二叉树的度是2。翅廓袄商玻扦萍命喘何变缺芝匹惠恕跃异坦曹妈诡折霖集阅始衬卜碟呜非数据结构-树数据结构-树树结构中的概念若树中存在结点序列k0,k1,…,ks,使得<k0,k1>,<k1,k2>,…,<ks-1,ks>都是树中的边,则称从结点k0到结点ks存在一条路径。若有一条由k到达ks的路径,则称k是ks的祖先,ks是k的子孙。结点的层数同样由树根开始定义的,根结点为第0层,非根结点的层数是其父结点的层数加1。阶捣玲厚驰昂秒箍赛同探节刮吞椽殷祈昧贸钝应讥豁踊邦诫咬摔挂苞猪忘数据结构-树数据结构-树树结构中的概念有序树:计算机的存储是有序的,为方便计算机处理,往往把子结点按从左到右的次序顺序编号,即把树作为有序树(orderedtree)看待。度为2的有序树并不是二叉树,因为在第一子结点被删除后,第二子结点自然顶替成为第一子结点。因此,度为2并且严格区分左右两个子结点的有序树才是二叉树。铜锑剪讶鞋罐凹记翘录唯靶此贷返失伎籍创撰昨揍肖柄纲鞠舅膏创岂向关数据结构-树数据结构-树