C语言编写中序遍历线索二叉树
时间: 2023-03-10 14:01:18 浏览: 97
我可以给你提供一个示例代码: void inOrder(struct node *root)
{
if (root != NULL)
{
inOrder(root->left);
printf("%d \n", root->data);
inOrder(root->right);
}
}
相关问题
c语言使用编写二叉树中序遍历线索化
好的,下面是使用C语言编写的二叉树中序遍历线索化的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
int ltag;
int rtag;
} TreeNode;
// 创建二叉树
TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) {
return NULL;
}
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = createTree();
node->right = createTree();
node->ltag = 0;
node->rtag = 0;
return node;
}
// 中序遍历线索化
void inOrderThread(TreeNode *p, TreeNode **prev) {
if (p != NULL) {
inOrderThread(p->left, prev);
if (p->left == NULL) {
p->left = *prev;
p->ltag = 1;
}
if (*prev != NULL && (*prev)->right == NULL) {
(*prev)->right = p;
(*prev)->rtag = 1;
}
*prev = p;
inOrderThread(p->right, prev);
}
}
// 中序遍历线索化后的遍历操作
void inOrderThreadTraverse(TreeNode *root) {
TreeNode *p = root->left;
while (p != root) {
while (p->ltag == 1) {
p = p->left;
}
printf("%d ", p->val);
while (p->rtag == 0) {
p = p->right;
if (p == root) {
return;
}
printf("%d ", p->val);
}
p = p->right;
}
}
int main() {
TreeNode *root = createTree();
TreeNode *prev = NULL;
inOrderThread(root, &prev);
inOrderThreadTraverse(root);
return 0;
}
```
在这个示例代码中,我们通过定义一个二叉树结构体来表示二叉树节点,其中 `ltag` 和 `rtag` 分别表示左右指针是否为线索指针。然后我们通过 `createTree()` 函数来创建一棵二叉树,通过 `inOrderThread()` 函数来对二叉树进行中序遍历线索化,最后通过 `inOrderThreadTraverse()` 函数来输出中序遍历线索化后的结果。
用C语言写出中序线索化二叉树的遍历代码
当然,我很乐意回答您的问题。以下是用C语言编写中序线索化二叉树的遍历代码:
```
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100
/*定义线索二叉树节点*/
typedef struct ThreadNode {
int data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag; //左标记与右标记
}ThreadNode, *ThreadTree;
/*全局变量存放线序链表*/
ThreadNode *pre = NULL;
/*初始化空线索二叉树*/
void InitThreadTree(ThreadTree &T) {
T = (ThreadNode *)malloc(sizeof(ThreadNode));
T->lchild = T->rchild = T;
T->ltag = T->rtag = 0;
}
/*通过中序遍历建立二叉树*/
void CreateInThreadTree(ThreadTree T) {
char ch;
scanf("%c", &ch);
if (ch == '#') {
T = NULL;
} else {
T = (ThreadNode *)malloc(sizeof(ThreadNode));
T->data = ch;
CreateInThreadTree(T->lchild);
if (T->lchild) {
T->ltag = 0;
} else {
T->ltag = 1;
}
CreateInThreadTree(T->rchild);
if (T->rchild) {
T->rtag = 0;
} else {
T->rtag = 1;
}
}
}
/*中序遍历线索化*/
void InThread(ThreadNode *p) {
if (p != NULL) {
InThread(p->lchild);
if (p->lchild == NULL) {
p->ltag = 1;
p->lchild = pre;
}
if (pre != NULL && pre->rchild == NULL) {
pre->rtag = 1;
pre->rchild = p;
}
pre = p;
InThread(p->rchild);
}
}
/*中序遍历线索二叉树*/
void InOrder(ThreadTree T) {
ThreadNode *p = T->lchild; //p指向根节点,也是第一个节点
while (p != T) {
while (p->ltag == 0) {
p = p->lchild;
}
printf("%c", p->data);
while (p->rtag == 1 && p->rchild !=T) {//向右线索遍历
p = p->rchild;
printf("%c", p->data);
}
p = p->rchild; //p指向右子树根节点
}
}
/*主函数*/
int main() {
ThreadTree T;
InitThreadTree(T);
printf("请输入中序序列,字母表示节点,#表示空节点:\n");
CreateInThreadTree(T);
InThread(T->lchild); //线索化中序遍历
printf("生成的中序线索二叉树中序序列为:\n");
InOrder(T); //输出中序序列
return 0;
}
```
希望我的回答能够帮到您,如果您还有其他问题,欢迎随时向我提问。