数据结构实验：二叉树的各种遍历（手写栈和队列实现）

#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);
    }
}