C++二叉树实验

1.以下图的二叉树为例，设计程序完成对二叉树的基本操作

运行结果如图所示：

2.自行设计一个算法，以二叉树为存储结构，统计二叉树的叶子结点个数，并将叶子节点依次输出

#include 
#include 

#define MaxSize 100
typedef char ElemType;

typedef struct node {
    //数据元素
    ElemType data;
    //指向左孩子
    struct node *lchild;
    //指向右孩子
    struct node *rchild;
} BTNode;

//由str串创建二叉链
void CreateBTNode(BTNode *&b, char *str) {
    BTNode *St[MaxSize], *p = NULL;
    int top = -1, k, j = 0;
    char ch;
    b = NULL;                //建立的二叉树初始时为空
    ch = str[j];
    while (ch != '\0')    //str未扫描完时循环
    {
        switch (ch) {
            case '(':
                top++;
                St[top] = p;
                k = 1;
                break;        //为左结点
            case ')':
                top--;
                break;
            case ',':
                k = 2;
                break;                        //为右结点
            default:
                p = (BTNode *) malloc(sizeof(BTNode));
                p->data = ch;
                p->lchild = p->rchild = NULL;
                if (b == NULL)                    //p指向二叉树的根结点
                    b = p;
                else                            //已建立二叉树根结点
                {
                    switch (k) {
                        case 1:
                            St[top]->lchild = p;
                            break;
                        case 2:
                            St[top]->rchild = p;
                            break;
                    }
                }
        }
        j++;
        ch = str[j];
    }
}

//以广义表法输出二叉树
void DispBTNode(BTNode *b) {
    if (b != NULL) {
        printf("%c", b->data);
        if (b->lchild != NULL || b->rchild != NULL) {
            printf("(");
            DispBTNode(b->lchild);
            if (b->rchild != NULL) printf(",");
            DispBTNode(b->rchild);
            printf(")");
        }
    }
}

//求二叉树b的结点个数
int Nodes(BTNode *b) {
    int num1, num2;
    if (b == NULL) {
        return 0;
        // b为叶子节点
    } else if (b->lchild == NULL && b->rchild == NULL) {
        return 1;
    } else {
        num1 = Nodes(b->lchild);
        num2 = Nodes(b->rchild);
        return (num1 + num2 + 1);
    }

}

//求二叉树b的叶子结点个数
int LeafNodes(BTNode *b) {
    int num1, num2;
    if (b == NULL) {
        return 0;
        // b为叶子节点
    } else if (b->lchild == NULL && b->rchild == NULL) {
        return 1;
    } else {
        num1 = LeafNodes(b->lchild);
        num2 = LeafNodes(b->rchild);
        return (num1 + num2);
    }

}

//求二叉树b的深度
int BTNodeDepth(BTNode *b) {
    int lchilddep, rchilddep;
    if (b == NULL) {
        return 0;
    } else {
        lchilddep = BTNodeDepth(b->lchild);
        rchilddep = BTNodeDepth(b->rchild);
        return lchilddep > rchilddep ? (lchilddep + 1) : (rchilddep + 1);
    }

}

//先序遍历的递归算法
void PreOrder(BTNode *b) {
    if (b->data == NULL) {
        return;
    }
    // 输出根结点
    printf("%c ", b->data);
    // 遍历左子树
    if (b->lchild != NULL) {
        PreOrder(b->lchild);
    }
    // 遍历右子树
    if (b->rchild != NULL) {
        PreOrder(b->rchild);
    }
}

//中序遍历的递归算法
void InOrder(BTNode *b) {
    if (b->data == NULL) {
        return;
    }
    // 遍历左子树
    if (b->lchild != NULL) {
        InOrder(b->lchild);
    }
    // 输出根结点
    printf("%c ", b->data);
    // 遍历右子树
    if (b->rchild != NULL) {
        InOrder(b->rchild);
    }

}

//后序遍历的递归算法
void PostOrder(BTNode *b) {
    if (b->data == NULL) {
        return;
    }
    // 遍历左子树
    if (b->lchild != NULL) {
        PostOrder(b->lchild);
    }
    // 遍历右子树
    if (b->rchild != NULL) {
        PostOrder(b->rchild);
    }
    // 输出根结点
    printf("%c ", b->data);
}

//层次遍历算法
void TravLevel(BTNode *b) {
    //定义循环队列
    BTNode *Qu[MaxSize];
    //定义队首和队尾指针
    int front, rear;
    //置队列为空队列
    front = rear = 0;
    if (b != NULL)
        printf("%c ", b->data);
    //结点指针进入队列
    rear++;
    Qu[rear] = b;
    //队列不为空
    while (rear != front) {
        front = (front + 1) % MaxSize;
        //队头出队列
        b = Qu[front];
        //输出左孩子,并入队列
        if (b->lchild != NULL) {
            printf("%c ", b->lchild->data);
            rear = (rear + 1) % MaxSize;
            Qu[rear] = b->lchild;
        }
        //输出右孩子,并入队列
        if (b->rchild != NULL) {
            printf("%c ", b->rchild->data);
            rear = (rear + 1) % MaxSize;
            Qu[rear] = b->rchild;
        }
    }
    printf("\n");
}


void AllPath(BTNode *b, ElemType path[], int pathlen) {
    int i;
    if (b != NULL) {
        //*b为叶子结点
        if (b->lchild == NULL && b->rchild == NULL) {
            printf("%c到根结点路径: %c ", b->data, b->data);
            for (i = pathlen - 1; i >= 0; i--) {
                printf("%c ", path[i]);
            }
            printf("\n");
        } else {
            //将当前结点放入路径中
            path[pathlen] = b->data;
            //路径长度增1
            pathlen++;
            //递归扫描左子树
            AllPath(b->lchild, path, pathlen);
            //递归扫描右子树
            AllPath(b->rchild, path, pathlen);
            //恢复环境
            pathlen--;
        }
    }
}

int main() {
    BTNode *b;
    ElemType path[MaxSize];
    CreateBTNode(b, "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    printf(" 二叉树b: ");
    DispBTNode(b);
    printf("\n\n");

    //在此处调用相关函数，输出二叉树b的结点个数;
    printf("二叉树b的结点个数：%d", Nodes(b));
    printf("\n");
    //在此处调用相关函数，输出二叉树b的叶子结点个数;
    printf("二叉树b的叶子结点个数：%d", LeafNodes(b));
    printf("\n");
    //在此处调用相关函数，输出二叉树b的深度;
    printf("二叉树b的深度：%d", BTNodeDepth(b));
    printf("\n\n");

    //参照运行结果图，在此处调用先序遍历函数;
    printf("先序遍历序列: ");
    PreOrder(b);
    printf("\n");
    //参照运行结果图，在此处调用中序遍历函数;
    printf("中序遍历序列: ");
    InOrder(b);
    printf("\n");
    //参照运行结果图，在此处调用后序遍历函数;
    printf("后序遍历序列: ");
    PostOrder(b);
    printf("\n");
    printf("层次遍历序列: ");
    TravLevel(b);
    printf("\n");

    printf("叶子结点路径: \n");
    AllPath(b, path, 0);
    printf("\n");
}

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269

运行截图