1、数据结构与算法树与二叉树赵颖 中南大学，赵颖 中南大学目录n 树的概念n 二叉树的概念n 二叉树的性质n 二叉树的存储结构赵颖 中南大学树的概念n 树是一种非常重要的非线性结构 树形结构重的元素存在逻辑上的 一对多 的关系，并且还体现了 分支结构 和 层次关系 ，是非常重要的非线性结构 现实生活中举例：家谱，行政机构组织图 计算机应用举例：编译器的语法分析树，哈夫曼编码复习：数据的逻辑结构复习：数据的逻辑结构数据结构中所说的数据结构中所说的 “关系关系 ”实际上是指数据元素之间实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。可归结为的逻辑关系，又称此为逻辑结构。可归结为 :线性结构线
2、性结构结构中的数据元素之间存在一对一的关系；树形结构树形结构结构中的数据元素之间存在一对多的关系；图状结构图状结构 (网状结构网状结构 ) 结构中的数据元素之间存在多对多的关系。赵颖 中南大学树的概念n 树的定义（递归定义法） 树是由 n (n 0) 个结点组成的有限集合 如果 n = 0，称为空树； 如果 n 0，则n 有一个特定的称之为 根 (root)的结点，它只有直接后继，但没有直接前驱；n 除根以外的其它结点划分为 m (m 0) 个互不相交的有限集合 T0, T1, , Tm-1，每个集合又是一棵树，称之 子树 。bacg hd e fi j赵颖 中南大学ACGB DE FK
3、LHMI J例如A只有根结点的树有 13个结点的树其中： A是根；其余结点分成三个互不相交的子集，T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M,T1,T2,T3都是根 A的子树，且本身也是一棵树空树赵颖 中南大学树的概念1层2层4层3层height= 4ACGB DE FK LHMI J结点结点的度分支结点叶结点子女双亲兄弟祖先子孙结点层次树的度树 高度森林树的基本术语赵颖 中南大学树的概念n 树的基本术语 结点 (node)表示树中的元素，包括数据项及若干指向其子树的分支 结点的度 (degree)结点拥有的子树数 叶子 (leaf)度为 0的结点 分支结点 -度
4、不为 0的结点 有序树、无序树 -如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树 树的度 一棵树中最大的结点度数，如果树的度为 k，可以称这棵树为 k叉树 结点的层次 (level)从根结点算起，根为第一层，它的孩子为第二层 树的深度 (depth)树中结点的最大层次数 森林 (forest)m(m0)棵互不相交的树的集合AB C DE F G H I JK L M赵颖 中南大学树的概念n 树的基本术语 在树结构中，结点之间的关系又可以用 家族关系 描述，定义如下： 孩子、双亲 -结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。 子孙 -以
5、某结点为根的子树中的所有结点都被称为是该结点的子孙。 祖先 -从根结点到该结点路径上的所有结点。 兄弟 -同一个双亲的孩子之间互为兄弟。 堂兄弟 -双亲在同一层的结点互为堂兄弟。AB C DE F G H I JK L M赵颖 中南大学树的概念AB C DE F G H I JK L M结点 A的度：？结点 B的度：？结点 M的度：？叶子：？结点 A的孩子：？结点 B的孩子：？结点 I的双亲：？结点 L的双亲：？结点 B， C， D为兄弟结点 K， L为兄弟树的度：？结点 A的层次：？结点 M的层次：？树的深度：？结点 F， G为堂兄弟结点 A是结点 F， G的祖先练习赵颖 中南大学树的概念AB C DE F G H I JK L M结点 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的祖先
