数据结构树和二叉树ppt课件.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《数据结构树和二叉树ppt课件.ppt》由会员分享,可在线阅读,更多相关《数据结构树和二叉树ppt课件.ppt(53页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程第6章 树和二叉树 树是一类重要的非线性数据结构,是以分支关系定义的层次结构。6.1 树的定义和基本术语定义v定义:树(tree)是n(n0)个结点的有限集T,n=0时为空树,n0时:l有且仅有一个特定的结点,称为树的根(root)l其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中每一个集合本身又是一棵树,称为根的子树(subtree),T1,T2,Tm又称为森林。v特点:l非空树中至少有一个结点根,只有根的树称为最小树l树中各子树是互不相交的集合病原体侵入机体,消弱机
2、体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程A只有根结点的树ABCDEFGHIJKLM有子树的树根子树病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程抽象数据类型树的定义:P118119基本术语v结点(node)表示树中的元素,包括数据项及若干指向其子树的分支v结点的度(degree)结点拥有的子树数v叶子(leaf)度为0的结点v孩子(child)结点子树的根称为该结点的孩子v双亲(parents)孩子结点的上层结点叫该结点的双亲病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定
3、性,且在一定部位生长繁殖,引起不同程度的病理生理过程v堂兄弟双亲在同一层的结点互为堂兄弟v兄弟(sibling)同一双亲的孩子v树的度一棵树中最大的结点度数v结点的层次(level)从根结点算起,根为第一层,它的孩子为第二层v深度(depth)树中结点的最大层次数v森林(forest)m(m0)棵互不相交的树的集合v有序树各子树是从左到右依次有序且不能交换的树,否则为无序树。病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程ABCDEFGHIJKLM结点A的度:3结点B的度:2结点M的度:0叶子:K,L,F,G,M,I,J结点A的孩子
4、: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的祖先病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程6.2 二叉树定义v定义:二叉树是n(n0)个结点的有限集,它或为空树(n=0),或由一个根结点和两棵分别称为左子树和右子树的互不相交的树构成v特点l每个结点至多有二棵子树(即不存在度大于2的结点)l二叉树的子树有左、右之分,且其次序不能任意颠倒l结构简单,存储效率高,运算简单v基本形态A只有
5、根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程二叉树性质v性质性质1:证明:用归纳法证明之证明:用归纳法证明之 i=1时,只有一个根结点,时,只有一个根结点,是对的是对的 假设对所有假设对所有 i=k命题成立命题成立 ,即第即第k层上至多有层上至多有 个结点个结点 又二叉树每个结点的度至多为又二叉树每个结点的度至多为2 第第k+1层上最大结点数是第层上最大结点数是第k层的层的2倍,即倍,即 故命题得证。故命题得证。因此,第一层为因此,第一层为20 第二层为第二
6、层为21 第二层为第二层为22 第四层为第四层为23病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程v性质性质2:深度为:深度为k的二叉树至多有的二叉树至多有 个结点个结点(k 1)证明:由性质证明:由性质1,可得深度为,可得深度为k 的二叉树最大结点数是的二叉树最大结点数是如深度为如深度为4 4的二叉树:的二叉树:病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程v性质性质3:对任何一棵二叉树:对任何一棵二叉树T,如果其终端结点数为如果其终端结点数为n0,度为度为2的结点
7、数为的结点数为n2,则则n0=n2+1证明:设证明:设n1为二叉树为二叉树T中度为中度为1的结点数的结点数 二叉树中所有结点的度均小于或等于二叉树中所有结点的度均小于或等于2 终端终端(度为度为0)结点数为结点数为n0,度为,度为2的结点数为的结点数为n2其结点总数其结点总数n=n0+n1+n2 又二叉树中,除根结点外,其余结点都只有一个指针与其双亲相又二叉树中,除根结点外,其余结点都只有一个指针与其双亲相 连。连。设指针数为设指针数为b,则,则n=b+1 (根结点无分支进入,需加入总数中根结点无分支进入,需加入总数中)又又分支由度为分支由度为1和度为和度为2的结点射出,的结点射出,b=n1+
8、2n2 于是,于是,n=b+1=n1+2n2+1 n1+2n2+1=n0+n1+n2 n0=n2+1病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程两种特殊形式的二叉树v满二叉树l定义:l特点:每一层上的结点数都是最大结点数v完全二叉树l定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中从左到右编号按1至n的结点一一对应时,称为完全二叉树。l特点u叶子结点只可能在最底两层上出现u对任一结点,若其右分支下子孙的最大层次为L,则其左分支下子孙的最大层次必为L 或L+1病原体侵入机体,消弱机体防御机能,破坏机体
9、内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程1231145891213671014151231145891267101234567123456病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程v性质性质4:具有:具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 证明:假设深度为k,则根据性质2和完全二叉树的 定义有 或 于是 k是整数 完全二叉树中:深度为k的最少结点数 病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程v性质性质5:如果对一
10、棵有:如果对一棵有n个结点的完全二叉树的结点按层序编号,个结点的完全二叉树的结点按层序编号,则对任一结点则对任一结点i(1 i n),(结点编号结点编号)有:有:(1)如果如果i=1,则结点则结点i是二叉树的根,无双亲;如果是二叉树的根,无双亲;如果i1,则其双亲是则其双亲是 i/2 (2)如果如果2in,则结点,则结点i无左孩子;无左孩子;如果如果2i n,则其左孩子是,则其左孩子是2i (3)如果如果2i+1n,则结点,则结点i无右孩子;无右孩子;如果如果2i+1 n,则其右孩子是,则其右孩子是2i+1病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起
11、不同程度的病理生理过程6.2.3 二叉树的存储结构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 11病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程v链式存储结构l二叉链表typedef struct node datatype data;struct node *lchild,*rchild;JD;lchild data rch
12、ild ABCDEFG在n个结点的二叉链表中,有n+1个空指针域 AB C D E F G病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程l三叉链表的存储typedef struct node datatype data;struct node *lchild,*rchild,*parent;JD;lchild data parent rchildABCDEFG A B C D E F G病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程 讨 论 在二叉链表中,查找结点都要
13、从根结点开始进行查找,查找的时间复杂度是结点的个数。而在三叉链表中查找结点实现就比较容易些,因为针对每个结点都可以进行上行查找或下行查找。病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程6.3 遍历二叉树和线索二叉树树的遍历v遍历按一定规律走遍树的各个顶点,且使每一顶点仅被访问一次,即找一个完整而有规律的走法,以得到树中所有结点的一个线性排列v常用方法l先根(序)遍历:先访问树的根结点,然后依次先根遍历根的每棵子树l后根(序)遍历:先依次后根遍历每棵子树,然后访问根结点l按层次遍历:先访问第一层上的结点,然后依次遍历第二层,第n层的
14、结点病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程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方法(D访问根,L访问左子树,R访问右子树)l先序(根)遍历:先访问根结点,然后分别先序遍历左子树、右子树l中序(根)遍历:先中序遍历左子树,然后访问根结点,
15、最后中序遍历右子树l后序(根)遍历:先后序遍历左、右子树,然后访问根结点DLRDLR、LDR、LRD病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程ADBCD L RAD L RD L RBDCD L R先序遍历序列:A B D C先序遍历:病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程ADBCL D RBL D RL D RADCL D R中序遍历序列:B D A C中序遍历:病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同
16、程度的病理生理过程ADBC L 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 f病原体侵入机体,消弱机体防御机能,破坏机体内环境的相对稳定性,且在一定部位生长繁殖,引起不同程度的病理生理过程例:已知二叉树先序序列:A B C D E F G H R,中序序列:B D C E A F H G R
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 二叉 ppt 课件
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内