n个节点的二叉树有多少种形态??

发布网友发布时间：2024-10-16 08:34

共1个回答

热心网友时间：2024-11-03 17:42

n个节点的二叉树有多少种形态?

公式: 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

所以,由4个结点可以构造出 14 种不同形态的二叉树.

对于上述公式的详细介绍,可以搜索 [ n个节点的二叉树有多少种形态 ]
或者,搜索 [ Catalan数 —— 卡特兰数 ]

另外,可以验证: 由3个结点可以构造出多少种不同形态的二叉树?

将n=3代入公式,B[3] = C[3,6] / (3+1) = 6! / (3! * 3! * 4) = 6*5/(3*2) = 5
所以,由3个结点可以构造出5种不同形态的二叉树.

附: 4个结点对应的14种形态的二叉树

       #     #      #       #        #
      /     /      /       /        /
     #     #      #       #        #
    /     /      / \       \        \
   #     #      #   #       #        #
  /       \                  \      /
#         #                  #    #

#        #        #         #       #
  \        \        \         \       \
   #        #        #         #       #
    \        \      / \       /       /
     #        #    #   #     #       #
      \      /              /         \
       #    #              #           #

     #        #        #        #
    / \      / \      / \      / \
   #   #    #   #    #   #    #   #
  /          \          /          \
#            #        #            #