题意描述

　　定义二叉树的标号概念：
　　　　仅有一个元素的树标号为1。
　　　　定义二叉树a的序号比b大为：
　　　　　　1．a的节点数比b多。
　　　　　　2．若a的节点数与b相等，且a的左子树标号比b的左子树大。
　　　　　　3．a的节点数和左子树标号都和b相等，且a的右子树标号比b的右子树大。
　　给定标号，求相应的二叉树。

算法分析

　　很容易想到具有s个节点的二叉树个数的递归式：
　　　　　　　　　　　。
　　用此式来计算标号为k的二叉树的节点数t，以及是具有t个节点的二叉树中的第n个。
　　　　节点数。
　　　　在t节点二叉树的序号n=k-f (t-1)。
　　为了方便描述，我们定义具有t个节点的第n个二叉为t－n。
进而想到可利用这个递归式来计算二叉树的左右子树。方法是：根据递归式求出t－n的左子树i－j和右子树t-i-1－k，然后分别递归地计算左子树和右子树。递归的边界是k=0或1，此时对应的二叉树可直接计算。打印时可采取边递归边打印的方法：设左子树为left，右子树为right，当前树即为：left+X+right。(详见参考程序)