假设二叉树采用二叉链存储结构,设计一个算法Level()求二叉树b中值为x的结点的层次(假设所有结点值唯一)给出C语言代码
时间: 2024-05-16 21:17:33 浏览: 151
以下是求二叉树中值为x的结点的层次的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
int Level(TreeNode* root, int x) {
if (root == NULL) {
return -1; // 如果根节点为空,则返回-1
}
if (root->val == x) {
return 0; // 如果根节点就是要找的节点,则返回0
}
int left_level = Level(root->left, x); // 在左子树中查找
int right_level = Level(root->right, x); // 在右子树中查找
if (left_level != -1) {
return left_level + 1; // 如果在左子树中找到了,则返回左子树中的层次加1
} else if (right_level != -1) {
return right_level + 1; // 如果在右子树中找到了,则返回右子树中的层次加1
} else {
return -1; // 如果左右子树中都没有找到,则返回-1
}
}
int main() {
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = NULL;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 4;
root->right->right->left = NULL;
root->right->right->right = NULL;
int x = 4;
int level = Level(root, x);
printf("The level of node with value %d is: %d\n", x, level);
free(root->left);
free(root->right->right);
free(root->right);
free(root);
return 0;
}
```
上述代码中,我们先定义了一个二叉树的结构体TreeNode,包含一个值域和左右子节点指针。然后,我们定义了一个Level()函数,用于求二叉树中值为x的节点的层次。在该函数中,我们首先判断当前节点是否为空或是否为要查找的节点,如果是,则返回相应的层次;否则,在左右子树中查找,如果在左子树中找到,则返回左子树中的层次加1,如果在右子树中找到,则返回右子树中的层次加1,否则返回-1。最后,我们编写了一个main()函数用于测试Level()函数的正确性。
阅读全文