通过一个先序遍历的结果建立一颗二叉树,并求树中指定节点的左孩子,右孩子(如果存在),用C语言编写
时间: 2024-12-13 19:26:48 浏览: 4
在C语言中,我们可以通过递归的方式从给定的先序遍历结果来构建一颗二叉树,然后通过已有的节点指针找到指定节点的左右子节点。这里是一个简单的步骤描述和示例代码:
1. 首先,定义二叉树节点结构:
```c
struct TreeNode {
int val; // 节点值
struct TreeNode* left; // 左子节点指针
struct TreeNode* right; // 右子节点指针
};
```
2. 定义辅助函数用于构建树:
```c
struct TreeNode* buildTree(int* preorder, int start, int end) {
if (start > end) return NULL;
// 先序遍历的第一项是根节点
struct TreeNode* root = malloc(sizeof(struct TreeNode));
root->val = preorder[start];
// 找到右子节点的起始位置
int inorderStart = start + 1;
for (int i = inorderStart; i <= end && preorder[i] != root->val; ++i) {}
// 递归构建左右子树
root->left = buildTree(preorder, inorderStart, i - 1);
root->right = buildTree(preorder, i, end);
return root;
}
```
3. 检索指定节点及子节点:
```c
struct TreeNode* findNode(struct TreeNode* root, int target) {
if (!root || root->val == target) return root;
if (root->val < target) {
return findNode(root->right, target); // 向右子树搜索
} else {
return findNode(root->left, target); // 向左子树搜索
}
}
// 获取指定节点的左、右子节点(如果存在)
int getLeftChild(struct TreeNode* node, int target) {
struct TreeNode* foundNode = findNode(node, target);
return foundNode ? foundNode->left->val : -1; // -1表示不存在
}
int getRightChild(struct TreeNode* node, int target) {
struct TreeNode* foundNode = findNode(node, target);
return foundNode ? foundNode->right->val : -1; // -1表示不存在
}
```
要使用这个功能,你需要先调用`buildTree`函数创建二叉树,然后调用`getLeftChild`和`getRightChild`来查找目标节点的子节点。
阅读全文