资源预览内容
第1页 / 共74页
第2页 / 共74页
第3页 / 共74页
第4页 / 共74页
第5页 / 共74页
第6页 / 共74页
第7页 / 共74页
第8页 / 共74页
第9页 / 共74页
第10页 / 共74页
亲,该文档总共74页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第五章 树与二叉树 树是一类重要的非线性数据结构,是以分支关 系定义的层次结构 5.1 树的定义 定义 v定义:树(tree)是n(n0)个结点的有限集T,其中: l有且仅有一个特定的结点,称为树的根(root) l当n1时,其余结点可分为m(m0)个互不相交的有限集 T1,T2,Tm,其中每一个集合本身又是一棵树,称为根的 子树(subtree) v特点: l树中至少有一个结点根 l树中各子树是互不相交的集合 A 只有根结点的树 A BCD EFGHIJ KLM 有子树的树根 子树 基本术语 v结点(node)表示树中的元素,包括数据项及若干 指向其子树的分支 v结点的度(degree)结点拥有的子树数 v叶子(leaf)度为0的结点 v孩子(child)结点子树的根称为该结点的孩子 v双亲(parents)孩子结点的上层结点叫该结点的 v兄弟(sibling)同一双亲的孩子 v树的度一棵树中最大的结点度数 v结点的层次(level)从根结点算起,根为第一层, 它的孩子为第二层 v深度(depth)树中结点的最大层次数 v森林(forest)m(m0)棵互不相交的树的集合 A BCD EFGHIJ KLM 结点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 只有根结点 的二叉树 空二叉树 A B 右子树为空 A B 左子树为空 A BC 左、右子树 均非空 二叉树性质 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实现:按满二叉树的结点层次编号,依次存放二叉树中的数 据元素 l特点: u结点间关系蕴含在其存储位置中 u浪费空间,适于存满二叉树和完全二叉树 a bc de fg a b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11 v链式存储结构 l二叉链表 typedef struct node datatype data; struct node *lchild, *rchild; Bnode,*Btree; lchild data rchild A B CD EF G 在n个结点的二叉链表中,有n+1个空指针域 A B C D E F G typedef struct node datatype data; struct node *lchild, *rchild, *parent; JD; lchild data parent rchild A B CD EF G A B C D E F G 三叉链表 二叉链表的生成 方法: 1 输入根结点; 2 若左子树不空,输入左子树; 3 若右子树不空,输入右子树 Btree createbtree(Btree bt,int k) datatype b; Btree t; Bnode *p; printf(“Please input node b: ”); scanf (“%d” , if (b!=0) p=(Bnode*)malloc(sizeof(Bnode);p-data=b; p-lchild=NULL;p-rchild=NULL; switch(k) case 0: t=p;break; case 1: bt-lchild=p;break; case2: bt-rchild=p;break; createbtree(p,1);createtree(p,2); return(t); 5.4 树和二叉树的遍历 树的遍历 v遍历按一定规律走遍树的各个顶点,且使每一顶点 仅被访问一次,即找一个完整而有规律的走法,以得到 树中所有结点的一个线性排列 v常用方法 l先根(序)遍历:先访问树的根结点,然后依次先根遍历根的 每棵子树 l后根(序)遍历:先依次后根遍历每棵子树,然后访问根结点 l按层次遍历:先访问第一层上的结点,然后依次遍历第二层, 第n层的结点 A BCD EFGH I JKLM NO 先序遍历: 后序遍历: 层次遍历: ABE F I GCDHJ KL NOM E I F G B C J K N O L M H D A AB C DE F GH I J KL MNO 二叉树的遍历 v方法 l先序遍历:先访问根结点,然后分别先序遍历左子树、右子树 l中序遍历:先中序遍历左子树,然后访问根结点,最后中序 遍历右子树 l后序遍历:先后序遍历左、右子树,然后访问根结点 l按层次遍历:从上到下、从左到右访问各结点 D LR LDR、LRD、DLR RDL、RLD、DRL A D B C D L R A D L R D L R B D C D L R 先序遍历序列:A B D C 先序遍历: A D B C L D R B L D R L D R A D C L D R 中序遍历序列:B D A C 中序遍历: A D B C L R D L R D L R D A D C L R D 后序遍历序列: D B C A 后序遍历: B - + / a* b- ef cd 先序遍历: 中序遍历: 后序遍历: 层次遍历: - + a * b - c d / e f -+a*b-cd/ef - +a *b - c d/e f -+a*b-c d/e f v算法 l递归算法 void preorder(JD *bt) if(bt!=NULL) printf(%dt,bt-data); preorder(bt-lchild); preorder(bt-rchild); void inorder(JD *bt) if(bt!=NULL) inorder(bt-lchild); printf(%dt,bt-data); inorder(bt-rchild); void postorder(JD *bt) if(bt!=NULL) postorder(bt-lchild); postorder(bt-rchild); printf(%dt,bt-data); void preorder(JD *bt) if(bt!=NULL) printf(%dt,bt-data); preorder(bt-lchild); preorder(bt-rchild); 主程序 Pre( T ) 返回 返回 pre(T R); 返回 返回 pre(T R); A CB D T B printf(B); pre(T L); B T A printf(A); pre(T L); A T D printf(D); pre(T L); D T C printf(C); pre(T L); C 返回 T 左是空返回 pre(T R); T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R); 先序序列:A B D C l非递归算法 A B CD EF G p i P-A (1) A B CD EF G p i P-A P-B (2) A B CD EF G pi P-A P-B P-C (3) p=NULL A B CD EF G i P-A P-B 访问:C(4) p A B CD EF G i P-A 访问:C B (5) A B CD EF G i P-A P-D 访问:C B p (6) A B CD EF G i P-A P-D P-E 访问:C B p (7) A B CD EF G i P-A P-D 访问:C B E p (8) A B CD EF G i P-A P-D P-G 访问:C B E P=NULL (9) A B CD EF G i P-A 访问:C B E G D p (11) A B CD EF G i P-A P-F 访问:C B E G D p (12) A B CD EF G i P-A P-D 访问:C B E G p (10) A B CD EF G i P-A 访问:C B E G D F p=NULL (13) A B CD EF G i 访问:C B E G D F A p (14) A B CD EF G i 访问:C B E G D F A p=NULL (15) Ch5_4.c Ch5_40.C 后序遍历非递归算法 v定义: l前驱与后继:在二叉树的先序、中序或后序遍历序列中两个相邻 的结点互称为 l线索:指向前驱或后继结点的指针称为 l线索二叉树:加上线索的二叉链表表示的二叉树叫 l线索化:对二叉树按某种遍历次序使其变为线索二叉树的过程叫 v实现 l在有n个结点的二叉链表中必定有n+1个空链域 l在线索二叉树的结点中增加两个标志域 ult :若 lt =0, lc 域指向左孩子;若 lt=1, lc域指向其前驱 urt :若 rt =0, rc 域指向右孩子;若 rt=1, rc域指向其后继 l结点定义: typedef struct node int data; int lt, rt; struct node *lc, *rc; JD; lc lt data rt rc 5.5 线索二叉树 A B C D E A B D C E T 先序序列:ABCDE 先序线索二叉树 00 0011 11 11 A B C D E A B D C E T 中序序列:BCAED 中序线索二叉树 00 0011 11 11 A B C D E A B D C E T 后序序列:CBEDA 后序线索二叉树 00 0011 1111 A B C D E 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列:BCAED 带头结点的中序线索二叉树 0 1 头结点: lt=0, lc指向根结点 rt=1, rc
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号