数据结构次课树和叉树.pptVIP

练习 一颗完全二叉树上有1001个结点，其中叶子结点的个数是_______。 A. 250 B. 500 C. 501 D. 505 练习 一棵有124个叶结点的完全二叉树，最多有_______个结点。 A. 248 B. 247 C. 249 D. 250 练习 在一棵 具有n个结点的完全二叉树，树枝结点的最大编号为_______。 A. B. C. D. 第六章 树和二叉树 6.1 树的定义和基本概念 6.2 二叉树 6.2.1 树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.4.3树和森林的遍历 6.6 赫夫曼树及其应用 6.6.1 最优二叉树（赫夫曼树） 6.6.2 赫夫曼编码 树结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。 树是递归结构，在树的定义中又用到了树的概念 树的定义 树是由 n (n ? 0) 个结点组成的有限集合。如果 n = 0，称为空树；如果 n 0，则 ? 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； ? 除根以外的其它结点划分为 m (m ? 0) 个 互不相交的有限集合T0, T1, …, Tm-1，每个集合又是一棵树，并且称之为根的子树。 例：下面的图是一棵树 T={A, B, C, D, E, F, G, H, I, J} A是根，其余结点可以划分为3个互不相交的集合： T1={B, E, F} , T2={C, G} , T3={D, H, I, J} 这些集合中的每一集合都本身又是一棵树，它们是A的子树。 例如 对于 T1，B是根，其余结点可以划分为2个互不相交的集合： T11={E}，T12={F}，T11,T12 是B的子树。 height = 3 A C G B D E F H I J 树的 基本术语 树结点： 包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子；双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；结点层次：根结点的层定义为1；根的孩子为第二层结点，依次类推；树的高（深）度：树中结点的最大层数；结点的度：结点子树的个数；树的度： 树中最大的结点度。叶子结点：也叫终端结点，是度为0的结点；分枝结点：度不为0的结点（非终端结点）；森林：互不相交的树集合；有序树：将数中每个结点的各子树看成是从左到右有次序的；无序树：不考虑子树的顺序； A B C D E F G H I J K 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的祖先 练习 1.假设在树中，结点x是结点y的双亲时，用（x,y）来表示树边，已知一棵树边的集合为：{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)} 用树形图表示出此树，并回答下列问题： (1)哪个是根结点？ (2)哪些是叶子结点？ (3)哪个是g的双亲？ (4)哪些是g的祖先？ (5)哪些是g的孩子？ (6)哪些是e的子孙？ (7)哪些是e的兄弟？哪些是f的兄弟？ (8)结点b和n的层次各是多少？ (9)树的深度是多少？ (10)以结点c为根的子树的深度是多少？ (11)树的度数是多少？ 练习 1.假设在树中，结点x是结点y的双亲时，用（x,y）来表示树边，已知一棵树边的集合为：{(i,m)