输入一组整数(假设各元素值均不相同),并按输入顺序建立二叉搜索树。设计一个递归算法按递减次序打印各元素的值。
时间: 2023-06-20 10:04:04 浏览: 29
以下是递归算法的实现:
1. 首先将输入的整数构建成一棵二叉搜索树,保证左子树的元素值小于根节点的元素值,右子树的元素值大于根节点的元素值。
2. 然后采用递归的方式,先访问右子树,再访问根节点,最后访问左子树。
3. 当访问到某个节点时,先递归访问其右子树,即对右子树进行递归调用。
4. 然后打印该节点的元素值。
5. 最后递归访问其左子树,即对左子树进行递归调用。
以下是具体的代码实现:
```
// 定义二叉树节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void printReverse(TreeNode* root) {
if (root == nullptr) {
return;
}
// 先访问右子树
printReverse(root->right);
// 打印当前节点的值
cout << root->val << " ";
// 再访问左子树
printReverse(root->left);
}
// 构建二叉搜索树
TreeNode* buildBST(vector<int>& nums, int left, int right) {
if (left > right) {
return nullptr;
}
// 找到中间节点
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[mid]);
// 递归构建左子树和右子树
root->left = buildBST(nums, left, mid - 1);
root->right = buildBST(nums, mid + 1, right);
return root;
}
int main() {
vector<int> nums = {5, 3, 6, 2, 4, 1};
TreeNode* root = buildBST(nums, 0, nums.size() - 1);
cout << "按递减次序打印二叉搜索树的元素值:" << endl;
printReverse(root);
cout << endl;
return 0;
}
```
假设输入的整数为{5, 3, 6, 2, 4, 1},则打印的结果为:6 5 4 3 2 1。