算法设计题:查找给定关键词的结点在二叉查找树中的层数。c语言
时间: 2024-05-01 15:22:50 浏览: 22
以下是一个基于递归的二叉查找树层数查找函数:
```c
int findNodeLevel(Node* root, int key, int level) {
if(root == NULL) {
return 0;
}
if(root->data == key) {
return level;
}
else if(key < root->data) {
return findNodeLevel(root->left, key, level+1);
}
else {
return findNodeLevel(root->right, key, level+1);
}
}
```
在这个函数中,我们首先检查当前节点是否为空,如果为空,则返回0。然后我们检查当前节点的数据是否等于给定的关键字,如果是,则返回当前层数。否则,我们递归地在左子树或右子树中查找关键字,同时增加层数。
相关问题
用C语言设计一个判别给定二叉树是否为二叉排序树的算法
以下是用C语言设计一个判别给定二叉树是否为二叉排序树的算法:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *lchild, *rchild;
} TreeNode, *Tree;
int pre = -32767; // pre为全局变量,保存当前结点中序前驱的值,初始值为-∞
int IsBST(Tree T) {
int left, right; // 保存左右子树的判断结果
if (T == NULL) // 空树也是二叉排序树,返回1
return 1;
else {
left = IsBST(T->lchild); // 判断左子树是否是二叉排序树
if (left == 0 || pre >= T->data) // 若左子树返回0或前驱大于等于当前结点
return 0; // 则不是二叉排序树,返回0
pre = T->data; // 保存当前结点的值
right = IsBST(T->rchild); // 判断右子树是否是二叉排序树
// 因为执行到这里时,left的值一定为1,如果left为0上面的则if判断为真已经返回0了
// 所以最后直接返回右子树的结果就可以判断给定的二叉树是否是二叉排序树了
return right;
}
}
int main() {
// 构造一颗二叉排序树
Tree T = (Tree)malloc(sizeof(TreeNode));
T->data = 4;
T->lchild = (Tree)malloc(sizeof(TreeNode));
T->lchild->data = 2;
T->lchild->lchild = (Tree)malloc(sizeof(TreeNode));
T->lchild->lchild->data = 1;
T->lchild->lchild->lchild = NULL;
T->lchild->lchild->rchild = NULL;
T->lchild->rchild = (Tree)malloc(sizeof(TreeNode));
T->lchild->rchild->data = 3;
T->lchild->rchild->lchild = NULL;
T->lchild->rchild->rchild = NULL;
T->rchild = (Tree)malloc(sizeof(TreeNode));
T->rchild->data = 6;
T->rchild->lchild = (Tree)malloc(sizeof(TreeNode));
T->rchild->lchild->data = 5;
T->rchild->lchild->lchild = NULL;
T->rchild->lchild->rchild = NULL;
T->rchild->rchild = (Tree)malloc(sizeof(TreeNode));
T->rchild->rchild->data = 7;
T->rchild->rchild->lchild = NULL;
T->rchild->rchild->rchild = NULL;
// 判断是否为二叉排序树
if (IsBST(T))
printf("给定的二叉树是一颗二叉排序树。\n");
else
printf("给定的二叉树不是一颗二叉排序树。\n");
return 0;
}
```
C语言源程序查找算法的实现: 任意输入一组数据作为二叉排序树中结点的键值,创建一棵二叉排序树,然后对给定的值进行查找。
好的,我可以为您解答。以下是C语言源程序查找算法的实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉排序树结点的数据结构
struct TreeNode {
int value;
struct TreeNode* left;
struct TreeNode* right;
};
// 创建新结点
struct TreeNode* createNode(int value) {
struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入结点
struct TreeNode* insertNode(struct TreeNode* root, int value) {
if (root == NULL) {
return createNode(value);
}
if (value < root->value) {
root->left = insertNode(root->left, value);
} else if (value > root->value) {
root->right = insertNode(root->right, value);
}
return root;
}
// 查找结点
struct TreeNode* searchNode(struct TreeNode* root, int value) {
if (root == NULL || root->value == value) {
return root;
}
if (value < root->value) {
return searchNode(root->left, value);
} else {
return searchNode(root->right, value);
}
}
// 中序遍历二叉排序树
void inorderTraversal(struct TreeNode* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->value);
inorderTraversal(root->right);
}
}
int main() {
struct TreeNode* root = NULL;
int n, value, searchValue;
// 读入数据
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &value);
root = insertNode(root, value);
}
// 中序遍历二叉排序树
printf("Inorder traversal of the tree: ");
inorderTraversal(root);
printf("\n");
// 查找给定的值
printf("Enter the value to search: ");
scanf("%d", &searchValue);
struct TreeNode* result = searchNode(root, searchValue);
if (result == NULL) {
printf("%d not found in the tree\n", searchValue);
} else {
printf("%d found in the tree\n", searchValue);
}
return 0;
}
```
该程序中,我们定义了一个 `struct TreeNode` 结构体表示二叉排序树的结点,包括结点的值和左右子结点指针。`createNode()` 函数用于创建新结点,`insertNode()` 函数用于插入结点,`searchNode()` 函数用于查找结点。`inorderTraversal()` 函数用于中序遍历二叉排序树。在 `main()` 函数中,我们首先读入数据并创建二叉排序树,然后进行中序遍历并输出结果。最后,我们读入给定值并在二叉排序树中查找该值,输出查找结果。
希望这个程序可以帮助到您!
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)