线索二叉树输出有问题

Question

这个代码输出有问题，但是我问了很多同学也找不出来
这是输出结果
Pre-order Traversal: 1 2 4 5 3 6 7
In-order Traversal: 4 2 5 1 6 3 7
Post-order Traversal: 5
后序的只有一个数字

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *left, *right;
    int isThreaded;
} Node;

Node *newNode(int data) {
    Node *temp = (Node *)malloc(sizeof(Node));
    temp->data = data;
    temp->left = temp->right = NULL;
    temp->isThreaded = 0;
    return temp;
}

void inOrderTraversal(Node *root) {
    if (!root) return;

    Node *current = root;
    while (current) {
        if (!current->left) {
            printf("%d ", current->data);
            current = current->right;
        } else {
            Node *pre = current->left;
            while (pre->right && pre->right != current) {
                pre = pre->right;
            }

            if (!pre->right) {
                pre->right = current;
                current = current->left;
            } else {
                pre->right = NULL;
                printf("%d ", current->data);
                current = current->right;
            }
        }
    }
}

void preOrderTraversal(Node *root) {
    if (!root) return;

    Node *current = root;
    while (current) {
        if (!current->left) {
            printf("%d ", current->data);
            current = current->right;
        } else {
            Node *pre = current->left;
            while (pre->right && pre->right != current) {
                pre = pre->right;
            }

            if (!pre->right) {
                printf("%d ", current->data);
                pre->right = current;
                current = current->left;
            } else {
                pre->right = NULL;
                current = current->right;
            }
        }
    }
}

void postOrderTraversal(Node* root) {
    if (!root) return;

    Node* dummy = newNode(-1);
    dummy->left = root;

    Node* current = dummy;
    while (current) {
        if (!current->left) {
            current = current->right;
        }
        else {
            Node* pre = current->left;
            while (pre->right && pre->right != current) {
                pre = pre->right;
            }

            if (!pre->right) {
                pre->right = current;
                current = current->left;
            }
            else {
                // Reverse the nodes from current->left to pre
                Node* first = current->left;
                Node* middle = first->right;
                Node* last;
                while (middle != current) {
                    last = middle->right;
                    middle->right = first;
                    middle->isThreaded = 1; // set the isThreaded flag to 1
                    first = middle;
                    middle = last;
                }

                // Print the reversed nodes
                first = pre;
                while (first != current->left) {
                    printf("%d ", first->data);
                    first = first->right;
                }

                // Re-reverse the nodes to restore the tree
                first = current->left;
                middle = first->right;
                while (middle != current) {
                    last = middle->right;
                    middle->right = first;
                    middle->isThreaded = 0; // set the isThreaded flag to 0
                    first = middle;
                    middle = last;
                }

                pre->right = NULL;
                current = current->right;
            }
        }
    }

    free(dummy);
}

int main() {
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);

    printf("Pre-order Traversal: ");
    preOrderTraversal(root);
    printf("\nIn-order Traversal: ");
    inOrderTraversal(root);
    printf("\nPost-order Traversal: ");
    postOrderTraversal(root);
    printf("\n");

    return 0;
}

Answer 1

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7406205
• 这篇博客你也可以参考下：设班级每位同学有三门课程的考试成绩， 采用二维数组编程实现从键盘输入每个同学的成绩，并计算其平均成绩后输出
• 除此之外, 这篇博客: 键盘输入一个字符串，编写代码获取字符串的长度并输出，要求使用字符指针实现。中的 问题描述 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• ---

• 您还可以看一下 纪佳琪老师的机器学习之线性回归理论与代码实践课程中的 数据归一化，画直线图，画损失函数图小节, 巩固相关知识点