第06章树和二叉树(Java版)
- 格式:ppt
- 大小:5.59 MB
- 文档页数:101
第6章树和二叉树第 6 章树和二叉树6.1 已知一棵树如图所示,回答下列问题:(1) 哪个是根结点?(2) 哪些是叶子结点?(3) 哪个是结点 G 的双亲?(4) 哪些是结点 G 的祖先?(5) 哪些是结点 B 的孩子?(6) 哪些是结点B的子孙?(7) 哪些是结点 E 的兄弟?(8) 结点 B 和 H 的层次号分别是什么 ?(9) 树的深度是多少?(10) 以结点 C 为根的子树的深度是多少? 【6.1 解】:(1) A(2) K, F,G,H,I,J(3) B(4) B,A(5) E,F,G(6) E,F,G,K(7) F,G(8) 2, 3(9) 4(10) 26.2 在结点个数为n(n>1)的各棵树中,最小的高度是多少?它有多少个叶结点?多少个分支结点?最大的高度树是多少?它有多少个叶结点?多少个分去结点?【6.2解】结点个数为n时,高度最小的树高度为1,有2层;它有n-1个叶结点,1个分支结点;高度最大的树的高度为n-1,有n层;它有1个叶结点,n-1个分支结点。
6.3简述树与二叉树的区别?【6.3解】二叉树的度最大为2,而树的度可以大于2;二叉树的每个结点的孩子有左、右之分,而树中结点的孩子无左右之分。
6.4 n(n>1)个结点的各棵二叉树中,最小的高度(h≥1)多少?最大的高度是多少?【6.4解】最小高度为:⎣⎦n2log+1,此时树为完全二叉树;最大高度为n,比如一棵斜二叉树。
6.5如果一棵树有n1个度为1的结点,有n2个度为2的结点,…,n m个度为m的结点,试问有多少个度为0的结点?试推导之。
【6.5解】设叶子结点数为n0,则树中结点数和总度数分别为: 结点数=n0+n1+n2+...+n m总度数=n1+2n2+...+m×n m结点数等于总度数加1,所以得到:n0=∑=+-miini21))1((6.6如果已知一棵二叉树有20个叶子结点,有10个结点仅有左孩子,15个结点仅有右孩子,求出该二叉树的结点数目。