尧图网页设计 
Python语言没有学过 不熟悉 暂且不找代码漏洞和错误 这里只讲一下个人解决这个问题的思路 首先以1,2,–3,n 为节点的所有二叉搜索树就是以123–n为中序序列的所有二叉树那么一种思路是非递归中序遍历中序序列为1 2 3—n的二叉树时入栈序列是前序序列出栈序列为中序序列 因此我们只需求出出栈序列1,2,3,—,n对应的所有合法的入栈序列就可知中序序列1,2,3,–,n对应的所有前序序列这些前序序列数目就是中序序列为1,2–n的二叉树(二叉搜索树)数目,将中序序列1,2,—,n和求出的每一个前序序列还原为二叉树即可得要求的所有二叉搜索树如果想要用这种方式解决本问题就必须解决通过编程构造出栈序列对应的所有合法入栈序列的问题当然这种方法太笨太过低效完全可以在递归处理中序序列时顺便构造出所有二叉搜索树这样做思路很简单对于给定序列L现在要得到以其为中序序列的所有二叉树我们只需遍历L遍历过程中每到达一个节点N就以其为二叉树根节点,L在N左右两侧的子序列LL,LR分别是以其为中序序列的所有可能的左子树和右子树的中序序列因此只需递归地在LL和LR上寻找以其为中序序列的所有二叉树,随后将以LL为中序序列的每一个二叉树根节点链接至根节点N左指针域将以LR为中序序列的每一个二叉树链接至根节点N的右指针域这样就得到了以L为中序序列以N为根节点的所有二叉树按以上方法重复处理L中每一个节点处理完毕后就得到了以L为中序序列的所有二叉树令L1,2,—,n使用上述步骤即可构造出以1,2,—,n为中序序列的所有二叉树(二叉搜索树)这种方法也可以推广到构造以给定序列为前序序列或后序序列的所有二叉树使用类似的思想也可构造出具有指定前序序列和后序序列的所有二叉树编写递归函数实现上述过程的伪代码如下vectorconstructBinaryTree(Seq L){if(L.length0){vector.push(NULL)}else{for(every node have index t in L){LLL[0,t-1]LRL[t1,L.length-1];vector LsubconstructBinaryTree(LL)vector RsubconstructBinaryTree(LR)for(every node i in Lsub){for(every node j in Rsub){Node_ptrnewNode(L[t])Node_ptr.leftchildi Node_ptr.rightchildj;vector.push(Node_ptr)}}}}returnvector}伪代码对应的C代码写好了结果是n4时共可构造出14棵二叉搜索树#includeiostream#includevector#includememory#includerandomusingnamespacestd;structBinaryTreeNode//二叉树节点类{intdata;BinaryTreeNode*left_childnullptr;BinaryTreeNode*right_childnullptr;BinaryTreeNode(intd):data(d){}BinaryTreeNode(constBinaryTreeNodecopied):data(copied.data),left_child(nullptr),right_child(nullptr){}};BinaryTreeNode*copyTree(BinaryTreeNode*root){if(rootnullptr)returnnullptr;BinaryTreeNode*_newnewBinaryTreeNode(*root);_new-left_childcopyTree(root-left_child);_new-right_childcopyTree(root-right_child);return_new;}voiddelTree(BinaryTreeNode*root){if(rootnullptr)return;delTree(root-left_child);delTree(root-right_child);deleteroot;}shared_ptrvectorBinaryTreeNode*constructBinaryTree(vectorintinorder_traversal,size_t left_index,size_t right_index){if(left_indexright_index)//二叉树为空树直接返回空根节点{returnmake_sharedvectorBinaryTreeNode*(1,nullptr);}shared_ptrvectorBinaryTreeNode*root_node_listmake_sharedvectorBinaryTreeNode*();//当前中序序列对应的所有二叉树的根节点表for(size_t ileft_index-1;iright_index;i){shared_ptrvectorBinaryTreeNode*left_sub(constructBinaryTree(inorder_traversal,left_index,i));//构造所有左子树shared_ptrvectorBinaryTreeNode*right_sub(constructBinaryTree(inorder_traversal,i2,right_index));//构造所有右子树for(size_t j0;jleft_sub-size();j){for(size_t k0;kright_sub-size();k)//由构造出的左右子树合成当前中序序列对应的所有二叉树{BinaryTreeNode*rootnewBinaryTreeNode(inorder_traversal[i]);if(k0)root-left_child(*left_sub)[j];elseroot-left_childcopyTree((*left_sub)[j]);if(j0)root-right_child(*right_sub)[k];elseroot-right_childcopyTree((*right_sub)[k]);root_node_list-push_back(root);}}}returnroot_node_list;}structJudgeResult//对二叉树的判断结果{boolisBSTtrue;//是否为二叉搜索树intmax_value_in_BST0;//二叉搜索树中最大节点值intmin_value_in_BST0;//二叉搜索树中的最小节点值};JudgeResultisBST(BinaryTreeNode*root)//判断二叉树是否为二叉搜索树{if(rootnullptr){returnJudgeResult();}JudgeResult result;if(root-left_child!nullptr){JudgeResult tempisBST(root-left_child);if(temp.isBSTtruetemp.max_value_in_BSTroot-data){result.min_value_in_BSTtemp.min_value_in_BST;}else{result.isBSTfalse;}}else{result.min_value_in_BSTroot-data;}if(root-right_child!nullptr){JudgeResult tempisBST(root-right_child);if(temp.isBSTtruetemp.min_value_in_BSTroot-data){result.max_value_in_BSTtemp.max_value_in_BST;}else{result.isBSTfalse;}}else{result.max_value_in_BSTroot-data;}returnresult;}intmain(){unsignedn10;vectorintinorder_traversal(n);for(unsignedi0;in;i)inorder_traversal[i]i1;shared_ptrvectorBinaryTreeNode*root_listconstructBinaryTree(inorder_traversal,1,n);for(size_t i0;iroot_list-size();i){JudgeResult resultisBST((*root_list)[i]);if(result.isBSTfalse){cout错误,构造出的二叉树中存在不为二叉搜索树的二叉树;exit(-1);}}cout中序序列;for(intm:inorder_traversal){coutm ;}cout对应的二叉树共有root_list-size()棵,它们均为二叉搜索树endl;for(size_t i0;iroot_list-size();i){delTree((*root_list)[i]);}cout销毁成功endl;return0;}运行结果这个问题网上实际上到处是解答解法虽然是独立思考得到的没有参考现成解答但显然和大多数已有的解法重复了 暂且这样吧 构造所有二叉树搜索树
Python语言没有学过 不熟悉 暂且不找代码漏洞和错误 这里只讲一下个人解决这个问题的思路 首先以1,2,–3,n 为节点的所有二叉搜索树就是以123–n为中序序列的所有二叉树那么一种思路是非递归中序遍历中序序列为1 2 3—n的二叉树时入栈序列是前序序列出栈序列为中序序列 因此我们只需求出出栈序列1,2,3,—,n对应的所有合法的入栈序列就可知中序序列1,2,3,–,n对应的所有前序序列这些前序序列数目就是中序序列为1,2–n的二叉树(二叉搜索树)数目,将中序序列1,2,—,n和求出的每一个前序序列还原为二叉树即可得要求的所有二叉搜索树如果想要用这种方式解决本问题就必须解决通过编程构造出栈序列对应的所有合法入栈序列的问题当然这种方法太笨太过低效完全可以在递归处理中序序列时顺便构造出所有二叉搜索树这样做思路很简单对于给定序列L现在要得到以其为中序序列的所有二叉树我们只需遍历L遍历过程中每到达一个节点N就以其为二叉树根节点,L在N左右两侧的子序列LL,LR分别是以其为中序序列的所有可能的左子树和右子树的中序序列因此只需递归地在LL和LR上寻找以其为中序序列的所有二叉树,随后将以LL为中序序列的每一个二叉树根节点链接至根节点N左指针域将以LR为中序序列的每一个二叉树链接至根节点N的右指针域这样就得到了以L为中序序列以N为根节点的所有二叉树按以上方法重复处理L中每一个节点处理完毕后就得到了以L为中序序列的所有二叉树令L1,2,—,n使用上述步骤即可构造出以1,2,—,n为中序序列的所有二叉树(二叉搜索树)这种方法也可以推广到构造以给定序列为前序序列或后序序列的所有二叉树使用类似的思想也可构造出具有指定前序序列和后序序列的所有二叉树编写递归函数实现上述过程的伪代码如下vectorconstructBinaryTree(Seq L){if(L.length0){vector.push(NULL)}else{for(every node have index t in L){LLL[0,t-1]LRL[t1,L.length-1];vector LsubconstructBinaryTree(LL)vector RsubconstructBinaryTree(LR)for(every node i in Lsub){for(every node j in Rsub){Node_ptrnewNode(L[t])Node_ptr.leftchildi Node_ptr.rightchildj;vector.push(Node_ptr)}}}}returnvector}伪代码对应的C代码写好了结果是n4时共可构造出14棵二叉搜索树#includeiostream#includevector#includememory#includerandomusingnamespacestd;structBinaryTreeNode//二叉树节点类{intdata;BinaryTreeNode*left_childnullptr;BinaryTreeNode*right_childnullptr;BinaryTreeNode(intd):data(d){}BinaryTreeNode(constBinaryTreeNodecopied):data(copied.data),left_child(nullptr),right_child(nullptr){}};BinaryTreeNode*copyTree(BinaryTreeNode*root){if(rootnullptr)returnnullptr;BinaryTreeNode*_newnewBinaryTreeNode(*root);_new-left_childcopyTree(root-left_child);_new-right_childcopyTree(root-right_child);return_new;}voiddelTree(BinaryTreeNode*root){if(rootnullptr)return;delTree(root-left_child);delTree(root-right_child);deleteroot;}shared_ptrvectorBinaryTreeNode*constructBinaryTree(vectorintinorder_traversal,size_t left_index,size_t right_index){if(left_indexright_index)//二叉树为空树直接返回空根节点{returnmake_sharedvectorBinaryTreeNode*(1,nullptr);}shared_ptrvectorBinaryTreeNode*root_node_listmake_sharedvectorBinaryTreeNode*();//当前中序序列对应的所有二叉树的根节点表for(size_t ileft_index-1;iright_index;i){shared_ptrvectorBinaryTreeNode*left_sub(constructBinaryTree(inorder_traversal,left_index,i));//构造所有左子树shared_ptrvectorBinaryTreeNode*right_sub(constructBinaryTree(inorder_traversal,i2,right_index));//构造所有右子树for(size_t j0;jleft_sub-size();j){for(size_t k0;kright_sub-size();k)//由构造出的左右子树合成当前中序序列对应的所有二叉树{BinaryTreeNode*rootnewBinaryTreeNode(inorder_traversal[i]);if(k0)root-left_child(*left_sub)[j];elseroot-left_childcopyTree((*left_sub)[j]);if(j0)root-right_child(*right_sub)[k];elseroot-right_childcopyTree((*right_sub)[k]);root_node_list-push_back(root);}}}returnroot_node_list;}structJudgeResult//对二叉树的判断结果{boolisBSTtrue;//是否为二叉搜索树intmax_value_in_BST0;//二叉搜索树中最大节点值intmin_value_in_BST0;//二叉搜索树中的最小节点值};JudgeResultisBST(BinaryTreeNode*root)//判断二叉树是否为二叉搜索树{if(rootnullptr){returnJudgeResult();}JudgeResult result;if(root-left_child!nullptr){JudgeResult tempisBST(root-left_child);if(temp.isBSTtruetemp.max_value_in_BSTroot-data){result.min_value_in_BSTtemp.min_value_in_BST;}else{result.isBSTfalse;}}else{result.min_value_in_BSTroot-data;}if(root-right_child!nullptr){JudgeResult tempisBST(root-right_child);if(temp.isBSTtruetemp.min_value_in_BSTroot-data){result.max_value_in_BSTtemp.max_value_in_BST;}else{result.isBSTfalse;}}else{result.max_value_in_BSTroot-data;}returnresult;}intmain(){unsignedn10;vectorintinorder_traversal(n);for(unsignedi0;in;i)inorder_traversal[i]i1;shared_ptrvectorBinaryTreeNode*root_listconstructBinaryTree(inorder_traversal,1,n);for(size_t i0;iroot_list-size();i){JudgeResult resultisBST((*root_list)[i]);if(result.isBSTfalse){cout错误,构造出的二叉树中存在不为二叉搜索树的二叉树;exit(-1);}}cout中序序列;for(intm:inorder_traversal){coutm ;}cout对应的二叉树共有root_list-size()棵,它们均为二叉搜索树endl;for(size_t i0;iroot_list-size();i){delTree((*root_list)[i]);}cout销毁成功endl;return0;}运行结果这个问题网上实际上到处是解答解法虽然是独立思考得到的没有参考现成解答但显然和大多数已有的解法重复了 暂且这样吧