树遍历算法：递归与迭代的优雅实现

算法原理

树遍历是指按某种规则访问树中所有节点，且每个节点仅被访问一次的过程。树遍历是树形数据结构操作的基础，广泛应用于表达式求值、语法分析、文件系统遍历等领域。

基本遍历方式

1. 前序遍历：根 → 左子树 → 右子树
2. 中序遍历：左子树 → 根 → 右子树
3. 后序遍历：左子树 → 右子树 → 根
4. 层序遍历：按层次从上到下，从左到右

实现方式

1. 递归实现：利用函数调用栈
2. 迭代实现：使用显式栈或队列
3. Morris遍历：O(1)空间复杂度的方法

优缺点分析

递归实现

优点：

• 代码简洁优雅
• 思路清晰直观
• 容易理解和实现

缺点：

• 可能栈溢出
• 空间复杂度O(h)
• 性能开销较大

迭代实现

优点：

• 避免栈溢出风险
• 空间使用可控
• 性能通常更好

缺点：

• 代码相对复杂
• 需要手动管理栈

C语言实现

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

// 二叉树节点定义
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 栈结构（用于迭代实现）
typedef struct StackNode {
    TreeNode* tree_node;
    struct StackNode* next;
} StackNode;

typedef struct Stack {
    StackNode* top;
    int size;
} Stack;

// 队列结构（用于层序遍历）
typedef struct QueueNode {
    TreeNode* tree_node;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
    int size;
} Queue;

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

// 栈操作
Stack* create_stack() {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->top = NULL;
    stack->size = 0;
    return stack;
}

void push(Stack* stack, TreeNode* node) {
    StackNode* stack_node = (StackNode*)malloc(sizeof(StackNode));
    stack_node->tree_node = node;
    stack_node->next = stack->top;
    stack->top = stack_node;
    stack->size++;
}

TreeNode* pop(Stack* stack) {
    if (stack->top == NULL) return NULL;
    
    StackNode* temp = stack->top;
    TreeNode* result = temp->tree_node;
    stack->top = stack->top->next;
    stack->size--;
    free(temp);
    return result;
}

bool is_stack_empty(Stack* stack) {
    return stack->top == NULL;
}

TreeNode* peek(Stack* stack) {
    return stack->top ? stack->top->tree_node : NULL;
}

// 队列操作
Queue* create_queue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
    return queue;
}

void enqueue(Queue* queue, TreeNode* node) {
    QueueNode* queue_node = (QueueNode*)malloc(sizeof(QueueNode));
    queue_node->tree_node = node;
    queue_node->next = NULL;
    
    if (queue->rear == NULL) {
        queue->front = queue->rear = queue_node;
    } else {
        queue->rear->next = queue_node;
        queue->rear = queue_node;
    }
    queue->size++;
}

TreeNode* dequeue(Queue* queue) {
    if (queue->front == NULL) return NULL;
    
    QueueNode* temp = queue->front;
    TreeNode* result = temp->tree_node;
    queue->front = queue->front->next;
    
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    
    queue->size--;
    free(temp);
    return result;
}

bool is_queue_empty(Queue* queue) {
    return queue->front == NULL;
}

/**
 * 前序遍历实现
 */

// 递归前序遍历
void preorder_recursive(TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder_recursive(root->left);
        preorder_recursive(root->right);
    }
}

// 迭代前序遍历
void preorder_iterative(TreeNode* root) {
    if (root == NULL) return;
    
    Stack* stack = create_stack();
    push(stack, root);
    
    while (!is_stack_empty(stack)) {
        TreeNode* current = pop(stack);
        printf("%d ", current->data);
        
        // 先压入右子树，再压入左子树（栈的特性）
        if (current->right != NULL) {
            push(stack, current->right);
        }
        if (current->left != NULL) {
            push(stack, current->left);
        }
    }
    
    free(stack);
}

