基础题目--树

xiaoxiao2021-02-28  25

1 一个具有767个节点的完全二叉树,其叶子节点个数为()

一棵树含有n个结点,则最后一个结点的编号必为n,它的父结点则为n/2,且为上一层最右边的一个根结点。 所以叶结点的个数就为:n-n/2。 此题中,n = 767,n-n/2 = 767 - 767/2 = 384。 2 高度为h(h>0)的完全二叉树对应的森林所含的树的个数一定是h()  错

二叉树转换为森林

假如一棵二叉树的根节点有右孩子,则这棵二叉树能够转换为森林,否则将转换为一棵树。

(1)从根节点开始,若右孩子存在,则把与右孩子结点的连线删除。再查看分离后的二叉树,若其根节点的右孩子存在,则连线删除…。直到所有这些根节点与右孩子的连线都删除为止。

(2)将每棵分离后的二叉树转换为树。

3 在具有   2n   个结点的完全二叉树中,叶子结点个数为(   完全二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点。根据完全二叉树性质,如果共2n 个结点,从根结点开始按层序用自然数 1  2 ,…, 2n 给结点编号,则编号为 n 的结点左子结点编号为 2n ,因此叶子结点编号为n+1,n+2,  ,2n 。故叶子结点个数为 n  答案 n

4 由权值分别为1、12、13、4、8的叶子节点生成一颗哈夫曼树,它的带权路径长度为(81)

-------设一棵二叉树中有3个叶子节点,有8个度为1的节点,则该二叉树中总的节点数为?

有公式:N2=N0-1,度为2的节点个数是度为0的节点个数减一,所以N0=3,则N2=2,再加上N1=8,总的是13

转载请注明原文地址: https://www.6miu.com/read-850040.html

最新回复(0)