数据结构-基于C++语言（微课版） 课件 1-1 树的逻辑模型

层次结构-树与二叉树线性结构表性线栈列队串和组数非线性结构数据结构树图层次结构应用背景层次结构-树与二叉树红楼家谱层次结构应用背景层次结构-树与二叉树部门结构目录结构本模块主要内容1、树与二叉树的逻辑模型；2、二叉树的基本性质3、二叉树的存储结构；4、二叉树的遍历以及算法实现；层次结构-树与二叉树5、树、森林与二叉树的转换；6、哈夫曼树及应用。层次结构树的定义树的判定本节目录：本节内容：树的逻辑模型树与二叉树的逻辑模型树与二叉树的逻辑模型树的逻辑模型ABCDFGHIJKLMEABCDEFGHABCDEFGHABCDEFGH(a)(b)(c)(d)树与二叉树的逻辑模型定义：树(Tree)是n个结点的有限集合T，满足:（2）其余的结点被分为m个互不相交的子集(T1、T2

、…Tm）ABDKEFLMJIHGCT1T2T3根每个子集本身又是一棵树，称为子树(Subtree)。（1）有且只有一个称为树的根(Root)结点；

树与二叉树的逻辑模型注意：互不相交的子集，子集也是一棵树，是子树。ABDKEFLMJIHGCT1T2T3根递归定义，除根结点外的任意一个结点，可以看作是子树的根结点。树与二叉树的逻辑模型树与非树：(a)树TABCDFGHIJKLMECHBFGLDIJKME(b)子树TA1(c)子树TA2

(d)子树TA3(e)子树TA4ABCDEFGHABCDEFGHABCDEFGH树与二叉树的逻辑模型根结点没有前驱结点；其它结点有且只有一个前驱结点；结点可有零个或多个后继结点。关于树的定义说明：根ABCDEIJFGHLMK小结：树的递归定义；判断树的标准；本节内容：树中的基本术语树与二叉树的逻辑模型ABDKEFLIGC根层次与线性结构的联系与区别；结点、结点的度、树的度、深度；结点间的关系。本节目录：本节内容：树中的基本术语树与二叉树的逻辑模型树与二叉树的逻辑模型根ABCDEIJFGHLMK基本术语:1）结点：表示树中的元素。A的度为4D的度为22）结点的度：结点拥有的子树个数。3）叶子结点：度为0的结点。树的度?F、L、H等为叶子结点树与二叉树的逻辑模型根ABCDEIJFGHLMK基本术语:4）双亲：一个结点的前驱结点。A的度为4D的度为25）孩子：结点的子树的根(后继结点)。6）兄弟：同一双亲的孩子。树的度为4B是F、G的双亲；F、G是B的孩子；树与二叉树的逻辑模型根ABCDEIJFGHLMK基本术语:7）结点的层次：根为第一层，根的直接后继结点为第二层，依此类推。8）深度：树中结点的最大层次数。1243层次号深度：4小结：结点间的关系；树的深度和度；叶子、根结点的特点；本节内容：树与二叉树的逻辑模型树与二叉树的逻辑模型本模块主要内容1、树与二叉树的逻辑模型；2、二叉树的基本性质；3、二叉树的存储结构；4、二叉树的遍历以及算法实现；层次结构-树与二叉树5、树、森林与二叉树的转换；二叉树的概念与术语；二叉树的基本形态。本节目录：本节内容：树与二叉树的逻辑模型树与二叉树的逻辑模型树与二叉树的逻辑模型定义：二叉树(Binarytree)是n(n≥0)个结点的有限集合。

1）若n=0时称为空树；

2）若n>1时，除根外，其余结点被分成为二个互不相交的子集T1,T2，分别称之为左、右子树，且左、右子树又都是二叉树。说明：递归定义，二叉树如不做特别说明，指有序树；EBADCFT1T2根树与二叉树的逻辑模型非二叉树说明：子树也是二叉树。EBADCFIGH以E为根的子树，不是二叉树。树与二叉树的逻辑模型形态一致，值不同说明：二叉树没有特别说明，认为是有序树。CABBACCBAABC两组不同的二叉树：值相等，形态不一致树与二叉树的逻辑模型说明：二叉树基本形态。二叉树的五种形态空只有