资源预览内容
第1页 / 共78页
第2页 / 共78页
第3页 / 共78页
第4页 / 共78页
第5页 / 共78页
第6页 / 共78页
第7页 / 共78页
第8页 / 共78页
第9页 / 共78页
第10页 / 共78页
亲,该文档总共78页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第五章 树树是一类重要的非线性数据结构,是以分支关 系定义的层次结构 5.1 树的定义定义 v定义:树(tree)是n(n0)个结点的有限集T,其中: l有且仅有一个特定的结点,称为树的根(root) l当n1时,其余结点可分为m(m0)个互不相交的有限集 T1,T2,Tm,其中每一个集合本身又是一棵树,称为根的 子树(subtree) v特点: l树中至少有一个结点根 l树中各子树是互不相交的集合A只有根结点的树ABCDEFGHIJKLM有子树的树根子树基本术语 v结点(node)表示树中的元素,包括数据项及若干 指向其子树的分支 v结点的度(degree)结点拥有的子树数 v叶子(leaf)度为0的结点 v孩子(child)结点子树的根称为该结点的孩子 v双亲(parents)孩子结点的上层结点叫该结点的 v兄弟(sibling)同一双亲的孩子 v树的度一棵树中最大的结点度数 v结点的层次(level)从根结点算起,根为第一层, 它的孩子为第二层 v深度(depth)树中结点的最大层次数 v森林(forest)m(m0)棵互不相交的树的集合ABCDEFGHIJKLM结点A的度:3 结点B的度:2 结点M的度:0叶子:K,L,F,G,M,I,J结点A的孩子:B,C,D 结点B的孩子:E,F结点I的双亲:D 结点L的双亲:E结点B,C,D为兄弟 结点K,L为兄弟树的度:3结点A的层次:1 结点M的层次:4树的深度:4结点F,G为堂兄弟 结点A是结点F,G的祖先 5.2 二叉树定义 v定义:二叉树是n(n0)个结点的有限集,它或为空树 (n=0),或由一个根结点和两棵分别称为左子树和右子 树的互不相交的二叉树构成 v特点 l每个结点至多有二棵子树(即不存在度大于2的结点) l二叉树的子树有左、右之分,且其次序不能任意颠倒 v基本形态A只有根结点 的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树 均非空二叉树性质 v性质1:证明:用归纳法证明之i=1时,只有一个根结点, 是对的 假设对所有j(1j1,则其 双亲是i/2(2) 如果2in,则结点i无左孩子;如果2in,则其左孩子是2i(3) 如果2i+1n,则结点i无右孩子;如果2i+1n,则其右孩子 是2i+1 5.3 树的存储结构树的存储结构 v双亲表示法 l实现:定义结构数组存放树的结点,每个结点含两个域: u数据域:存放结点本身信息 u双亲域:指示本结点的双亲结点在数组中位置 l特点:找双亲容易,找孩子难typedef struct node datatype data;int parent; JD;JD tM;abcdefhgiacdefghib012235551096012345789dataparent0号单元不用或 存结点个数如何找孩子结点v孩子表示法 l多重链表:每个结点有多个指针域,分别指向其子树的根 u结点同构:结点的指针个数相等,为树的度D u结点不同构:结点指针个数不等,为该结点的度ddata child1 child2 . childDdata degree child1 child2 . childdl孩子链表:每个结点的孩子结点用单链表存储,再用含n个 元素的结构数组指向每个孩子链表孩子结点:typedef struct node int child; /该结点在表头数组中下标struct node *next; /指向下一孩子结点JD; 表头结点:typedef struct tnode datatype data; /数据域struct node *fc; /指向第一个孩子结点TD;TD tM; /t0不用abcdefhgi6012345789acdefghibdatafc2 34 59 7 86如何找双亲结点l带双亲的孩子链表612345789acdefghibdatafc2 34 59 7 86012235551parentabcdefhgiv孩子兄弟表示法(二叉树表示法) l实现:用二叉链表作树的存储结构,链表中每个结点的两个 指针域分别指向其第一个孩子结点和下一个兄弟结点 l特点 u操作容易 u破坏了树的层次typedef struct node datatype data;struct node *fch, *nsib; JD;abcdefhgia b c d e f g h i二叉树的存储结构 v顺序存储结构 l实现:按满二叉树的结点层次编号,依次存放二叉树中的数 据元素 l特点: u结点间关系蕴含在其存储位置中 u浪费空间,适于存满二叉树和完全二叉树abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11v链式存储结构 l二叉链表typedef struct node datatype data;struct node *lchild, *rchild; JD;lchild data rchild ABCDEFG在n个结点的二叉链表中,有n+1个空指针域ABC DE FGl三叉链表typedef struct node datatype data;struct node *lchild, *rchild, *parent; JD;lchild data parent rchildABCDEFGAB C DE FG树与二叉树转换ACBED树ABCDE二叉树A BC D E A B C D E A BC D E 对应存储存储解释解释v将树转换成二叉树 l加线:在兄弟之间加一连线 l抹线:对每个结点,除了其左孩子外,去除其与其余孩子之 间的关系 l旋转:以树的根结点为轴心,将整树顺时针转45ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空v将二叉树转换成树 l加线:若p结点是双亲结点的左孩子,则将p的右孩子,右孩 子的右孩子,沿分支找到的所有右孩子,都与p的双亲 用线连起来 l抹线:抹掉原二叉树中双亲与右孩子之间的连线 l调整:将结点按层次排列,形成树结构 ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIv森林转换成二叉树 l将各棵树分别转换成二叉树 l将每棵树的根结点用线相连 l以第一棵树根结点为二叉树的根,再以根结点为轴心,顺时 针旋转,构成二叉树型结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJv二叉树转换成森林 l抹线:将二叉树中根结点与其右孩子连线,及沿右分支搜索 到的所有右孩子间连线全部抹掉,使之变成孤立的二叉树 l还原:将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ 5.4 树和二叉树的遍历树的遍历 v遍历按一定规律走遍树的各个顶点,且使每一顶点 仅被访问一次,即找一个完整而有规律的走法,以得到 树中所有结点的一个线性排列 v常用方法 l先根(序)遍历:先访问树的根结点,然后依次先根遍历根的 每棵子树 l后根(序)遍历:先依次后根遍历每棵子树,然后访问根结点 l按层次遍历:先访问第一层上的结点,然后依次遍历第二层, 第n层的结点ABCDEFGHIJKLMNO先序遍历:后序遍历:层次遍历:ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNO二叉树的遍历 v方法 l先序遍历:先访问根结点,然后分别先序遍历左子树、右子树 l中序遍历:先中序遍历左子树,然后访问根结点,最后中序 遍历右子树 l后序遍历:先后序遍历左、右子树,然后访问根结点 l按层次遍历:从上到下、从左到右访问各结点DLRLDR、LRD、DLR RDL、RLD、DRLADBCD L RA D L RD L RBDCD L R先序遍历序列:A B D C先序遍历:ADBCL D RBL D RL D RADCL D R中序遍历序列:B D A C中序遍历:ADBCL R DL R DL R DADCL R D后序遍历序列: D B C A后序遍历:B-+/a*b-efcd先序遍历:中序遍历:后序遍历:层次遍历:- + a * b - c d / e f-+a*b-cd/ef- +a *b - c d/e f-+a*b-c d/e fv算法 l递归算法Ch5_1.cvoid preorder(JD *bt) if(bt!=NULL) printf(“%dt“,bt-data);preorder(bt-lchild);preorder(bt-rchild); 主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B); pre(T L);BTAprintf(A); pre(T L);ATDprintf(D); pre(T L);DTCprintf(C); pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列:A B D Cl非递归算法ABCDEFGpi P-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问:C(4)pABCDEFGi P-A访问:C B(5)ABCDEFGiP-AP-D访问:C Bp(6)ABCDEFGiP-AP-DP-E访问:C Bp(7)ABCDEFGiP-AP-D访问:C B E p(8)ABCDEFGiP-AP-DP-G访问:C B E P=NULL(9)ABCDEFGi P-A访问:C B E G Dp(11)ABCDEFGiP-AP-F访问:C B E G Dp(12)ABCDEFGiP-AP-D访问:C B E G p(10)ABCDEFGi P-A访问:C B E G D Fp=NULL (13)ABCDEFGi访问:C B E G D F Ap(14)ABCDEFGi访问:C B E G D F Ap=NULL(15)Ch5_4.c Ch5_40.C后序遍历非递归算法v遍历算法应用 l按先序遍历序列建立二叉树的二叉链表,已知先序序
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号