C语言实现二叉树多操作：构建、遍历、求高、查祖先及内存管理

```c #include <stdio.h> #include <stdlib.h> // 二叉树的节点结构体 typedef struct TreeNode { char data; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 创建新节点 TreeNode* createNode(char data) { TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; } // 根据扩充先序序列构建二叉树 TreeNode* buildTree(char* preorder, int* index) { char data = preorder[*index]; (*index)++; if (data == '#') { return NULL; } TreeNode* root = createNode(data); root->left = buildTree(preorder, index); root->right = buildTree(preorder, index); return root; } // 中序遍历 void inorderTraversal(TreeNode* root) { if (root!= NULL) { inorderTraversal(root->left); printf("%c ", root->data); inorderTraversal(root->right); } } // 后序遍历 void postorderTraversal(TreeNode* root) { if (root!= NULL) { postorderTraversal(root->left); postorderTraversal(root->right); printf("%c ", root->data); } } // 计算节点高度 int height(TreeNode* root) { if (root == NULL) { return 0; } int leftHeight = height(root->left); int rightHeight = height(root->right); return (leftHeight > rightHeight? leftHeight : rightHeight) + 1; } // 打印节点高度 void printHeights(TreeNode* root) { if (root!= NULL) { int h = height(root); printf("%c 的高度为: %d\n", root->data, h); printHeights(root->left); printHeights(root->right); } } // 查找节点的祖先 void findAncestors(TreeNode* root, char target, TreeNode* ancestors[]) { if (root == NULL) { return; } if (root->data == target) { int i = 0; while (ancestors[i]!= NULL) { printf("%c ", ancestors[i]->data); i++; } return; } ancestors[0] = root; findAncestors(root->left, target, ancestors + 1); findAncestors(root->right, target, ancestors + 1); } // 释放二叉树内存 void clearTree(TreeNode* root) { if (root!= NULL) { clearTree(root->left); clearTree(root->right); free(root); } } int main() { TreeNode* root = NULL; int choice; char preorder[100]; int index = 0; do { printf("1—create tree\n2—inorder\n3—postorder\n4—high\n5—ancent\n6—clear tree\n7—exit\n"); scanf("%d", &choice); switch (choice) { case 1: printf("请输入二叉树的扩充先序序列: "); scanf("%s", preorder); root = buildTree(preorder, &index); break; case 2: printf("中序序列: "); inorderTraversal(root); printf("\n"); break; case 3: printf("后序序列: "); postorderTraversal(root); printf("\n"); break; case 4: printf("各节点高度: \n"); printHeights(root); printf("\n"); break; case 5: printf("请输入要查找祖先的节点: "); char target; scanf(" %c", &target); TreeNode* ancestors[100] = {NULL}; findAncestors(root, target, ancestors); printf("\n"); break; case 6: clearTree(root); root = NULL; break; } } while (choice!= 7); return 0; } ``` 1. 输入的扩充先序序列格式要正确，特殊字符代表空节点要统一。 2. 释放内存时要确保递归释放所有节点，避免内存泄漏。 3. 处理用户输入时要进行适当的错误检查和处理。 ######[AI写代码神器 | 1114点数解答 | 2024-12-21 16:32:51]