用C语言,用先序遍历创建一个二叉树,用0表示空指针,并查找某个节点的父节点
时间: 2024-12-18 08:34:37 浏览: 3
树子系统实现二叉树的创建,先序遍历,中序遍历,后序遍历,求叶子数,求结点数,求树的深度
在C语言中,我们可以通过定义一个二叉树节点的结构体来创建二叉树。每个节点包含数据部分和指向左右子树的指针。使用先序遍历的方式创建二叉树时,我们可以按照根节点、左子树、右子树的顺序输入节点值,并用0表示空指针。
下面是一个简单的示例代码,展示如何用C语言创建一个二叉树,并查找某个节点的父节点:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建二叉树
TreeNode* createBinaryTree() {
int value;
scanf("%d", &value);
if (value == 0) {
return NULL;
}
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->data = value;
node->left = createBinaryTree();
node->right = createBinaryTree();
return node;
}
// 查找父节点
TreeNode* findParent(TreeNode *root, int target) {
if (root == NULL || root->left == NULL && root->right == NULL) {
return NULL;
}
if ((root->left != NULL && root->left->data == target) || (root->right != NULL && root->right->data == target)) {
return root;
}
TreeNode *leftSearch = findParent(root->left, target);
if (leftSearch != NULL) {
return leftSearch;
}
return findParent(root->right, target);
}
int main() {
printf("Enter nodes in preorder (use 0 for NULL):\n");
TreeNode *root = createBinaryTree();
int target;
printf("Enter the value of the node to find its parent: ");
scanf("%d", &target);
TreeNode *parent = findParent(root, target);
if (parent != NULL) {
printf("The parent of node %d is %d.\n", target, parent->data);
} else {
printf("No parent found or node does not exist.\n");
}
return 0;
}
```
在这个程序中,`createBinaryTree`函数通过递归方式读取输入来构建二叉树。当输入为0时,返回NULL表示该位置没有节点。`findParent`函数用于查找指定节点的父节点。如果找到目标节点,则返回其父节点;否则继续在左右子树中搜索。
用户需要按照先序遍历的顺序输入节点值,并在最后输入要查找父节点的目标值。程序将输出目标节点的父节点的值或者相应的提示信息。
阅读全文