计算机软件技术基础 教学课件 作者 李淑芬第4章.ppt

《计算机软件技术基础 教学课件 作者 李淑芬第4章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章树树与图属于非线性结构4.1树的概念4.1树的概念——树型结构应用举例“资源管理器”界面。4.1树的概念——树的结构定义树(Tree)是n(n>=0)个结点的有限集合。当n=0时，称为空树；当n>0时，称为非空树。在任意一棵非空树中：（1）有且仅有一个特定的结点，称为树根(root)，它没有直接前驱，但有零个或多个直接后继（2）当n>1时，其余结点被划分成m个互不相交的子集，每个子集又是一棵树，被称为子树(subtree)。4.1树的概念——树的表示方法（层次）abcdghijfemlk4.1树的概念——树的表示方法（集合）abc

2、deklfghmij4.1树的概念——树的表示方法（凹凸图）abeklfcgdhmij4.1树的概念——树的表示方法（广义表）(a(b(e(k,l),f),c(g),d(h(m),i,j)))4.1树的概念——基本术语结点结点的度，树的度叶子(终端结点)非终端结点结点的层次树的深度有序树，无序树森林abcdghijfemlk4.1树的概念——基本术语孩子双亲兄弟祖先子孙堂兄弟abcdghijfemlk4.2二叉树的基本概念和主要性质二叉树定义二叉树由n(n>=0)个元素组成。当n=0时，为空二叉树；当n>0时，有且仅有一个元素为根，其余结

3、点分成最多两个互不相交的子集，子集有左右顺序，每个子集又是一个二叉树。4.2二叉树的概念和性质——定义4.2二叉树的概念和性质——二叉树的五种形态RLLR满二叉树深度为k，且有2k-1个结点的二叉树。4.2二叉树的概念和性质——满二叉树完全二叉树:一棵深度为h，结点数为n的二叉树，如果其结点1n的位置序号分别与满二叉树的结点1n的位置序号一一对应，则为完全二叉树。满二叉树完全二叉树1234567123454.2二叉树的概念和性质——完全二叉树二叉树性质（性质1）在二叉树的第i层上至多有2i-1个结点。证明：(数学归纳法)i=1，只有根

4、结点，2i-1=20=1成立设1j

5、2+14.2二叉树的概念和性质——二叉树性质二叉树性质（性质4）具有n个结点的完全二叉树的深度为log2n+1。证明:设深度为k,则有:2k-1-11，则序号为i的结点的双亲结点序号为i/2；如2×i>n，则序号为i的结点无左孩子；如2×i≤n，则序号为i的结点的左孩子结点的序号为2×i；如2×i＋1>n，则序号为i的结点

6、无右孩子；如2×i＋1≤n，则序号为i的结点的右孩子结点的序号为2×i＋1。123454.2二叉树的概念和性质——二叉树性质4.3二叉树的存储顺序存储结构：顺序存储就是用一组地址连续的存储单元来存放一棵二叉树的结点。适用于存储完全二叉树或满二叉树。12345123454.3二叉树的存储——顺序存储结构二叉树顺序存储结构定义==================typedefstruct{DataTypedata[];intnum；}BTree;4.3二叉树的存储——顺序存储结构lchilddatarchildlchilddataparent

7、rchild链式存储结构：二叉树的链式存储结构是用链表来表示二叉树。4.3二叉树的存储——链式存储结构abcdefga^b^c^d^e^f^^g^T4.3二叉树的存储——链式存储结构二叉树链式存储结构定义==================typedefstructBTNode{DataTypedata;structBTNode*lchild,*rchild;}BTree;4.3二叉树的存储——链式存储结构4.4二叉树的遍历遍历二叉树：按某种搜索路径巡访二叉树中每个结点一次且仅一次的过程。访问顺序有：DLR,DRLLDR,RDLLRD,R

8、LD4.4二叉树的遍历——遍历的概念遍历二叉树DLR先序遍历LDR中序遍历LRD后序遍历4.4二叉树的遍历——遍历的概念PreOrder:abcdegfhInOrder:cbegdfahPos