输入一组整数(假设各元素值均不相同),并按输入顺序建立二叉搜索树。设计一个递归算法按递减次序打印各元素的值。(用c语言)
时间: 2024-08-12 07:06:49 浏览: 52
关于PHP递归算法和应用方法介绍
在C语言中,你可以使用递归算法来构建一个二叉搜索树(BST)并按照递减顺序打印节点的值。首先,我们需要定义一个二叉搜索树节点结构和一些基本的递归函数。以下是一个简单的示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉搜索树节点结构
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 插入节点到BST
TreeNode* insertNode(TreeNode* root, int val) {
if (root == NULL) {
root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = root->right = NULL;
} else if (val < root->val) {
root->left = insertNode(root->left, val);
} else {
root->right = insertNode(root->right, val);
}
return root;
}
// 递归函数用于按照递减顺序访问节点
void printInDescendingOrder(TreeNode* node, int prev_val) {
if (node != NULL) {
printInDescendingOrder(node->right, node->val); // 先右子树
printf("%d ", node->val); // 打印当前节点值
if (prev_val < node->val) { // 如果前一个值小于当前值,说明应该左子树已经打印过了
printInDescendingOrder(node->left, node->val); // 现在从右到左访问左子树
}
}
}
int main() {
int arr[] = {9, 5, 10, 0, 6, 11};
int n = sizeof(arr) / sizeof(arr);
TreeNode* root = NULL;
for (int i = 0; i < n; i++) {
root = insertNode(root, arr[i]);
}
printf("Nodes in descending order: ");
printInDescendingOrder(root, INT_MAX); // 使用最大值初始化prev_val,确保先访问较大的节点
printf("\n");
return 0;
}
```
在这个代码中,`insertNode`函数用于插入新节点,保持BST的性质。`printInDescendingOrder`函数是一个递归函数,它会先访问右子树,然后打印节点值,接着如果前一个值小于当前值,就从右到左访问左子树,保证了递减打印。
相关问题:
1. 二叉搜索树的特点是什么?
2. 递归函数`printInDescendingOrder`的作用是什么?
3. `insertNode`函数中的条件判断是如何保证插入节点满足BST的性质的?
阅读全文