为什么下面这段代码创建的二叉数和中序线索二叉树,把它们中序遍历后的结果不同啊。代码在下面。大佬帮帮我吧,卡在这里好久了代码在下面。
#include <stdlib.h>
#include <stdio.h>
typedef struct BiTNode {
int data;
struct BiTNode* lchild, * rchild;
int ltag, rtag;
} BiTNode, * BiTree;
BiTree q = NULL;
BiTree pre = NULL;
void CreatBiT(BiTree T, BiTree M, BiTree N) {
if (T != NULL) {
T->lchild = M;
T->rchild = N;
}
}
void visit(BiTree T) {
if (T->lchild == NULL) {
T->lchild = pre;
T->ltag = 1;
}
if (pre != NULL && pre->rchild == NULL) {
pre->rchild = T;
pre->rtag = 1;
}
pre = T;
}
void InThread(BiTree T) {
if (T == NULL) return; // 防止空指针解引用
InThread(T->lchild);
visit(T);
InThread(T->rchild);
}
void CreateInThread(BiTree T) {
if (T != NULL) {
InThread(T);
if (pre->rchild == NULL) {
pre->rtag = 1;
}
}
}
//中序线索二叉树的以T为根的子树第一个被访问的结点;
BiTNode *FirstNode(BiTree T) {
/* 目的错误
if (T == NULL || T->lchild == NULL) {
return NULL;
}
BiTree K = T->rchild;
while (K != NULL && K->ltag == 0) {
K = K->lchild;
}
return K;*/
while(T->ltag==0){
T=T->lchild;
}
return T;
}
//中序线索二叉树中找到结点p的后继结点
BiTNode* NextNode(BiTree T) {
/* if (T->rtag == 1) {
return T->rchild;
} else {
return FirstNode(T); // 确保函数名称一致
}*/
if(T->rtag==0){
return FirstNode(T->rchild);
} else{
return T->rchild;
}
}
void FreeTree(BiTree T) {
if (T != NULL) {
FreeTree(T->lchild);
FreeTree(T->rchild);
free(T);
}
}
visit3(BiTree T){
printf("%da ",T->data);
}
void InOrder4(BiTNode *T){
BiTNode* p;
for(p=FirstNode(T);p!=NULL;p=NextNode(p))
visit3(p);
}
void InOrder3(BiTree T){
if(T!=NULL){
InOrder3(T->lchild);
visit3(T);
InOrder3(T->rchild);
}
}
int main() {
int i;
BiTree T, J;
pre = NULL; // 确保 pre 初始化
T = (BiTree)malloc(sizeof(BiTNode));
T->data = 0; // 根节点
T->lchild = T->rchild = NULL; // 初始化根节点的子节点
J = T; // 保存根节点的指针
for (i = 1; i <= 4; ++i) {
BiTree M = (BiTree)malloc(sizeof(BiTNode));
BiTree N = (BiTree)malloc(sizeof(BiTNode));
M->data = i;
M->lchild = NULL;
M->rchild = NULL;
N->data = i + 2;
N->lchild = NULL;
N->rchild = NULL;
// 连接 M 和 N 到当前节点 T
CreatBiT(T, M, N);
// 更新 T 指向下一个节点,保持树结构完整
T = M; // 这里需要确保逻辑上是正确的
}
printf("二叉树的中序遍历 ;");
InOrder3(J);
CreateInThread(J); // 确保传递的是根节点进行线索化
printf("\n中序线索二叉树的中序遍历;");
InOrder4(J);
// InOrder3(J);
// 释放分配的内存
// FreeTree(J);
return 0;
}
#include <stdlib.h>
#include <stdio.h>
typedef struct BiTNode {
int data;
struct BiTNode* lchild, * rchild;
int ltag, rtag;
} BiTNode, * BiTree;
BiTree q = NULL;
BiTree pre = NULL;
void CreatBiT(BiTree T, BiTree M, BiTree N) {
if (T != NULL) {
T->lchild = M;
T->rchild = N;
}
}
void visit(BiTree T) {
if (T->lchild == NULL) {
T->lchild = pre;
T->ltag = 1;
}
if (pre != NULL && pre->rchild == NULL) {
pre->rchild = T;
pre->rtag = 1;
}
pre = T;
}
void InThread(BiTree T) {
if (T == NULL) return; // 防止空指针解引用
InThread(T->lchild);
visit(T);
InThread(T->rchild);
}
void CreateInThread(BiTree T) {
if (T != NULL) {
InThread(T);
if (pre->rchild == NULL) {
pre->rtag = 1;
}
}
}
//中序线索二叉树的以T为根的子树第一个被访问的结点;
BiTNode *FirstNode(BiTree T) {
/* 目的错误
if (T == NULL || T->lchild == NULL) {
return NULL;
}
BiTree K = T->rchild;
while (K != NULL && K->ltag == 0) {
K = K->lchild;
}
return K;*/
while(T->ltag==0){
T=T->lchild;
}
return T;
}
//中序线索二叉树中找到结点p的后继结点
BiTNode* NextNode(BiTree T) {
/* if (T->rtag == 1) {
return T->rchild;
} else {
return FirstNode(T); // 确保函数名称一致
}*/
if(T->rtag==0){
return FirstNode(T->rchild);
} else{
return T->rchild;
}
}
void FreeTree(BiTree T) {
if (T != NULL) {
FreeTree(T->lchild);
FreeTree(T->rchild);
free(T);
}
}
visit3(BiTree T){
printf("%da ",T->data);
}
void InOrder4(BiTNode *T){
BiTNode* p;
for(p=FirstNode(T);p!=NULL;p=NextNode(p))
visit3(p);
}
void InOrder3(BiTree T){
if(T!=NULL){
InOrder3(T->lchild);
visit3(T);
InOrder3(T->rchild);
}
}
int main() {
int i;
BiTree T, J;
pre = NULL; // 确保 pre 初始化
T = (BiTree)malloc(sizeof(BiTNode));
T->data = 0; // 根节点
T->lchild = T->rchild = NULL; // 初始化根节点的子节点
J = T; // 保存根节点的指针
for (i = 1; i <= 4; ++i) {
BiTree M = (BiTree)malloc(sizeof(BiTNode));
BiTree N = (BiTree)malloc(sizeof(BiTNode));
M->data = i;
M->lchild = NULL;
M->rchild = NULL;
N->data = i + 2;
N->lchild = NULL;
N->rchild = NULL;
// 连接 M 和 N 到当前节点 T
CreatBiT(T, M, N);
// 更新 T 指向下一个节点,保持树结构完整
T = M; // 这里需要确保逻辑上是正确的
}
printf("二叉树的中序遍历 ;");
InOrder3(J);
CreateInThread(J); // 确保传递的是根节点进行线索化
printf("\n中序线索二叉树的中序遍历;");
InOrder4(J);
// InOrder3(J);
// 释放分配的内存
// FreeTree(J);
return 0;
}