用c语言实现 1.先序遍历创建二叉树; 2.中序线索化二叉树; 3.分别通过 找前驱 和 找后继 的方式,遍历中序线索二叉树。
时间: 2024-02-11 08:09:51 浏览: 31
好的,以下是用C语言实现的代码:
```c
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
// 定义二叉树节点的结构体
struct TreeNode {
char data; // 数据域
struct TreeNode* leftChild; // 左孩子指针
struct TreeNode* rightChild; // 右孩子指针
bool leftTag; // 左线索标志
bool rightTag; // 右线索标志
};
// 先序遍历创建二叉树
struct TreeNode* createBinaryTree() {
char c;
scanf("%c", &c);
getchar(); // 读取输入字符后需要跳过回车符
if (c == '#') { // 如果输入#,表示该节点为空指针
return NULL;
}
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); // 创建根节点
root->data = c;
root->leftChild = createBinaryTree(); // 递归创建左子树
root->rightChild = createBinaryTree(); // 递归创建右子树
return root;
}
// 中序线索化二叉树
void inOrderThreading(struct TreeNode* root, struct TreeNode** pre) {
if (root == NULL) { // 如果是空树,直接返回
return;
}
inOrderThreading(root->leftChild, pre); // 递归线索化左子树
if (root->leftChild == NULL) { // 如果左孩子为空,将左孩子指针指向前驱节点
root->leftChild = *pre;
root->leftTag = true;
}
if (*pre != NULL && (*pre)->rightChild == NULL) { // 如果前驱节点的右孩子为空,将前驱节点的右孩子指针指向当前节点
(*pre)->rightChild = root;
(*pre)->rightTag = true;
}
*pre = root; // 更新前驱节点
inOrderThreading(root->rightChild, pre); // 递归线索化右子树
}
// 获取中序线索二叉树的第一个节点
struct TreeNode* firstNode(struct TreeNode* root) {
while (root->leftTag == false) {
root = root->leftChild;
}
return root;
}
// 获取中序线索二叉树中节点的后继节点
struct TreeNode* nextNode(struct TreeNode* root) {
if (root->rightTag == false) { // 如果右线索标志为false,表示有右孩子
return firstNode(root->rightChild);
}
else { // 如果右线索标志为true,表示没有右孩子,返回右线索指向的后继节点
return root->rightChild;
}
}
// 通过找前驱的方式遍历中序线索二叉树
void inOrderTraverseByPredecessor(struct TreeNode* root) {
while (root != NULL) {
while (root->leftTag == false) { // 如果左线索标志为false,说明有左孩子,继续向左走
root = root->leftChild;
}
printf("%c ", root->data); // 输出当前节点
root = root->leftChild; // 向左孩子继续遍历
}
printf("\n");
}
// 通过找后继的方式遍历中序线索二叉树
void inOrderTraverseBySuccessor(struct TreeNode* root) {
struct TreeNode* p = firstNode(root); // 获取第一个节点
while (p != NULL) {
printf("%c ", p->data); // 输出当前节点
p = nextNode(p); // 获取当前节点的后继节点
}
printf("\n");
}
int main() {
struct TreeNode* root = createBinaryTree(); // 创建二叉树
struct TreeNode* pre = NULL;
inOrderThreading(root, &pre); // 中序线索化二叉树
printf("通过找前驱的方式遍历中序线索二叉树:");
inOrderTraverseByPredecessor(root); // 通过找前驱的方式遍历中序线索二叉树
printf("通过找后继的方式遍历中序线索二叉树:");
inOrderTraverseBySuccessor(root); // 通过找后继的方式遍历中序线索二叉树
return 0;
}
```
以上代码中,`createBinaryTree`函数用于创建二叉树,`inOrderThreading`函数用于中序线索化二叉树,`firstNode`函数用于获取中序线索二叉树的第一个节点,`nextNode`函数用于获取中序线索二叉树中节点的后继节点,`inOrderTraverseByPredecessor`函数用于通过找前驱的方式遍历中序线索二叉树,`inOrderTraverseBySuccessor`函数用于通过找后继的方式遍历中序线索二叉树。