卡塔兰数和二叉树形态
给定n个节点，一共有多少个二叉树形态
设计一个递归算法，求在给定二叉树的结点总数N的情况下，二叉树可能拥有的形状数M。
例如
满足要求的任何一棵二叉树都是高度为N的满二叉树从根结点开始的子树。将这棵满二叉树的结点按照从上至下、从左至右的顺序进行编号，根结点的编号为1，则可以按层次输出任何结点总数为N的二叉树的所有结点编号。例如当N=3时，输出结果为：
1: 1, 2, 3
2: 1, 2, 4
3: 1, 2, 5
4: 1, 3, 6
5: 1, 3, 7
tree_count is 5 when N is 3
解答采用c++语法，运用了主要c语法以及&符号
递归实现版本
#include
#include
void arrange(int arr[],int idx,int N,int &tree_count,double &height)
{
int i=0;
int flag=-1;
if(idx==0)//idx为0时特殊实现
{
arr[idx]=1;
arrange(arr,idx+1,N,tree_count,height);
}
if(idx==N)//idx为N时则打印
{
tree_count++;
printf("%d:",tree_count);
for(int k=0;k { printf("%d ",arr[k]); } int h=(int)log2(arr[N-1]); printf("%20dheight",h); height+=h; printf("\n"); } if(idx>0&&idx { for(i=arr[idx-1]+1;i<=arr[idx-1]*2+1;i++)//利用顺序的排列，idx上的值要大于idx-1上的值 { flag=-1;//设置标志位为-1假如为1就进入下一个位置上值的寻找 arr[idx]=i; int k=0; for(;k { if((arr[idx]==arr[k]*2)||(arr[idx]==arr[k]*2+1)) { flag=1; break;//如果合法就break进入下一个位置寻找，由于栈会保留前面所有值 } } if(flag==1） { arrange(arr,idx+1,N,tree_count,height);//寻找下一个位置上的值 } } } } int main() { int arr[5]; int tree_count=0; int idx=0; int n=6; double height=0; arrange(arr,idx,n,tree_count,height); printf("tree_count is %d when N is %d\n",tree_count,n,height); printf("average height=%f",(double)height/(double)tree_count);//求平均高度 printf("\n log2N=%f",log2(n));//运用math函数 int c=1,i=0;//卡塔兰数的实现 for(i=n+2;i<=2*n;i++) //2n!/((n!)*n+1)-->2n!/(n+1)! c*=i; for(i=1;i<=n;i++) //2n!/((n!)*(n+1)!) c/=i; if(c==tree_count) printf("\nM和N之间满足卡塔兰数关系\n"); else printf("M和N之间不满足卡塔兰数关系\n"); } 递推实现版本 #include void buildtree(int N,int &tree_count) { tree_count=0; int arr[N]={0}; int arrappend[N]={0}; int idx=0; arr[0]=1; int tag=-1; int l=0; while(idx>-1) { while(arrappend[idx] { arrappend[idx]++; } //找到arrappend的值 if(idx { if(tag==1) { arrappend[idx]=0; idx--; tag=-1; while(arr[idx]*2+1==arr[idx+1]) { idx--; arrappend[idx+1]=0;//如果退后那么把后面arrappend的值抹去 } continue; } else { if(arr[arrappend[idx]]*2==arr[idx])//如果2倍那么设为2倍加一 { arr[idx+1]=arr[arrappend[idx]]*2+1; idx++; arrappend[idx-1]++; continue; } if(arr[arrappend[idx]]*2>arr[idx]&&arr[arrappend[idx]]*2!=arr[idx+1]) { //如果新的值不为2倍就设置为2倍 arr[idx+1]=2*arr[arrappend[idx]]; idx++; continue; } if(arr[arrappend[idx]]*2==arr[idx+1])//与arr[idx+1]比较与上面不同 { arr[idx+1]=arr[arrappend[idx]]*2+1; idx++ ; arrappend[idx-1]++; continue; } if(arr[arrappend[idx]]*2 { arrappend[idx]++; } } } else { tree_count++; printf("%d:",tree_count); for(int k=0;k { printf("%d ",arr[k]);//打印出一条路径 } for(int k=0;k { printf(" %d ",arrappend[k]); } printf("\n"); if(arr[idx]==arr[idx-1]*2+1) { tag=1; arr[idx]=0; } idx--; } } } int main() { int N=9; int tree_count=0; buildtree(N,tree_count); printf("\n%d 个",tree_count); } 以上两种方式还留有优化空间本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
