数据结构重读 - 树的计数问题

树的计数问题:具有n个结点的不同形态的树共有多少棵。即具有n个结点、互不相似的二叉树的数目bn。

二叉树的相似:两棵都为空树或者两棵都不是空树,而且它们的左右子树分别相似。

二叉树的等价:两者不仅相似,而且对应结点上的元素均相同。

二叉树在bn较小的时候形态和计数如下:

经过书上复杂的推导,含有n个结点的互不相似的二叉树个数为:

如果推广一下,不是二叉树而是树,则:

具有n个结点的互不相似的树的个数为tn = bn-1

即:

关于给定先/中/后序构造二叉树的问题:

前序+中序,可以唯一确定一棵二叉树。

后序+中序,可以唯一确定一棵二叉树。

先序+后序,不能唯一确定一棵二叉树。

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *