PTA（树和二叉树）1-7 二叉树的非递归遍历

1-7 二叉树的非递归遍历

分数 5

作者 陈越

单位 浙江大学

本题要求用非递归的方法实现对给定二叉树的 3 种遍历。

函数接口定义：

1
2
3
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );

其中BinTree结构定义如下：

1
2
3
4
5
6
7
8
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
    int flag;
};

要求 3 个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。

此外，裁判程序中给出了堆栈的全套操作，可以直接调用。

裁判测试程序样例：

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
#include <stdio.h>
#include <stdlib.h>
typedef enum { false, true } bool;

typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
    int flag;
};

/*------堆栈的定义-------*/
typedef Position SElementType;
typedef struct SNode *PtrToSNode;
struct SNode {
    SElementType Data;
    PtrToSNode Next;
};
typedef PtrToSNode Stack;

/* 裁判实现，细节不表 */
Stack CreateStack();
bool IsEmpty( Stack S );
bool Push( Stack S, SElementType X );
SElementType Pop( Stack S ); /* 删除并仅返回S的栈顶元素 */
SElementType Peek( Stack S );/* 仅返回S的栈顶元素 */
/*----堆栈的定义结束-----*/

BinTree CreateBinTree(); /* 裁判实现，细节不表 */
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );

int main()
{
    BinTree BT = CreateBinTree();
    printf("Inorder:");    InorderTraversal(BT);    printf("\n");
    printf("Preorder:");   PreorderTraversal(BT);   printf("\n");
    printf("Postorder:");  PostorderTraversal(BT);  printf("\n");
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：

1
如图

tree.jpg

输出样例：

1
2
3
Inorder: D B E F A G H C I
Preorder: A B D F E C G H I
Postorder: D E F B H G I C A
  • 非递归跟前面的递归真的是两个级别，非递归用到栈了，直接上强度了
  • 递归只用思考根在哪个位置，然后写出终结条件就可以了
  • 而非递归需要像思考：比如中序序列怎么列出来的思路，完整的用代码实现自己的逻辑
  • 这题用栈很妙，让p先指向根节点，都是一个while套一个while
  • 遍历左子树直到空，期间将根节点依次入栈，用来下一次出栈访问上一个结点的信息
  • 前序遍历：先访问根节点，再遍历左子树，最后遍历右子树（根 → 左 → 右）。
  • 中序遍历：先遍历左子树，再访问根节点，最后遍历右子树（左 → 根 → 右）。
  • 后序遍历：先遍历左子树，再遍历右子树，最后访问根节点（左 → 右 → 根）。

答案

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
void InorderTraversal( BinTree BT ) {
    Stack S = CreateStack();
    BinTree p = BT; // 用于遍历树的结点
    while (p != NULL || !IsEmpty(S)) {
        // 遍历至最左子树，所有左节点入栈，直到指向空(类比老师上课讲的，往左走到无路可走)
        while (p != NULL) {
            Push(S, p);
            p = p->Left;
        }
        // 弹出栈顶节点（左子树已遍历完），访问根节点
        p = Pop(S);
        printf(" %c", p->Data);
        // 转向右子树(因为要根左右)
        p = p->Right;
    }
}
void PreorderTraversal( BinTree BT ) {
    Stack S = CreateStack(); // 要记录访问过的根，所以要入栈记录，后面依次弹出，可以访问右子树
    BinTree p = BT;
    while (p != NULL || !IsEmpty(S)) {
        // 遍历至最左子树，过程中访问根节点
        while (p != NULL) {
            printf(" %c", p->Data); // 先访问根节点
            Push(S, p);             // 根节点入栈（后续需访问其右子树）
            p = p->Left;            // 继续遍历左子树
        }
        // 弹出栈顶节点，转向其右子树
        p = Pop(S);
        p = p->Right;
    }
}
void PostorderTraversal( BinTree BT ) {
    Stack S = CreateStack();
    BinTree p = BT;
    while (p != NULL || !IsEmpty(S)) {
        // 遍历至最左子树，过程中访问根节点
        while (p != NULL) {
            Push(S, p); // 遍历至最左子树，所有节点入栈（flag=0表示未访问）
            p = p->Left; // 继续遍历左子树
        }
        // 查看栈顶节点
        p = Peek(S);
        if (p->flag == 0) {
            // 首次访问：标记为已访问左子树，转向右子树
            p->flag = 1;
            p = p->Right;
        } else {
            // 再次访问：右子树已遍历完，访问根节点
            Pop(S);
            printf(" %c", p->Data);
            p = NULL; // 继续处理栈顶节点
        }
    }
}

代码解析

  1. 中序遍历（InorderTraversal）
    • 逻辑：先将所有左子树节点入栈，直到最左节点；弹出栈顶节点（此时左子树已遍历完），访问该节点（根节点），再转向其右子树重复上述过程。
    • 关键：根节点的访问时机在左子树遍历完成后。
  2. 前序遍历（PreorderTraversal）
    • 逻辑：在遍历左子树的过程中，每遇到一个节点就立即访问（根节点优先），然后将节点入栈（用于后续访问右子树）；左子树遍历完后，弹出栈顶节点并转向其右子树。
    • 关键：根节点的访问时机在左子树遍历之前。
  3. 后序遍历（PostorderTraversal）
    • 逻辑：通过节点的flag标记控制访问时机。首次入栈时flag=0（未访问右子树），弹出时若flag=0，则标记为1并转向右子树；再次遇到flag=1的节点时，说明右子树已遍历完，此时访问该节点。
    • 关键：根节点的访问时机在左右子树均遍历完成后，需通过标记区分节点是否已处理右子树。

结构含义

1. 核心数据结构：二叉树节点（struct TNode）

这是整个结构的基础，用于存储二叉树的每个节点信息：

  • ElementType Data：存储节点的数据（这里通过 typedef 定义为 char 类型，即节点存储字符数据）。
  • BinTree Left 和 BinTree Right：分别指向当前节点的左子树和右子树（BinTree 本质是指向 TNode 的指针，即 Position）。
  • int flag：节点的标记位（通常用于遍历等操作中标记节点状态，例如是否已访问）。

2. 类型别名：简化指针表示

通过 typedef 定义了三个别名，本质都是指针类型，目的是简化代码书写并明确语义：

  • Position：等价于 struct TNode *，表示 “二叉树节点的位置（指针）”。
  • BinTree：等价于 Position（即 struct TNode *），专门用于表示 “二叉树”（通常指向根节点）。
  • ElementType：等价于 char，明确节点存储的数据类型（后续若需修改数据类型，只需修改此处即可）。

3. 辅助结构：堆栈（struct SNode 及相关类型）

堆栈用于辅助二叉树的操作（例如非递归遍历），其设计与二叉树节点强关联：

  • SElementType：堆栈中存储的元素类型，被定义为 Position（即二叉树节点的指针），说明这个堆栈是专门用于存放二叉树节点地址的。
  • struct SNode：堆栈的节点结构，包含：
    • SElementType Data：存储一个二叉树节点的指针（即栈元素是二叉树节点的位置）。
    • PtrToSNode Next：指向栈的下一个节点（构成链式堆栈）。
  • Stack：等价于 PtrToSNode，表示 “堆栈”（通常指向栈顶节点）。