#include<cstring> #include<cstdio> #include<iostream> using namespace std; typedef struct treepoint* tNode; typedef struct queue* qNode; typedef struct stack* sNode; struct treepoint { char date; tNode lson, rson; }; char s[110]; int pos; tNode build() {//建立二叉树 tNode bt = (tNode)malloc(sizeof(treepoint)); pos++; if (s[pos] == '#')bt = NULL; else { bt->date = s[pos]; bt->lson = build(); bt->rson = build(); } return bt; } void pre_order_travel(tNode bt) {//前序遍历 printf("%c", bt->date); if (bt->lson != NULL) pre_order_travel(bt->lson); if (bt->rson != NULL) pre_order_travel(bt->rson); //free(bt); } void mid_order_travel(tNode bt) {//中序遍历 if (bt->lson != NULL) mid_order_travel(bt->lson); printf("%c", bt->date); if (bt->rson != NULL) mid_order_travel(bt->rson); //free(bt); } void post_order_travel(tNode bt) {//后序遍历 if (bt->lson != NULL) post_order_travel(bt->lson); if (bt->rson != NULL) post_order_travel(bt->rson); printf("%c", bt->date); //free(bt); } struct stack { tNode value; sNode next; }; sNode top; void Stack_creat() { top = (sNode)malloc(sizeof(stack)); top->next = NULL; } void Stack_push(tNode item) { sNode temp = (sNode)malloc(sizeof(stack)); temp->next = top->next; temp->value = item; top->next = temp; } bool Stack_empty() { return top->next == NULL; } void Stack_pop() { sNode temp = top->next; top->next = temp->next; } void iter_Inorder(tNode root) {//非递归遍历二叉树 Stack_creat(); if (root != NULL) { Stack_push(root); } while (!Stack_empty()) { sNode temp = top->next; cout << temp->value->date; Stack_pop(); if (temp->value->rson) { Stack_push(temp->value->rson); } if (temp->value->lson) { Stack_push(temp->value->lson); } } cout << endl; } qNode front, rear; struct queue { tNode value; qNode next; }; void Queue_creat() { front = (qNode)malloc(sizeof(queue)); rear = (qNode)malloc(sizeof(queue)); front->next = rear; } bool Queue_empty() { return front->next == rear; } void Queue_delete() { qNode temp = front->next; front->next = temp->next; } void Queue_push(tNode item) { qNode temp = (qNode)malloc(sizeof(queue)); rear->value = item; rear->next = temp; temp->next = NULL; rear = temp; } void level_order(tNode root) {//二叉树的层序遍历 if (root == NULL) { cout << endl; } Queue_creat(); Queue_push(root); while (!Queue_empty()) { qNode temp = front->next; Queue_delete(); cout << temp->value->date; if (temp->value->lson != NULL) { Queue_push(temp->value->lson); } if (temp->value->rson != NULL) { Queue_push(temp->value->rson); } } cout << endl; } int leaf(tNode bt) {//计算叶子节点数量 int flag = 0; int cnt = 0; if (bt->lson != NULL) cnt += leaf(bt->lson); else flag++; if (bt->rson != NULL) cnt += leaf(bt->rson); else flag++; if (flag == 2) cnt = 1; return cnt; } int maxheight = 0; void height(tNode bt, int now) {//计算树的深度 if (now > maxheight)maxheight = now; if (bt->lson != NULL) height(bt->lson, now + 1); if (bt->rson != NULL) height(bt->rson, now + 1); } int main() { while (~scanf("%s", s + 1)) {//输入二叉树的前序遍历来建树 pos = 0; tNode root = build(); cout << "先序遍历: "; pre_order_travel(root); cout << endl; cout << "中序遍历: "; mid_order_travel(root); cout << endl; cout << "后序遍历: "; post_order_travel(root); cout << endl; cout << "二叉树的非递归遍历: "; iter_Inorder(root); cout << "二叉树的层序遍历: "; level_order(root); printf("叶子结点数: %d\n", leaf(root)); maxheight = 0; height(root, 1); printf("树的深度为: %d\n", maxheight); } }