根结点值小于L 根结点和左子树中节点关键码值均小于L 在区间之外 应该全部丢弃 右子树中可能有节点值在区间外 也可能有节点值在区间内 所以对右子树递归裁剪 由于左子树和根结点均被丢弃 所以直接返回右子树裁剪结果的根结点根结点大于R情形类似如果根结点在区间内 则不应丢弃 但此时左右子树均可能有节点在区间外所以对左右子树递归裁剪 裁剪结果链接回根结点如果二叉搜索树为空 裁剪结果仍为空树 直接返回空指针更新2019.6.19刚才看了一下递归代码存在一个问题假若向下搜索过程中找到了一棵根节点无需修剪但根节点子树可能需要修剪的BST那么递归函数会在左右子树中递归搜索根节点无需修剪的子树在搜索过程中遇到的根节点和左子树或右子树需要全部修剪的子树对应递归调用的一层调用栈中会为该层的函数调用信息开辟栈空间而这是没有必要的因为遇到的子树根节点和根节点的左子树(右子树)应全部抛弃只需修剪根节点的右子树(左子树)因此在这一层为根节点和根节点的左子树(右子树)应该被抛弃的子树保留栈空间是没有必要造成了空间的浪费实际上我们只需将搜索过程中遇到的根节点不应被修剪的BST子树的根节点压栈即可而且整个过程完全可以用非递归的方式实现自己编写的经过优化后的非递归代码如下#includeiostream#includestack#includevectorusingnamespacestd;structBSTNode//二叉搜索树节点定义{intdata;//数据域BSTNode*left_childnullptr;BSTNode*right_childnullptr;BSTNode(intd):data(d){}BSTNode(constBSTNodebe_copy):data(be_copy.data),left_child(nullptr),right_child(nullptr){}};BSTNode*trimBST(BSTNode*root,intleft,intright)//修剪二叉搜索树只保留区间[left, right]内的节点{enumProcessRate{START,LEFT_SUB_TREE,RIGHT_SUB_TREE};//处理状态尚未修剪任何子树已修剪过左子树两棵子树均已修剪structStackNode{BSTNode*ptr_to_node_every_layer;//需修剪的BST根节点指针ProcessRate rateProcessRate::START;//修剪状态BSTNode*ptr_to_root_beconstructed;//修剪后形成的新的BST根节点指针StackNode(BSTNode*p):ptr_to_node_every_layer(p){ptr_to_root_beconstructednewBSTNode(*ptr_to_node_every_layer);}};stackStackNodework_stack;BSTNode*curroot;while(cur!nullptr){if(rightcur-data){curcur-left_child;}elseif(cur-dataleft){curcur-right_child;}else{work_stack.push(StackNode(cur));break;}}if(curnullptr){returnnullptr;}while(true){if(work_stack.top().rate!ProcessRate::RIGHT_SUB_TREE){if(work_stack.top().rateProcessRate::START)//左子树尚未修剪修剪左子树{curwork_stack.top().ptr_to_node_every_layer-left_child;}elseif(work_stack.top().rateProcessRate::LEFT_SUB_TREE)//右子树尚未修剪修剪右子树{curwork_stack.top().ptr_to_node_every_layer-right_child;}while(cur!nullptr)//向下搜索抛弃修剪掉的部分{if(rightcur-data){curcur-left_child;}elseif(cur-dataleft){curcur-right_child;}else{work_stack.push(StackNode(cur));//找到根节点无需修剪但子树需修剪的BST子树break;}}if(curnullptr)//被修剪的子树为空或子树中所有节点值都在[L,R]外{if(work_stack.top().rateProcessRate::START){work_stack.top().rateProcessRate::LEFT_SUB_TREE;}else{work_stack.top().rateProcessRate::RIGHT_SUB_TREE;}}}else//当前BST左右子树均修剪完毕{StackNode tempwork_stack.top();work_stack.pop();if(work_stack.empty()false)//栈不为空,将已经修剪完毕的当前BST链接至上一层需修剪的BST的子女指针域并更新上一层修剪状态{if(work_stack.top().rateProcessRate::START){work_stack.top().ptr_to_root_beconstructed-left_childtemp.ptr_to_root_beconstructed;work_stack.top().rateProcessRate::LEFT_SUB_TREE;}elseif(work_stack.top().rateProcessRate::LEFT_SUB_TREE){work_stack.top().ptr_to_root_beconstructed-right_childtemp.ptr_to_root_beconstructed;work_stack.top().rateProcessRate::RIGHT_SUB_TREE;}}else{returntemp.ptr_to_root_beconstructed;//如果栈为空说明当前已经修剪完毕的BST子树就是最终修剪结果直接返回}}}}voidinorderTraverse(BSTNode*root)//输出中序序列{if(root!nullptr){inorderTraverse(root-left_child);coutroot-data ;inorderTraverse(root-right_child);}}intmain(){BSTNode*rootnullptr;vectorintinput{4,89,23,46,12,3,56,78,34,45,11};//插入BST中的数据for(constinti:input){BSTNode*temproot;if(tempnullptr){rootnewBSTNode(i);}else{BSTNode*parentnullptr;while(temp!nullptr){if(temp-datai)break;parenttemp;if(temp-datai){temptemp-right_child;}elseif(temp-datai){temptemp-left_child;}}if(tempnullptr){if(iparent-data){parent-left_childnewBSTNode(i);}else{parent-right_childnewBSTNode(i);}}}}BSTNode*_newtrimBST(root,5,50);cout修剪后的二叉树的中序序列为:;if(_newnullptr){coutNULL;}else{inorderTraverse(_new);}coutendl;return0;}仅供参考