作业帮有关数据结构的树的问题
来源：学生作业帮 编辑：拍题作业网作业帮 分类：综合作业 时间：2024/05/29 09:15:20
有关数据结构的树的问题
设树T的度为4,其中度为1、2、3、4的结点个数分别是4、2、1和1,则T中叶子结点的个数是多少?
有人知道是为什么吗?有什么公式吗?
设树T的度为4,其中度为1、2、3、4的结点个数分别是4、2、1和1,则T中叶子结点的个数是多少?
有人知道是为什么吗?有什么公式吗?
用树来做比较简单：
根据每一行的输入创建一个树,然后合并到主树上,完后后,判断起来就简单了,都是树的标准操作.
还有一种做法,定义一个二维数组d,第一维表示第几个人,第二维表示这个人的儿子,没有儿子则初始化为长度为0的空数组,最后的数组是这样的：
2 3 4
5
-
-
-（最后三个为空数组）
然后根据输入的两个数d1,d2,按下面的方式寻找关系：
(1) 递归遍历数组d[d1],如果能够找到d2,表示d1是d2的祖先
(2) 否则,递归遍历d[d2],如果能够找到d1,表示d2是d1的祖先
(3) 否则,d1和d2没有关系
这里主要是递归遍历,例如输入1,5,先遍历d[1],也就是数组2,3,4,当遍历到2时,还要查看d[2],结果找到了5,说明1是5的祖先.
其实这里的数组就是一颗简易的树,遍历时采用的是深度优先策略.
另外,为了描述方便,这里假设数组序号是从1而不是从0开始的,即数组的第一项为d[1]
根据每一行的输入创建一个树,然后合并到主树上,完后后,判断起来就简单了,都是树的标准操作.
还有一种做法,定义一个二维数组d,第一维表示第几个人,第二维表示这个人的儿子,没有儿子则初始化为长度为0的空数组,最后的数组是这样的：
2 3 4
5
-
-
-（最后三个为空数组）
然后根据输入的两个数d1,d2,按下面的方式寻找关系：
(1) 递归遍历数组d[d1],如果能够找到d2,表示d1是d2的祖先
(2) 否则,递归遍历d[d2],如果能够找到d1,表示d2是d1的祖先
(3) 否则,d1和d2没有关系
这里主要是递归遍历,例如输入1,5,先遍历d[1],也就是数组2,3,4,当遍历到2时,还要查看d[2],结果找到了5,说明1是5的祖先.
其实这里的数组就是一颗简易的树,遍历时采用的是深度优先策略.
另外,为了描述方便,这里假设数组序号是从1而不是从0开始的,即数组的第一项为d[1]