用C++实现二叉树遍历(flist)

这里提供一个使用链表实现的二叉树遍历代码：

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

typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

typedef struct Node {
    TreeNode* data;
    struct Node* next;
} Node;

typedef struct {
    Node* head;
    Node* tail;
} Flist;

// 初始化链表
void init_list(Flist* flist) {
    flist->head = NULL;
    flist->tail = NULL;
}

// 在链表尾部插入节点
void append(Flist* flist, TreeNode* data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;

    if (flist->head == NULL) {
        flist->head = new_node;
    } else {
        flist->tail->next = new_node;
    }

    flist->tail = new_node;
}

// 删除链表头部节点
TreeNode* pop(Flist* flist) {
    if (flist->head == NULL) {
        return NULL;
    }

    Node* temp_node = flist->head;
    TreeNode* temp_data = flist->head->data;

    if (flist->head == flist->tail) {
        flist->tail = NULL;
    }

    flist->head = flist->head->next;
    free(temp_node);

    return temp_data;
}

// 前序遍历
void preorder(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    Flist flist;
    init_list(&flist);
    append(&flist, root);

    while (flist.head != NULL) {
        TreeNode* current_node = pop(&flist);
        printf("%d ", current_node->data);

        if (current_node->right != NULL) {
            append(&flist, current_node->right);
        }

        if (current_node->left != NULL) {
            append(&flist, current_node->left);
        }
    }
}

// 中序遍历
void inorder(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    Flist flist;
    init_list(&flist);
    TreeNode* current_node = root;

    while (current_node != NULL || flist.head != NULL) {
        if (current_node != NULL) {
            append(&flist, current_node);
            current_node = current_node->left;
        } else {
            current_node = pop(&flist);
            printf("%d ", current_node->data);
            current_node = current_node->right;
        }
    }
}

// 后序遍历
void postorder(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    Flist flist;
    init_list(&flist);
    TreeNode* current_node = root;
    TreeNode* last_visited_node = NULL;

    while (current_node != NULL || flist.head != NULL) {
        if (current_node != NULL) {
            append(&flist, current_node);
            current_node = current_node->left;
        } else {
            TreeNode* temp_node = flist.head->data;

            if (temp_node->right != NULL && temp_node->right != last_visited_node) {
                current_node = temp_node->right;
            } else {
                printf("%d ", temp_node->data);
                last_visited_node = pop(&flist);
            }
        }
    }
}

// 创建新节点
TreeNode* new_node(int data) {
    TreeNode* new_node = (TreeNode*)malloc(sizeof(TreeNode));
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

int main() {
    // 创建二叉树
    TreeNode* root = new_node(1);
    root->left = new_node(2);
    root->right = new_node(3);
    root->left->left = new_node(4);
    root->left->right = new_node(5);
    root->right->left = new_node(6);
    root->right->right = new_node(7);

    // 遍历二叉树
    printf("前序遍历：");
    preorder(root);
    printf("\n");

    printf("中序遍历：");
    inorder(root);
    printf("\n");

    printf("后序遍历：");
    postorder(root);
    printf("\n");

    return 0;
}

该代码使用了一个自定义的链表结构体`Flist`，其中的`init_list`、`append`和`pop`函数分别用于初始化链表、在链表尾部插入节点和删除链表头部节点。在遍历过程中，需要用到一个链表来存储待处理的节点。对于前序遍历，从根节点开始，先输出当前节点的值，然后将其右子节点和左子节点分别加入链表中，这样在下一次循环时就会先处理左子节点。对于中序遍历，从根节点开始，先将其和其所有左子节点加入链表中，然后依次弹出链表头部节点，输出其值，并将其右子节点加入链表中。对于后序遍历，从根节点开始，先将其和其所有左子节点加入链表中，然后依次弹出链表头部节点，如果该节点的右子节点存在且未被处理过，则将其右子节点加入链表中，否则输出该节点的值并将其标记为已处理。