西南交通大学数据结构第六次实验报告-顺序存储完全二叉树先、中、后序遍历

实验目的：掌握完全二叉树的顺序存储与链式存储结构以及遍历算法。

#include "iostream"

using namespace std;

typedef struct BinaryTree {
    char value;
    BinaryTree* lc;
    BinaryTree* rc;
} BT;

BT* construct_tree(int depth, int length, const char *msg) {
    if (depth <= length) {
        BT *root = new BT;
        root->value = msg[depth - 1];
        root->lc = construct_tree(2 * depth, length, msg);
        root->rc = construct_tree(2 * depth + 1, length, msg);
        return root;
    } else {
        return nullptr;
    }
}


void front(BT *tree) {
    if (tree) {
        cout << tree->value;
        front(tree->lc);
        front(tree->rc);
    } else {
        return ;
    }
}

void middle(BT *tree) {
    if (tree) {
        middle(tree->lc);
        cout << tree->value;
        middle(tree->rc);
    } else {
        return ;
    }
}

void back(BT *tree) {
    if (tree) {
        back(tree->lc);
        back(tree->rc);
        cout << tree->value;
    } else {
        return ;
    }
}

void front(const char* tree, int length, int depth) {
    if (depth < length) {
        cout << tree[depth];
        front(tree, length, depth * 2 + 1);
        front(tree, length, depth * 2 + 2);
    } else {
        return ;
    }
}

void middle(const char* tree, int length, int depth) {
    if (depth < length) {
        middle(tree, length, depth * 2 + 1);
        cout << tree[depth];
        middle(tree, length, depth * 2 + 2);
    } else {
        return ;
    }
}

void back(const char* tree, int length, int depth) {
    if (depth < length) {
        back(tree, length, depth * 2 + 1);
        back(tree, length, depth * 2 + 2);
        cout << tree[depth];
    }
}

int main() {
    string in;
    cin >> in;
    const char *msg = in.c_str();
    cout << "----------Front!----------" << endl;
    front(msg, in.size(), 0);
    cout << endl;
    cout << "----------Middle!----------" << endl;
    middle(msg, in.size(), 0);
    cout << endl;
    cout << "----------Back!----------" << endl;
    back(msg, in.size(), 0);
    BT* tree = construct_tree(1, in.size(), msg);
    cout << endl;
    cout << "----------Reverted!----------" << endl;
    cout << "----------Front!----------" << endl;
    front(tree);
    cout << endl;
    cout << "----------Middle!----------" << endl;
    middle(tree);
    cout << endl;
    cout << "----------Back!----------" << endl;
    back(tree);
    cout << endl;
    return 0;
}

有问题评论区指教，谢谢