【数据结构】树与二叉树（九）：二叉树的后序遍历（非递归算法NPO）

5.2.1 二叉树

  二叉树是一种常见的树状数据结构，它由结点的有限集合组成。一个二叉树要么是空集，被称为空二叉树，要么由一个根结点和两棵不相交的子树组成，分别称为左子树和右子树。每个结点最多有两个子结点，分别称为左子结点和右子结点。

二叉树性质

引理5.1：二叉树中层数为i的结点至多有$2^i$个，其中$i\ge 0$。

引理5.2：高度为k的二叉树中至多有$2^{k+1}-1$个结点，其中$k\ge 0$。

引理5.3：设T是由n个结点构成的二叉树，其中叶结点个数为$n_0$，度数为2的结点个数为$n_2$，则有$n_0=n_2+1$。

• 详细证明过程见前文：【数据结构】树与二叉树（三）：二叉树的定义、特点、性质及相关证明

满二叉树、完全二叉树定义、特点及相关证明

• 详细证明过程见前文：【数据结构】树与二叉树（四）：满二叉树、完全二叉树及其性质

5.2.2 二叉树顺序存储

  二叉树的顺序存储是指将二叉树中所有结点按层次顺序存放在一块地址连续的存储空间中，详见：
【数据结构】树与二叉树（五）：二叉树的顺序存储（初始化，插入结点，获取父节点、左右子节点等）

5.2.3 二叉树链接存储

  二叉树的链接存储系指二叉树诸结点被随机存放在内存空间中，结点之间的关系用指针说明。在链式存储中，每个二叉树结点都包含三个域：数据域（Data）、左指针域（Left）和右指针域（Right），用于存储结点的信息和指向子结点的指针，详见：
【数据结构】树与二叉树（六）：二叉树的链式存储

5.2.4 二叉树的遍历

• 遍历（Traversal）是对二叉树中所有节点按照一定顺序进行访问的过程。
• 通过遍历，可以访问树中的每个节点，并按照特定的顺序对它们进行处理。
• 对二叉树的一次完整遍历，可给出树中结点的一种线性排序。
  • 在二叉树中，常用的遍历方式有三种：先序遍历、中序遍历和后序遍历。
  • 这三种遍历方式都可以递归地进行，它们的区别在于节点的访问顺序。
    • 在实现遍历算法时，需要考虑递归终止条件和递归调用的顺序。
  • 还可以使用迭代的方式来实现遍历算法，使用栈或队列等数据结构来辅助实现。
• 遍历是二叉树中基础而重要的操作，它为其他许多操作提供了基础，如搜索、插入、删除等。
  

1-3 先序、中序、后序遍历递归实现及相关练习

【数据结构】树与二叉树（七）：二叉树的遍历（先序、中序、后序及其C语言实现）

后序遍历递归实现

void postOrderTraversal(struct Node* root) {
    if (root == NULL) {
        return;
    }
    // 递归遍历左子树
    postOrderTraversal(root->left);
    // 递归遍历右子树
    postOrderTraversal(root->right);
    // 访问根节点
    printf("%c ", root->data);
}

1
2
3
4
5
6
7
8
9
10
11
12

4. 中序遍历非递归

【数据结构】树与二叉树（八）：二叉树的中序遍历（非递归算法NIO）

5. 后序遍历非递归

a. 算法NPO

b. 算法解读

  算法NPO(t)利用了一个辅助堆栈S来遍历二叉树T的所有节点。

1. 如果t为空，则直接返回。
2. 创建一个空堆栈S，并将根节点t和初始标记0入栈（S <= (t, 0)）。
3. 进入循环，只要堆栈S非空，执行以下步骤：
   a. 从堆栈S中弹出栈顶元素，将其赋值给(p, i)。
   b. 如果标记i为0，则表示节点p还未处理左子树，将左子节点入栈（S <= (Left( p), 0)）。
   c. 如果标记i为1，则表示节点p已处理完左子树，但还未处理右子树，将右子节点入栈（S <= (Right( p), 0)）。
   d. 如果标记i为2，则表示节点p的左右子树都已处理完毕，可以打印节点p的值。
4. 跳转到步骤3，继续循环，直到堆栈S为空。

c. 典例剖析

d.代码实现

void nonRecursiveInOrder(struct Node* root) {
    struct Node* stack[100];  // 辅助堆栈，用于模拟递归调用栈
    int top = -1;  // 栈顶指针

    struct Node* current = root;

    while (current != NULL || top != -1) {
        // 将当前结点的左子结点入栈
        while (current != NULL) {
            stack[++top] = current;
            current = current->left;
        }

        // 弹出栈顶结点，并访问
        current = stack[top--];
        printf("%c ", current->data);

        // 处理右子结点
        current = current->right;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5. 代码整合

#include 
#include 

// 二叉树结点的定义
struct Node {
    char data;
    struct Node* left;
    struct Node* right;
};

// 创建新结点
struct Node* createNode(char data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 后序遍历
void postOrderTraversal(struct Node* root) {
    if (root == NULL) {
        return;
    }
    // 递归遍历左子树
    postOrderTraversal(root->left);
    // 递归遍历右子树
    postOrderTraversal(root->right);
    // 访问根节点
    printf("%c ", root->data);
}


// 非递归后根遍历
void nonRecursivePostOrder(struct Node* root) {
    struct Node* stack[100];  // 辅助堆栈，用于模拟递归调用栈
    int tagStack[100];  // 标记堆栈，用于记录结点的访问状态
    int top = -1;  // 栈顶指针

    struct Node* current = root;
    int tag = 0;

    while (current != NULL || top != -1) {
        while (current != NULL && tag == 0) {
            stack[++top] = current;
            tagStack[top] = 0;
            current = current->left;
        }

        if (tagStack[top] == 0) {
            current = stack[top];
            tagStack[top] = 1;
            current = current->right;
            tag = 0;
        } else if (tagStack[top] == 1) {
            current = stack[top--];
            printf("%c ", current->data);
            tag = 1;
        }
    }
}

int main() {
    // 创建一棵二叉树
    struct Node* root = createNode('a');
    root->left = createNode('b');
    root->right = createNode('c');
    root->left->left = createNode('d');
    root->left->right = createNode('e');
    root->left->right->left = createNode('f');
    root->left->right->right = createNode('g');

    // 递归后序遍历二叉树
    printf("Recursive In-order traversal: \n");
    postOrderTraversal(root);
    printf("\n");


    // 非递归后序遍历二叉树
    printf("Non-recursivePost-order traversal: \n");
    nonRecursivePostOrder(root);
    printf("\n");
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89