// Morris前序遍历（O(1)空间）
void preorder_morris(TreeNode* root) {
    TreeNode* current = root;
    
    while (current != NULL) {
        if (current->left == NULL) {
            printf("%d ", current->data);
            current = current->right;
        } else {
            // 找到中序前驱
            TreeNode* predecessor = current->left;
            while (predecessor->right != NULL && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            
            if (predecessor->right == NULL) {
                // 建立线索
                predecessor->right = current;
                printf("%d ", current->data);
                current = current->left;
            } else {
                // 删除线索
                predecessor->right = NULL;
                current = current->right;
            }
        }
    }
}

/**
 * 中序遍历实现
 */

// 递归中序遍历
void inorder_recursive(TreeNode* root) {
    if (root != NULL) {
        inorder_recursive(root->left);
        printf("%d ", root->data);
        inorder_recursive(root->right);
    }
}

// 迭代中序遍历
void inorder_iterative(TreeNode* root) {
    Stack* stack = create_stack();
    TreeNode* current = root;
    
    while (current != NULL || !is_stack_empty(stack)) {
        // 一直向左走到底
        while (current != NULL) {
            push(stack, current);
            current = current->left;
        }
        
        // 处理栈顶元素
        current = pop(stack);
        printf("%d ", current->data);
        
        // 转向右子树
        current = current->right;
    }
    
    free(stack);
}

// Morris中序遍历
void inorder_morris(TreeNode* root) {
    TreeNode* current = root;
    
    while (current != NULL) {
        if (current->left == NULL) {
            printf("%d ", current->data);
            current = current->right;
        } else {
            // 找到中序前驱
            TreeNode* predecessor = current->left;
            while (predecessor->right != NULL && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            
            if (predecessor->right == NULL) {
                // 建立线索
                predecessor->right = current;
                current = current->left;
            } else {
                // 删除线索
                predecessor->right = NULL;
                printf("%d ", current->data);
                current = current->right;
            }
        }
    }
}

/**
 * 后序遍历实现
 */

// 递归后序遍历
void postorder_recursive(TreeNode* root) {
    if (root != NULL) {
        postorder_recursive(root->left);
        postorder_recursive(root->right);
        printf("%d ", root->data);
    }
}

// 迭代后序遍历（使用两个栈）
void postorder_iterative_two_stacks(TreeNode* root) {
    if (root == NULL) return;
    
    Stack* stack1 = create_stack();
    Stack* stack2 = create_stack();
    
    push(stack1, root);
    
    while (!is_stack_empty(stack1)) {
        TreeNode* current = pop(stack1);
        push(stack2, current);
        
        if (current->left != NULL) {
            push(stack1, current->left);
        }
        if (current->right != NULL) {
            push(stack1, current->right);
        }
    }
    
    while (!is_stack_empty(stack2)) {
        TreeNode* current = pop(stack2);
        printf("%d ", current->data);
    }
    
    free(stack1);
    free(stack2);
}

// 迭代后序遍历（使用一个栈和标记）
void postorder_iterative_single_stack(TreeNode* root) {
    if (root == NULL) return;
    
    Stack* stack = create_stack();
    TreeNode* current = root;
    TreeNode* last_visited = NULL;
    
    while (current != NULL || !is_stack_empty(stack)) {
        if (current != NULL) {
            push(stack, current);
            current = current->left;
        } else {
            TreeNode* peek_node = peek(stack);
            
            // 如果右子树存在且未被访问
            if (peek_node->right != NULL && last_visited != peek_node->right) {
                current = peek_node->right;
            } else {
                printf("%d ", peek_node->data);
                last_visited = pop(stack);
            }
        }
    }
    
    free(stack);
}

/**
 * 层序遍历实现
 */

// 标准层序遍历
void level_order_traversal(TreeNode* root) {
    if (root == NULL) return;
    
    Queue* queue = create_queue();
    enqueue(queue, root);
    
    while (!is_queue_empty(queue)) {
        TreeNode* current = dequeue(queue);
        printf("%d ", current->data);
        
        if (current->left != NULL) {
            enqueue(queue, current->left);
        }
        if (current->right != NULL) {
            enqueue(queue, current->right);
        }
    }
    
    free(queue);
}

// 分层打印层序遍历
void level_order_by_levels(TreeNode* root) {
    if (root == NULL) return;
    
    Queue* queue = create_queue();
    enqueue(queue, root);
    
    int level = 0;
    
    while (!is_queue_empty(queue)) {
        int level_size = queue->size;
        printf("第 %d 层: ", level++);
        
        for (int i = 0; i < level_size; i++) {
            TreeNode* current = dequeue(queue);
            printf("%d ", current->data);
            
            if (current->left != NULL) {
                enqueue(queue, current->left);
            }
            if (current->right != NULL) {
                enqueue(queue, current->right);
            }
        }
        printf("\n");
    }
    
    free(queue);
}

// 之字形层序遍历
void zigzag_level_order(TreeNode* root) {
    if (root == NULL) return;
    
    Stack* current_level = create_stack();
    Stack* next_level = create_stack();
    
    push(current_level, root);
    bool left_to_right = true;
    int level = 0;
    
    while (!is_stack_empty(current_level)) {
        printf("第 %d 层: ", level++);
        
        while (!is_stack_empty(current_level)) {
            TreeNode* node = pop(current_level);
            printf("%d ", node->data);
            
            if (left_to_right) {
                if (node->left != NULL) push(next_level, node->left);
                if (node->right != NULL) push(next_level, node->right);
            } else {
                if (node->right != NULL) push(next_level, node->right);
                if (node->left != NULL) push(next_level, node->left);
            }
        }
        
        printf("\n");
        
        // 交换栈
        Stack* temp = current_level;
        current_level = next_level;
        next_level = temp;
        
        left_to_right = !left_to_right;
    }
    
    free(current_level);
    free(next_level);
}

/**
 * 特殊遍历方式
 */

// 垂直遍历
typedef struct VerticalNode {
    int horizontal_distance;
    TreeNode* tree_node;
    struct VerticalNode* next;
} VerticalNode;

void vertical_order_util(TreeNode* root, int hd, VerticalNode** head) {
    if (root == NULL) return;
    
    // 创建新的垂直节点
    VerticalNode* new_node = (VerticalNode*)malloc(sizeof(VerticalNode));
    new_node->horizontal_distance = hd;
    new_node->tree_node = root;
    new_node->next = NULL;
    
    // 插入到链表中（按水平距离排序）
    if (*head == NULL || (*head)->horizontal_distance > hd) {
        new_node->next = *head;
        *head = new_node;
    } else {
        VerticalNode* current = *head;
        while (current->next != NULL && current->next->horizontal_distance <= hd) {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
    
    // 递归处理左右子树
    vertical_order_util(root->left, hd - 1, head);
    vertical_order_util(root->right, hd + 1, head);
}

void vertical_order_traversal(TreeNode* root) {
    VerticalNode* head = NULL;
    vertical_order_util(root, 0, &head);
    
    printf("垂直遍历: ");
    VerticalNode* current = head;
    while (current != NULL) {
        printf("%d ", current->tree_node->data);
        VerticalNode* temp = current;
        current = current->next;
        free(temp);
    }
    printf("\n");
}

// 边界遍历
void print_left_boundary(TreeNode* root) {
    if (root == NULL) return;
    
    if (root->left != NULL) {
        printf("%d ", root->data);
        print_left_boundary(root->left);
    } else if (root->right != NULL) {
        printf("%d ", root->data);
        print_left_boundary(root->right);
    }
}

void print_leaves(TreeNode* root) {
    if (root == NULL) return;
    
    print_leaves(root->left);
    
    if (root->left == NULL && root->right == NULL) {
        printf("%d ", root->data);
    }
    
    print_leaves(root->right);
}

void print_right_boundary(TreeNode* root) {
    if (root == NULL) return;
    
    if (root->right != NULL) {
        print_right_boundary(root->right);
        printf("%d ", root->data);
    } else if (root->left != NULL) {
        print_right_boundary(root->left);
        printf("%d ", root->data);
    }
}

void boundary_traversal(TreeNode* root) {
    if (root == NULL) return;
    
    printf("边界遍历: ");
    printf("%d ", root->data);
    
    print_left_boundary(root->left);
    print_leaves(root->left);
    print_leaves(root->right);
    print_right_boundary(root->right);
    
    printf("\n");
}

// 创建测试树
TreeNode* create_test_tree() {
    TreeNode* root = create_node(1);
    root->left = create_node(2);
    root->right = create_node(3);
    root->left->left = create_node(4);
    root->left->right = create_node(5);
    root->right->left = create_node(6);
    root->right->right = create_node(7);
    root->left->left->left = create_node(8);
    root->left->left->right = create_node(9);
    
    return root;
}

// 测试函数
void test_traversals() {
    printf("=== 树遍历算法测试 ===\n");
    
    TreeNode* root = create_test_tree();
    
    printf("前序遍历:\n");
    printf("递归: ");
    preorder_recursive(root);
    printf("\n");
    
    printf("迭代: ");
    preorder_iterative(root);
    printf("\n");
    
    printf("Morris: ");
    preorder_morris(root);
    printf("\n\n");
    
    printf("中序遍历:\n");
    printf("递归: ");
    inorder_recursive(root);
    printf("\n");
    
    printf("迭代: ");
    inorder_iterative(root);
    printf("\n");
    
    printf("Morris: ");
    inorder_morris(root);
    printf("\n\n");
    
    printf("后序遍历:\n");
    printf("递归: ");
    postorder_recursive(root);
    printf("\n");
    
    printf("双栈迭代: ");
    postorder_iterative_two_stacks(root);
    printf("\n");
    
    printf("单栈迭代: ");
    postorder_iterative_single_stack(root);
    printf("\n\n");
    
    printf("层序遍历:\n");
    printf("标准: ");
    level_order_traversal(root);
    printf("\n");
    
    printf("分层打印:\n");
    level_order_by_levels(root);
    printf("\n");
    
    printf("之字形遍历:\n");
    zigzag_level_order(root);
    printf("\n");
    
    vertical_order_traversal(root);
    boundary_traversal(root);
}

int main() {
    test_traversals();
    return 0;
}

复杂度分析

时间复杂度

• 所有遍历方式：O(n) - 每个节点访问一次

空间复杂度

• 递归实现：O(h) - h为树的高度
• 迭代实现：O(h) - 显式栈的空间
• Morris遍历：O(1) - 常数空间
• 层序遍历：O(w) - w为树的最大宽度

实际应用

1. 编译器：语法树的分析和代码生成
2. 文件系统：目录结构的遍历
3. 表达式求值：数学表达式的计算
4. 数据库：B树索引的遍历
5. XML/HTML解析：文档结构的处理
6. 图形渲染：场景图的遍历

总结

树遍历算法是树形数据结构操作的基础，不同的遍历方式适用于不同的应用场景。递归实现简洁优雅，迭代实现更加高效，Morris遍历则在空间复杂度上达到了最优。掌握各种遍历方法及其实现细节，对于理解和应用树形数据结构具有重要意义。

版权所有，如有侵权请联系我