《数据结构与算法分析》课程教学课件（PPT讲稿）第六章 树与二叉树

第6章树和二叉树 从对线性结构的研究过渡到对树形 结构的研究，是数据结构课程学习的一 次跃变

从对线性结构的研究过渡到对树形 结构的研究，是数据结构课程学习的一 次跃变

6.1 树的定义和基本术语 1.树的定义（非递归) 树是由n(n≥0)个结点组成的有限集合。 如果n=0,称为空树； 如果n>0,则： ·有一个特定的称之为根(roo)的结点，它只有 后继，但没有前驱； ·其余结点有且仅有一个直接前驱，但可以有0 个或多个后继

6.1 树的定义和基本术语 1. 树的定义 （非递归） 树是由n (n  0)个结点组成的有限集合。 如果n = 0，称为空树； 如果n > 0，则: ▪ 有一个特定的称之为根(root)的结点，它只有 后继，但没有前驱； ▪ 其余结点有且仅有一个直接前驱，但可以有0 个或多个后继

A B E F H 是不是一棵树？

是不是一棵树？

2、树的基本术语

A B C E F H M 结点：数据元素及其分支

结点：数据元素及其分支

A B C D E E © H K L M 结点的子树

结点的子树

A B 结点的度：结点射出的分支数。 树的度：树内各结点度的最大值

结点的度: 结点射出的分支数。 树的度：树内各结点度的最大值

A B 叶子结点（终端）：度为0的结点。 非终端结点：度不为0的结点。 结点的层次：树中根结点的层次为1，下一层结点的层次是2， 以此类推。 树的深度：树中所有结点层次的最大值

叶子结点（终端）: 度为0的结点。 非终端结点: 度不为0的结点。 结点的层次: 树中根结点的层次为1，下一层结点的层次是2， 以此类推。 树的深度: 树中所有结点层次的最大值

B 父结点：结点的前驱称为该结点的父亲。 孩子结点：结点的后继称为该结点的孩子。 兄弟：同一个父亲的孩子之间互称兄弟。 堂兄弟：兄弟的孩子之间互称堂兄弟。 有序树、无序树：如果树中每棵子树从左向右的排列拥有一定 的顺序，不得互换，则称为有序树，否则称为无序树

父结点：结点的前驱称为该结点的父亲。 孩子结点：结点的后继称为该结点的孩子。 兄弟：同一个父亲的孩子之间互称兄弟。 堂兄弟：兄弟的孩子之间互称堂兄弟。 有序树、无序树: 如果树中每棵子树从左向右的排列拥有一定 的顺序，不得互换，则称为有序树，否则称为无序树

B 填空： 对于一棵具有个结点的树，该树中所有结点的度数之和为？ 答：结点的度数之和应为所有分支数之和，除了根结点之外， 所有结点都有一个分支射入，因此树中所有结点度数之和是 n-1

填空： 对于一棵具有n个结点的树，该树中所有结点的度数之和为？ 答：结点的度数之和应为所有分支数之和，除了根结点之外， 所有结点都有一个分支射入，因此树中所有结点度数之和是 ｎ－１