用c语言编写前序、后序二叉树线索化代码
时间: 2024-10-14 18:10:14 浏览: 1
在C语言中,线索化(Threaded Binary Tree)是一种将二叉树节点附加额外的信息(称为线索),以便在遍历时无需访问前驱或后继节点,提高查找效率。这里给出一个简单的例子,展示如何实现前序和后序线索化的代码:
**前序线索化(Preorder Traversal with Threaded Node):**
```c
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
struct TreeNode **pre; // 指向前驱节点线索
} TreeNode;
void insertPreOrder(TreeNode **root, int val) {
if (*root == NULL) {
*root = (TreeNode *)malloc(sizeof(TreeNode));
(*root)->val = val;
(*root)->pre = &(*root)->left;
} else {
TreeNode *temp = *root;
while (temp->left != NULL || temp->right != NULL) {
if (temp->val > val) {
if (temp->left == NULL) {
temp->left = (TreeNode *)malloc(sizeof(TreeNode));
temp->left->val = val;
temp->left->pre = &temp->left->right;
} else {
temp = temp->left;
}
} else {
if (temp->right == NULL) {
temp->right = (TreeNode *)malloc(sizeof(TreeNode));
temp->right->val = val;
temp->right->pre = &temp->right->left;
} else {
temp = temp->right;
}
}
}
}
}
// 示例遍历
void preOrderTraversal(TreeNode *root) {
if (root != NULL) {
printf("%d -> ", root->val);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
```
**后序线索化(Postorder Traversal with Threaded Node):**
```c
void insertPostOrder(TreeNode **root, int val) {
if (*root == NULL) {
*root = (TreeNode *)malloc(sizeof(TreeNode));
(*root)->val = val;
(*root)->pre = NULL;
} else {
insertPostOrder(&((*root)->left), val);
insertPostOrder(&((*root)->right), val);
if ((*root)->left != NULL) {
(*root)->left->pre = root;
}
if ((*root)->right != NULL) {
(*root)->right->pre = root;
}
}
}
// 示例遍历
void postOrderTraversal(TreeNode *root) {
TreeNode *prev = NULL;
while (root != NULL) {
if (root->pre != NULL && root->pre != prev) {
root = root->pre;
} else {
printf("%d -> ", root->val);
prev = root;
root = root->left ? root->left : root->right;
}
}
}
```