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

百度出来的二叉排序树定义为：空二叉树或者满足：
1、若左子树不为空，则左子树上所有节点的值均小于它的根节点的值
2、若右子树不为空，则右子树上所有节点的值均小于它的跟节点的值
3、左右子树也分别为二叉排序树

答案为 14.
这种问题怎么算，谢谢。...百度出来的二叉排序树定义为：空二叉树或者满足：
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种，不知道是我理解误区在哪儿？请教各位了~~谢谢展开

torjanz · 2018-4-30 01:52:41

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

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

1 个回复

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