百度出来的二叉排序树定义为:空二叉树或者满足:
1、若左子树不为空,则左子树上所有节点的值均小于它的根节点的值
2、若右子树不为空,则右子树上所有节点的值均小于它的跟节点的值
3、左右子树也分别为二叉排序树
答案为 14.
这种问题怎么算,谢谢。
我的理解:(假如4个节点为1.2.3.4)
1 1 1 1 1 1
\ \ \ \ \ \
2 2 3 3 4 4
\ \ / \ \ / /
3 4 2 4 4 3 2
\ / / / \
4 3 2 2 3
2 2 3 3
/ \ / \ / \ / \
1 3 1 4 1 4 2 4
\ / \ /
4 3 2 1
4 4 4 4 4 4
/ / / / / /
3 3 2 2 1 1
/ / / \ / \ \
2 1 1 3 1 2 3
/ \ \ \ /
1 2 3 3 2
一共为 16种,教育部考试中心出的考试复习资料上的答案为 14种,不知道是我理解误区在哪儿?请教各位了~~谢谢
由4个节点可以构造出14种不同的二叉树。二叉树节点公式:B[n] = C[n,2n] / (n+1)。二叉树组合数C[n,2n]的n为上标,2n为下标,将n=4代入公式,可以得出,B[4] = C[4,8] / (4+1) = 8! / (4! * 4! * 5) = 8*7*6/(4*3*2) = 14。
扩展资料:
有N个结点的二叉树各结点如果用顺序方式存储,则结点之间有如下关系:
1、若I为结点编号则 如果I>1,则其父结点的编号为I/2。
2、如果2*I<=N,则其左孩子(即左子树的根结点)的编号为2*I;若2*I>N,则无左孩子。
3、如果2*I+1<=N,则其右孩子的结点编号为2*I+1;若2*I+1>N,则无右孩子。
4、设有i个枝点,I为所有枝点的道路长度总和,J为叶的道路长度总和J=I+2i。5、对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1。