Question

数据结构问题 由4个节点可以构造出多少种不同的二叉树？

百度出来的二叉排序树定义为：空二叉树或者满足：
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种，不知道是我理解误区在哪儿？请教各位了~~谢谢

Answer 1

由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。

Answer 2

看了你上面的理解，你可能认为1节点和2、3、4节点不同，其实4个节点是相同的。例如：
1 2
\ \
3 4
\ \
2 1
\ \
4 3
这两个是相同的，因为节点是相同的！所以你上面的理解有重复出现的情况，所以才会多！

Answer 3

看了你上面的理解，你可能认为1节点和2、3、4节点不同，其实4个节点是相同的。例如：
1
2
\
\
3
4
\
\
2
1
\
\
4
3
这两个是相同的，因为节点是相同的！所以你上面的理解有重复出现的情况，所以才会多！