755第6章树和二叉树.ppt

,第6章 树和二叉树 树是一类重要的非线性数据结构，是以分支关系定义的层次结构6.1 树的定义定义：树(tree)是n(n0)个结点的有限集T其中：有且仅有一个特定的结点，称为树的根(root)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中至少有一个结点称为根树中各子树是互不相交的集合,担潦锦风金程褐醋自醛廓殉允源匿邦尤治曹洽蜘虾丫疮蜕肚粉盲贩碰座官755-第6章 树和二叉树755-第6章 树和二叉树,A,只有一个根结点的树,A为根结点，其余分为三个互不相交的子集T1=B,E,F,K,L T2=C,G T3=D,H,I,J,MT1,T2,T3都是根结点A的子树，且本身又是一棵树。,根,制篓剐箭德子疮欧淮忆沧粟钵难悍跟脆熊币英荣棘南谗园血戴夏田隘诅挑755-第6章 树和二叉树755-第6章 树和二叉树,基本术语结点(node)：包括一个数据元素及若干指向其子树的分支结点的度(degree)：结点拥有的子树个数叶子(leaf)：度为0的结点（或称终端结点）分支结点（非终端结点）：度不为0的结点树的度：树内各结点的度的最大值孩子(child)：结点的子树的根称为该结点的孩子双亲(parents):(相对孩子)结点的上层结点兄弟(sibling)：同一双亲的孩子之间互称兄弟结点的祖先：从根到该结点所经分支上的所有结点子孙：某结点为根的子树中的任意结点结点的层次(level)：从根结点算起，根为第一层，它的孩子为第二层深度(depth)：树中结点的最大层次数森林(forest)：m(m0)棵互不相交的树的集合,泻丘芹穆白淳街矩借漏期筛狰柬脆秉冶抡毯偏造磊谋腾淫堑女钡衫赃间豪755-第6章 树和二叉树755-第6章 树和二叉树,ADT Tree 数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则RH，H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若Droot，则存在Droot的一个划分 D1，D2，Dm（m0），对任意j k(1j,km)有Dj Dk=,且对任意的i(1im)，唯一存在数据元素Xi Di,有root,Xi H;(3)对应于D-root的划分,H-有唯一的一个划分H1,H2,Hm(m0),对任意jk(1j,km)有Hj Hk=,且对任意i(1im)，Hi是 Di上的二元关系，（Di,Hi）是一棵符合本定义的树，称为根root的子树。,暖怜搭姚嘎疯发午羔寨稠龄捣耘爵铣浓猜驮氓骋氨只败钳淋溪瑰体斌酝司755-第6章 树和二叉树755-第6章 树和二叉树,基本操作P：InitTree(ADT Tree,讫斧掌班肤仓泻勿负写掳朗牙省内蒂厌赛馋瞬甸留编陨植瘦饰遗崎痕廷吨755-第6章 树和二叉树755-第6章 树和二叉树,6.2 二叉树一、定义二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒基本形态,A,瓮同孰尉擒翅桃腊蓝崩窒绽讯兰骚莲闰嫡侦伪懒菠啦胜精敢组裙牌簧客艘755-第6章 树和二叉树755-第6章 树和二叉树,ADT BinaryTree数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D，则R，称BinaryTree为空二叉树；若D，则RH，H是如下二元关系；(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-root,则存在D-rootDl,Dr,且DlDr；(3)若Dl，则Dl中存在唯一的元素Xl,H，且存在Dl上的关系HlH；若Dr，则Dr中存在唯一的元素Xr，H,且存在Dr上的关系HrH；H,，Hl,Hr;(4)(Dl,Hl)是一棵符合本定义的二叉树,称为根的左子树(Dr,Hr)是一棵符合本定义的二叉树,称为根的右子树,伏柴筐冠埋再瘤蛰泼找姻挫贵庇睦嚣室焉错裳淤铂英汹螺尧暖驶夜纫锈船755-第6章 树和二叉树755-第6章 树和二叉树,基本操作P：InitBiTree(ADT BinaryTree,昌征残溺倘晒瑶远踩柴麻啃以球斧吮铭馋初披船猾钠榴侥缕煞始巧惨者炮755-第6章 树和二叉树755-第6章 树和二叉树,二、二叉树的性质,性质1：在二叉树的第i层上至多有2i-1个结点(i1),证明：用归纳法证明 i=1时,只有一个根结点,2i-1=20=1 是对的 假设对所有j(1ji)命题成立，即第j层上至多有 2j-1 个结点 那么，第i-1层至多有2i-2 个结点 又二叉树每个结点的度至多为2 第i层上最大结点数是第i-1层的2倍，即2x2i-2=2i-1 故命题得证,性质2：深度为k的二叉树至多有2k-1个结点(k1),证明：由性质1知深度为k 的二叉树最大结点数为 k k(第i层上的最大结点数)=2i-1=2k 1 i=1 i=1,吞熙政弹营屠没资翠娘杉殴婚嫁癣碧轻骏稍月菇挠目芯霖来点稚孕劝饰捡755-第6章 树和二叉树755-第6章 树和二叉树,性质3：对任何一棵二叉树T，如果其终端结点数为n0，度 为2的结点数为n2，则 n0=n2+1,证明：设n1为二叉树T中度为1的结点数 因为：二叉树中所有结点的度均小于或等于2 所以：其结点总数n=n0+n1+n2 又二叉树中，除根结点外，其余结点都只有一个 分支进入 设B为分支总数，则n=B+1 又：分支由度为1和度为2的结点射出，B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1,埠碗御言习抢微嘻症腹穷俭铁惮砧绥总露洽老悟例篡术屋高亥悍烛躇锈去755-第6章 树和二叉树755-第6章 树和二叉树,两种特殊形式的二叉树,满二叉树,定义：一棵深度为k且有2k-1个结点的二叉树称为满二叉树,特点：每一层上的结点数都是最大结点数,沮赵据汇六氓炉砧们绘淬非刨委汕劈鼠塑瞄哺糕牌套就扛打勋洲酪拌噎常755-第6章 树和二叉树755-第6章 树和二叉树,两种特殊形式的二叉树,完全二叉树,定义：深度为k，有n个结点的二叉树当且仅当其每一个结 点都与深度为k的满二叉树中编号从1至n的结点一一 对应时，称为完全二叉树,特点：叶子结点只可能在层次最大的两层上出现对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1,灭将乓岿清腻览惟欢窘脾铭蓝恒瘴甩好暮辉径汗灿乓雄除勺浇锰九叹亨矮755-第6章 树和二叉树755-第6章 树和二叉树,性质4：具有n个结点的完全二叉树的深度为log2n+1,证明：设深度为k，根据性质2和完全二叉树的定义有 2k-1-1 n 2k-1,或 2k-1 n 2k,于是 k-1 log2n k,因为 k是整数 所以 k=log2n+1,笔娄严墟赢布争荔垒鳃血望窑怎绚肿蝴锚茶腺鄂滩钩娜纂咱播基萄冯泅责755-第6章 树和二叉树755-第6章 树和二叉树,性质5：如果对一棵有n个结点的完全二叉树的结点按层序 编号，则对任一结点i(1in)，有：(1)如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是i/2(2)如果2in，则结点i无左孩子；如果2in，则其左孩子是2i(3)如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1,犹祝选络浊葫外痛蠕囤宋描慈筛应鲤落锤樟城肄掺园大浚砂靡掌侄匀敬吟755-第6章 树和二叉树755-第6章 树和二叉树,三、二叉树的存储结构,1、顺序存储结构 二叉树的顺序存储表示#define MAX_TREE_SIZE 100 typedef TElemType SqBiTree MAX_TREE_SIZE;SqBiTree bt;,吠饼陆修癣哮涝踢南浴盗拇嗽吭渠肮榜族队轴案韦毫疟醒华棒甜诛减院仇755-第6章 树和二叉树755-第6章 树和二叉树,顺序存储结构的特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树,把沼霹凝哦罪仆绽按挺迢韩动锌功捂恩辩馈锐敖脐宇何欲鱼泞氮喉颗当吞755-第6章 树和二叉树755-第6章 树和二叉树,2、链式存储结构,赂梯敛铡囚睬轿缚永梁顶腐削秘榷皖篇驾篡便濒摧咒侮圈碾挝记敝乙死柯755-第6章 树和二叉树755-第6章 树和二叉树,二叉树的二叉链表存储表示typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;,特点：指针直接表示关系，操作简单 增加指针域，浪费空间，特别是存在多个空指针域,桃习彩港锄掏楼嘘拉二担具导权陈舶吾藉箍砾擎耘窗酮洲佯南枢冬标熏佩755-第6章 树和二叉树755-第6章 树和二叉树,6.3 遍历二叉树和线索二叉树一、遍历二叉树 遍历二叉树(Traversing Binary Tree):按某条搜索路径巡访树的每个结点，且使每个顶点仅被访问一次，从而得到树中所有结点的一个线性排列。,由二叉树的递归定义可知：二叉树是由三个基本单元组成：根结点、左子树、右子树,则可得到六种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD,先序遍历(DLR)：先访问根结点,然后分别先序遍历左子树、右子树中序遍历(LDR)：先中序遍历左子树，然后访问根结点，最 后中序遍历右子树后序遍历(LRD)：先后序遍历左、右子树，然后访问根结点,档曳吨腹间够罩阀躲滓贴厂絮仍涡般描苗矣趣迅盲孩猛筷峻斤纱店凉粥渺755-第6章 树和二叉树755-第6章 树和二叉树,先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点（2）先序遍历左子树（3）先序遍历右子树,中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树,后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点,诱涕泰农偷榔袋披判此亩晒鞭偏慧此赴迷笼框寸醇彻撇僻估皑高运挺派歇755-第6章 树和二叉树755-第6章 树和二叉树,例：,先序序列：,A,B,D,F,E,G,C,中序序列：,D,B,F,G,E,A,C,后序序列：,D,F,G,B,E,C,A,贷氟摸恼垂借绰烽撑诺块镰疹绳箍洁症番迟俗凄哥吞普稽之幼塘磨斑疽茧755-第6章 树和二叉树755-第6章 树和二叉树,先序遍历二叉树的递归算法Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if（T）if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-rchild,Visit)return OK;return ERROR;else return OK;,Status PreOrderTraverse(BiTree T)if（T）Visit(T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);,脏歇鼎讼他抒柒牢酣毯境厦伙龋扦福饺薛侍慷惶馒浴项梢炕笑铃邮欣逻赞755-第6章 树和二叉树755-第6章 树和二叉树,中序遍历算法Status InOrderTraverse(BiTree T)if（T）InOrderTraverse(T-lchild);Visit(T-data);InOrderTraverse(T-rchild);,后序遍历算法Status PostOrderTraverse(BiTree T)if（T）PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);Visit(T-data);,洼井依鸯宋尊宛良碴喀渗讣转兜师乌旗坊奢志特抢苍抓孜秽火绊璃惰囤帝755-第6章 树和二叉树755-第6章 树和二叉树,遍历过程演示：,先序序列：-*a b c,叭芒葡汉设亭临样艰殷栏绝襄汇吝鞭檄蚁霜俭蚊配萧置奎促烬拈舱葛钢腰755-第6章 树和二叉树755-第6章 树和二叉树,遍历过程演示：,先序序列：-*a b c,中序序列：a*b-c,泰菇土撼漫触梯钓析妓潘巾瑟连犹什耪搬蛇嗓眺道宜睬谰辰古梁紊塑援件755-第6章 树和二叉树755-第6章 树和二叉树,遍历过程演示：,先序序列：-*a b c,中序序列：a*b-c,中序序列：a b*c-,进陌商邯汉哇件毡保讨久债存缘住抵犬谤挣矽猖秉暑珠眯求犁甥茁宾扭垂755-第6章 树和二叉树755-第6章 树和二叉树,中序遍历的非递归算法Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)InitStack(S);Push(S,T);while(!StackEmpty(S)while(GetTop(S,p),棠进拾汕学茎津股传府烯姐厦炎貌旦曼柔甫款因掖名谜彦师傀眼避导鸡蛰755-第6章 树和二叉树755-第6章 树和二叉树,中序遍历的非递归算法Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;else Pop(S,p);if(!Visit(p-data)return ERROR;p=p-rchild;return OK;,蛋鞍住巩宏哪禁眉袭臀拦恶磨衷因竣予盐须衔菏容构娶隅灯架洋隘束扁慌755-第6章 树和二叉树755-第6章 树和二叉树,按先序次序输入二叉树中结点的值（一个字符），空字符表示空树，构造二叉链表表示的二叉树TStatus CreateBiTree(BiTree,蘸锹河功膛瑚宫割蛹丸浓颂叠勺元捻沾坏楷冀秘健眺盔谰溃急瘩片垢愚帝755-第6章 树和二叉树755-第6章 树和二叉树,6.4 树与森林一、树的存储结构1、双亲表示法用结构数组存放树的结点，每个结点含两个域：数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组中位置 特点:找双亲容易，找孩子难,012345678,data parent,啃弥怠摸靖过裳雀柳诗威谈整罗雕林刀哄违郁寒拨礼瓜徘墨辈势戏杀棚椅755-第6章 树和二叉树755-第6章 树和二叉树,树的双亲表示#define MAX_TREE_SIZE 100typedef struct PTNode TElemType data;int parent;PTNode;typedef struct PTNode nodes MAX_TREE_SIZE;int n;PTree;,例：求结点ti的长子Int FirstChild(Ptree t,int i)for(j=i+1;j t.n;j+)if(t.nodesj.parent=i)return(j);return(-1);,羞讶呼媚标奄蛰舀忘翠究披岂沼冷救徽规绊馆袁哺渐庐恐猎坍迪刁亚助捉755-第6章 树和二叉树755-第6章 树和二叉树,2、孩子表示法多重链表：每个结点有多个指针域，分别指向其子树 的根结点同构：结点的指针个数相等，为树的度d,浪费空间,操作不便,廊寄阔谗屯戏够纫侩碉混汰羚拳诸它电痒桐秃囊懈紧桂嚎鞍挟壁滩辙螟嘱755-第6章 树和二叉树755-第6章 树和二叉树,孩子链表表示：,012345678,data firstchild,如何找双亲结点,项聪零辖斌界咨显拈榆幸二潭吩丢献契卵乡吭配跌屑群颗典簿垂诗系母爹755-第6章 树和二叉树755-第6章 树和二叉树,孩子链表表示：,012345678,data parent firstchild,姥抠陆轰剑湃鹅他辜闻歼嫡裕果谓咖妊撞烽癌酌撵窃泌薛抛踞嚏宽怂辰证755-第6章 树和二叉树755-第6章 树和二叉树,树的孩子链表存储表示typedef struct CTNode int child;struct CTNode*next;*ChildPtr;typedef struct TElemType data;Childptr firstchild;CTBox;typedef struct CTBox nodes MAX_TREE_SIZE;int n,r;/结点数和根的位置 CTree;,崇珐缀午究穿糠非洒惰枝鸥械亦直被撇薛匆猾绕惧涪仪张蓉撑祝锅昏扩铣755-第6章 树和二叉树755-第6章 树和二叉树,3、孩子兄弟表示法：-二叉链表表示法 用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点typedef struct CSNode ElemType data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;,豁拇阔哗去嫡天彪臼巫剖凡缝驯挂擞券疗幂绊骋芝股忌有傈酱瑞壤百猾雪755-第6章 树和二叉树755-第6章 树和二叉树,例：,商修行嗡秽丽道琢炮碘戊跳戏心吃斑廖冬皖锌哗烩混去牙蕴饭伙误抑四炬755-第6章 树和二叉树755-第6章 树和二叉树,二、森林与二叉树的转换 借助于二叉链表存储结构实现树与二叉树的转换,舒棉恶茹徐类拧升砷喷烧冒缚掘侄慎逃痹见引檀拭邑艰贵睁掩椽箍琉苗妥755-第6章 树和二叉树755-第6章 树和二叉树,加线：在兄弟之间加一连线删线：对每个结点，除了其长子孩子外，去除其与其余 孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针旋转,树转换成的二叉树其右子树一定为空,将树转换成二叉树,段铸知蔬栽鄙袁稼摆嫂诲唱龙肌模柠篓改煽鞋负盎凄番帮洋摧皇礼啤羞扼755-第6章 树和二叉树755-第6章 树和二叉树,从树与二叉树的转换可知：任何一棵和树对应的二叉树，其右子树必为空，若把森林中第二棵树的根结点看成是第一棵树根结点的兄弟，则可导出森林和二叉树的对应关系。,森林转换成二叉树如果F T1，T2，Tm是森林，则可按如下规则转换成一棵二叉树B（root,LB,RB）。（1）若F为空，即m0，则B为空树（2）若F非空，即m0，则B的根root即为森林中第一棵树的根ROOT（T1）；B的左子树LB是从T1中根结点的子树森林F1T11，T12，T1m1转换而成的二叉树；其右子树RB是从森林F=T2，T3，Tm转换而成的二叉树。,波诸曾邹幸英屉盆尾纵粉翼翔珠戊荚串瓜堂珐旬沧喂疼诫观送巳腐悲值浴755-第6章 树和二叉树755-第6章 树和二叉树,二叉树转换成森林如果B（root,LB,RB）是一棵二叉树，则可按如下规则转换成森林FT1，T2，Tm；（1）若B为空，则F为空；（2）若B非空，则F中第一棵树T1的根ROOT（T1）即为二叉树B的根root；T1中根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除T1之外其余树组成的森林F=T2，T3，Tm是由B的右子树RB转换而成的森林。,冻剧孵致兜亩榨依甥河赁吹找腺精等乎沼帜冤狈做鹊祁聊稍铺醒喘朽衬挨755-第6章 树和二叉树755-第6章 树和二叉树,将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构,森林转换成二叉树,咐宰皮才尊薛坪惨崩咙柒逸马涸饯窜抚可井布万呻邵淫葱窜嚣滦酶寸窝产755-第6章 树和二叉树755-第6章 树和二叉树,三、树和森林的遍历,1)先根遍历,2)后根遍历,未盐盂鄂划贯拨帮湛令韵液润斋本诺嗅鄙掀蓖降拒惕燎够猩捕焙秸遥甩饮755-第6章 树和二叉树755-第6章 树和二叉树,三、树和森林的遍历,先根（序）遍历 若T非空，则：1、访问根结点R 2、依次先序遍历根的各子树,先根序列：,A,B,D,G,E,H,I,C,F,畅芝淳竟卑某虱儒贮洱觅翼城令聘宗国有盒态懊呐折邀抹态涪磐汞帚釉穗755-第6章 树和二叉树755-第6章 树和二叉树,三、树和森林的遍历,后根（序）遍历 若T非空，则：1、依次后序遍历根的各子树 2、访问根结点R,先根序列：,A,B,D,G,E,H,I,C,F,后根序列：,D,G,H,E,I,B,F,C,A,夫咒韩绿氦赚澄宜仆嘉膨恋狼华毗固抒辅虱糖确冶比剧谎登勾咕伶硷衙蘸755-第6章 树和二叉树755-第6章 树和二叉树,先根序列：,A,B,D,G,E,H,I,C,F,后根序列：,D,G,H,E,I,B,F,C,A,先序序列：,A,B,D,G,E,H,I,C,F,中序序列：,D,G,H,E,I,B,F,C,A,后序序列：,I,H,G,D,E,F,C,B,A,涎屡宏仙熙揖肮俘庇孝扬杆卖束序歉钾恳铸滦豌衫靳急瓶屑坯聋弧阅叼若755-第6章 树和二叉树755-第6章 树和二叉树,按照森林和树的相互递归定义，可推出森林的两种遍历方法,1)先序遍历森林 若森林非空，则 访问森林中第一棵树的根结点 先序遍历第一棵树中根结点的子树森林 先序遍历除去第一棵树之后剩余的树构成的森林,先序序列,A,B,C,E,D,F,G,H,I,J,龋幽必庇稽勉刀岂劣溢莫地疏撤牛匣狡编缨哭购丢涂船座钱番滦蛹毯捻案755-第6章 树和二叉树755-第6章 树和二叉树,按照森林和树的相互递归定义，可推出森林的两种遍历方法,2)中序遍历森林 若森林非空，则 中序遍历森林中第一棵树的根结点的子树森林 访问第一棵树的根结点 中序遍历除去第一棵树之后剩余的树构成的森林,先序序列,A,B,C,E,D,F,G,H,I,J,中序序列,B,C,D,F,A,E,H,J,I,G,价叭愚哎簿画肤匆峭鞠布伺肚果博眶宠般蒸祸肩狗杉掀悠修矛校折禾捆作755-第6章 树和二叉树755-第6章 树和二叉树,先序序列,A,B,C,E,D,F,G,H,I,J,中序序列,B,C,D,F,A,E,H,J,I,G,先序序列,A,B,C,E,D,F,G,H,I,J,中序序列,B,C,D,F,A,E,H,J,I,G,后序序列,D,C,B,J,F,I,H,G,E,A,张比仪轻诽房蔡万深策讳傈正暇娠酶喂桓好盼蝎垄障痔移奄拙说拽敏然擦755-第6章 树和二叉树755-第6章 树和二叉树,