高校问答置之不理反义词:n个结点（大小都不相同）的二叉排序树共有几种排法？
来源：百度文库 编辑：高校问答 时间：2024/05/05 08:17:09
最好能有最后的推导公式。
其实我有答案，是我自己推导出来的：
排法总数为：14*pow(3,n-4) (n=4,5,6....)
当有两个结点时，有2种排法；
当有三个结点时，有5种排法。
大家可以试一下，有什么错误请指出！
其实我有答案，是我自己推导出来的：
排法总数为：14*pow(3,n-4) (n=4,5,6....)
当有两个结点时，有2种排法；
当有三个结点时，有5种排法。
大家可以试一下，有什么错误请指出！
既然是二叉树又怎么会 大小都不相同。
如果只是二叉树的话可以使用深度优先遍历实现前序、中序、后序遍历。使用广度优先可以实现按层遍历
前序
preorder(node *root){
if (root == null) return;
visited(root); //1
preorder(root->left); //2
preorder(root->right);//3
}
中序、后序只是注释1、2、3行的顺序问题
中序时2、1、3，后序是2、3、1
按层遍历需要用到队列
queue q;
q.enqueue(root);
while(!q.isempty()){
root = q.front;
visit(root);
q.dequeue();
if (root->left != null) q.enqueue(root->left);
if (root->right != null) q.enqueue(root->right);
}
楼上显然把BST当成普通的二叉树了
应该是2*N-1种
比如1,2,3 3个结点,2做根结点只有一种情况,1和3做根结点都有两种情况,共5种
N个结点的情况可以用归纳法证明
推荐您看一看catalan数就明白了