Penney's Blogs

言必行，行必果

0%

03-树3 Tree Traversals Again

发表于 分类于 Valine：
本文字数： 3.6k 阅读时长 ≈ 3 分钟

​ An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

20151020162946653

Input Specification:

​ Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.

Output Specification:

​ For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:
1
2
3
4
5
6
7
8
9
10
11
12
13
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
Sample Output:
1
3 4 2 6 5 1
分析：

​ 从堆栈实现二叉树非递归遍历算法可知，入栈操作是先序遍历的顺序，而出栈操作则是中序遍历操作的顺序，需要输出后序遍历的顺序；所以需要根据push和pop构造出先序数组和中序数组，再利用递归算法依次找到根结点左右两边各元素的顺序。

编码：
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

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

#define MAXSIZE 50
struct SNode {
    int data[MAXSIZE];
    int top;
};
typedef struct SNode *PtrToSNode;

int *in, *pre, *post, number;

PtrToSNode CreateStack() {
    PtrToSNode temp;
    temp = (PtrToSNode) malloc(sizeof(struct SNode));
    temp->top = 0;
    return temp;
}

void Push(PtrToSNode s, int item) {
    s->data[++(s->top)] = item;
}

int Pop(PtrToSNode s) {
    return s->data[(s->top)--];
}

void DestroyStack(PtrToSNode s) {
    free(s);
}

// 根据输入数据创建先序数组pre和中序数组in
void Input() {
    int i, n, value, indexPush = 0, indexPop = 0;
    char *s;
    char temp[50];
    // 1.创建堆栈Stack
    PtrToSNode Stack = CreateStack();
    // 2.读取共有多少数字number
    scanf("%d", &number);
    n = number * 2;
    // 3.根据输入的number创建pre,in,post数组
    in = (int *) malloc(sizeof(int) * n);
    pre = (int *) malloc(sizeof(int) * n);
    post = (int *) malloc(sizeof(int) * n);
    // 4.根据输入的数据，读取push或pop操作，小于number*2
    for (i = 0; i < n; i++) {
        // 5.读取字符串temp
        scanf("%s", temp);
        // 6.字符串是否包含字符h
        s = strchr(temp, 'h');
        if (s != NULL) {
            // 7.如果包含，则继续读取数值value
            scanf("%d", &value);
            // 8.将读取到数值存入数组pre，并压入堆栈Stack
            pre[indexPush] = value;
            Push(Stack, value);
            indexPush++;
        } else {
            // 9.如果不包含字符h,则弹栈，将值存入数组in
            in[indexPop] = Pop(Stack);
            indexPop++;
        }
    }
    // 10.释放堆栈Stack
    DestroyStack(Stack);
}

// 根据先序、中序获取后序数组post
void GetPost(int preL, int inL, int postL, int len) {
    // 1.如果在数组外，直接返回
    if (len == 0)
        return;
    // 2.如果数组最后只有一个元素时，直接将先序值赋值给后序对应位置
    if (len == 1) {
        post[postL] = pre[preL];
        return;
    }
    int root, i, lenL, lenR;
    // 3.数组长度大于1时，将先序pre的第1个元素即为根结点
    root = pre[preL];
    // 4.将根结点的值赋值给post数组的最末位
    post[postL + len - 1] = root;
    // 5.遍历找到根结点root在中序数组in中的位置i
    for (i = 0; i < len; i++) {
        if (in[inL + i] == root)
            break;
    }
    // 6.根结点root的左子树部分长度即为i, 右子树长度为len-i-1（根结点）
    lenL = i;
    lenR = len - lenL - 1;
    // 7.递归求左子树部分, 先序指针右移1位, 数组为左子树部分lenL
    GetPost(preL + 1, inL, postL, lenL);
    // 8.递归求右子树部分, 先序、中序、后序指针移至根结点右边，数组长度不右子树部分lenR
    GetPost(preL + lenL + 1, inL + lenL + 1, postL + lenL, lenR);
}

void printPost() {
    for (int i = 0; i < number; i++) {
        if (i == number - 1) {
            printf("%d", post[i]);
        } else {
            printf("%d ", post[i]);
        }
    }
}

int main() {
    Input();
    GetPost(0, 0, 0, number);
    printPost();
    return 0;
}
小结：
  1. 在构造先序数组和中序数组时，用strchr(temp, ‘h’)函数判断字符串中是否包含字符h，包含返回具体的地址，不包含返回NULL；
  2. 先序数组的第1个元素为后序数组的最后一个元素，即为根结点，如何根据这个条件写递归函数；
  3. 构造的递归函数的边界条件，如len=0，len=1，如何确定？