Question

设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n,则这棵二叉中共有( )个结点.

Answer 1

2n-1

度数只有0和2，说明这是一颗满二叉树，那么总节点数为2^(h+1) -1 h是高度，叶子节点数为2^h

则2^h=n

2^(h+1) -1=2n-1

扩展资料：

二叉树性质

性质1：二叉树的第i层上至多有2i-1（i≥1）个节点。

性质2：深度为h的二叉树中至多含有2h-1个节点。

性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。

性质4：具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）。

性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

当i=1时，该节点为根，它无双亲节点。

当i>1时，该节点的双亲节点的编号为i/2。

Answer 2

引用bjfu1106的回答：
2n+1,因为二叉树中有n2=n0+1，即度数为二的节点个数比度数为0的节点个数多1.详情可以参考数据结构C语言版第二版第118页，对这个性质有说明

由n0=n2+1，n0=n，立即推，总结点数为n0+n2=2n-1

Answer 3

n0=n2+1,度为零的节点总是比度为二的节点多一个。2n-1

Answer 4

引用bjfu1106的回答：
2n+1,因为二叉树中有n2=n0+1，即度数为二的节点个数比度数为0的节点个数多1.详情可以参考数据结构C语言版第二版第118页，对这个性质有说明

n0=n2+1书上是这样写的

Answer 5

2n+1,因为二叉树中有n2=n0+1，即度数为二的节点个数比度数为0的节点个数多1.详情可以参考数据结构C语言版第二版第118页，对这个性质有说明

追问

设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。