在用二叉链表表示的有n个结点的二叉树中，值为非空的链域的个数为多少？答案是n-1，这个是为什么啊，求解

wo370506875 · 2018-4-30 02:07:21

n个节点则有2n个链域，除了根节点没有被lchild和rchild指向，其余的节点必然会被指到。所以空链域公有2n-(n-1)=n+1;
非空链域有2n-(n+1)=n-1；

万同堂 · 2018-4-30 02:07:22

首先
二叉树的节点都有2个指针。每个节点有0个、1个或2个空指针。对应的有2个、1个、0个非空指针。非空指针的总数就是二叉树的边的个数。
设一个二叉树x个节点含有0个空指针，y个节点有1个空指针，z个节点有2个空指针
有如下等式
1、 x+y+z=N 节点总数为N，题目叙述
2、 y+2*z=N+1空指针个数为N+1，题目叙述
3、 2*x+y= N-1 二叉树的边数。树的边数=树的节点数-1
解以上方程组就可得出树的几种类型的节点数了。你就可以构造这个二叉树了。如果方程组有解
一般可以构造的二叉树是很多的。

在用二叉链表表示的有n个结点的二叉树中，值为非空的链域的个数为多少？答案是n-1，这个是为什么啊，求解

2 个回复