储存字符串的二叉树的定义、建立、遍历函数(先中后)和释放操作函数
时间: 2024-02-24 14:53:16 浏览: 23
储存字符串的二叉树是一种数据结构,每个节点存储一个字符,每个节点最多有两个子节点,左子节点存储比该节点小的字符,右子节点存储比该节点大的字符。
定义:
```
struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
};
```
建立:
```
struct TreeNode* createTree(char* str, int start, int end) {
if (start > end) return NULL;
int mid = (start + end) / 2;
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = str[mid];
root->left = createTree(str, start, mid - 1);
root->right = createTree(str, mid + 1, end);
return root;
}
```
遍历:
```
//先序遍历
void preorderTraversal(struct TreeNode* root) {
if (root == NULL) return;
printf("%c", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
//中序遍历
void inorderTraversal(struct TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%c", root->val);
inorderTraversal(root->right);
}
//后序遍历
void postorderTraversal(struct TreeNode* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c", root->val);
}
```
释放:
```
void releaseTree(struct TreeNode* root) {
if (root == NULL) return;
releaseTree(root->left);
releaseTree(root->right);
free(root);
}
```
注意,在释放函数中需要递归地释放左右子树。