数据结构实现: 可以正确运行的练手程序

程序源代码全部在此:
1. 链表: 数据结构定义链表没有头结点。增删节点的时候需要有判定头结点是否为空的代码。
2. 链表: 数据结构增加了头节点的定义，以一个元素的代价大大简化了判定的代码，大大提高了运行效率。典型的时间换空间。
3. 二叉树和节点遍历: 已知前序和中序遍历，求后续遍历的结果。
------------------------------
1. 链表源代码(无头结点):

struct node{
    int data;
    node* link;
};
node* create_node(int i)
{
    return new node{ i, nullptr };
}
void delete_node(node* n)
{
    if (n->link)
        delete_node(n->link);
    delete n;
}
struct list{
    node* p;
};
list* create_list()
{
    return new list{ nullptr };
}
void delete_list(list* l)
{
    if (l->p)
        delete_node(l->p);
    l->p = nullptr;
}
void insert_node(list* l, node* n)
{
    node* tmp = l->p;
    if (tmp == nullptr)
        l->p = n;
    else
    {
        while (tmp->link)
            tmp = tmp->link;
        tmp->link = n;
    }
}
void remove_node(list* l, size_t idx)
{
    if (idx < 0)throw false;
    node* p = l->p; //head
    if (idx == 0)
    {
        l->p = p->link;
    }
    else
    {
        node* old = nullptr;
        while (idx--)
        {
            if (p == nullptr)throw false;
            old = p;
            p = p->link;
        }
        old->link = p->link;
    }
    p->link = nullptr;
    delete_node(p);
}
void display_list(list* l)
{
    node * p = l->p;
    while (p)
    {
        cout << p->data << endl;
        p = p->link;
    }
}
int main()
{
    list* l = create_list();
    insert_node(l, create_node(1));
    insert_node(l, create_node(2));
    insert_node(l, create_node(3));
    insert_node(l, create_node(4));
    display_list(l);
    remove_node(l, 2);
    remove_node(l, 0);
    cout << "--------" << endl;
    display_list(l);
    delete_list(l);
    return 0;
}

2. 链表源代码(有头结点):

struct node{
    int data;
    node* link;
};
node* create_node(int i)
{
    return new node{ i, nullptr };
}
void delete_node(node* n)
{
    if (n->link)
        delete_node(n->link);
    delete n;
}
struct list{
    node head;
};
list* create_list()
{
    return new list{ node{ -1, nullptr } };
}
void delete_list(list* l)
{
    if (l->head.link)
        delete_node(l->head.link);
    l->head.link = nullptr;
}
void insert_node(list* l, node* n)
{
    node* tmp = &l->head;
    while (tmp->link)
        tmp = tmp->link;
    tmp->link = n;
}
void remove_node(list* l, size_t idx)
{
    if (idx <= 0)throw false;
    node* p = l->head.link; //head
    node* old = nullptr;
    while (idx--)
    {
        if (p == nullptr)throw false;
        old = p;
        p = p->link;
    }
    old->link = p->link;
    p->link = nullptr;
    delete_node(p);
}
void display_list(list* l)
{
    node * p = l->head.link;
    while (p)
    {
        cout << p->data << endl;
        p = p->link;
    }
}
int main()
{
    list* l = create_list();
    insert_node(l, create_node(1));
    insert_node(l, create_node(2));
    insert_node(l, create_node(3));
    insert_node(l, create_node(4));
    display_list(l);
    remove_node(l, 3);
    remove_node(l, 2);
    cout << "--------" << endl;
    display_list(l);
    delete_list(l);
    return 0;
}

3. 二叉树的遍历和重建

struct node
{
    node* left;
    node* right;
    char data;
};
struct tree
{
    node* root;
};
node* createNode(char i = -1)
{
    return new node{ nullptr, nullptr, i };
}
void destroyNode(node* n)
{
    if (n == nullptr)return;
    if (n->left) destroyNode(n->left);
    if (n->right) destroyNode(n->right);
    delete n;
}
tree* createTree()
{
    return new tree{ nullptr };
}
void destroyTree(tree* t)
{
    destroyNode(t->root);
}
node* createRoot(tree* t, node* n)
{
    if (t->root) destroyNode(t->root);
    t->root = n;
    return n;
}
node* appendNode(node* n, node* parent = nullptr, bool isLeft = true)//false means right
{
    if (isLeft) parent->left = n;
    else parent->right = n;
    return n;
}
void traverseNode(node* n)
{
    if (n == nullptr)return;
    traverseNode(n->left);
    traverseNode(n->right);
    cout << n->data << endl;
}
void traverseTree(tree* t)
{
    node* n = t->root;
    traverseNode(n);
}
void rebuildTreeImpl(node* n, char* DLR, char* LDR, size_t length)
{
    if (length == 0)
        return;
    char root = DLR[0];
    n->data = root;
    size_t idx = 0;
    for (; idx < length; ++idx)
        if (root == LDR[idx])break;

    char* newDLR = DLR + 1;
    if (idx > 0) //has left sub tree
    {
        n->left = createNode();
        rebuildTreeImpl(n->left, newDLR, LDR, idx);
    }
    if (idx < length - 1) //right sub tree
    {
        n->right = createNode();
        rebuildTreeImpl(n->right, newDLR + idx, LDR + idx + 1, length - idx - 1);
    }
}
tree* rebuildTree(char* DLR, char* LDR, size_t length)
{
    tree* t = createTree();
    node* n = createNode();
    t->root = n;
    rebuildTreeImpl(n, DLR, LDR, length);
    return t;
}
int main()
{
    char DLR[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I' };
    char LDR[] = { 'B', 'C', 'A', 'E', 'D', 'G', 'H', 'F', 'I' };
    static_assert(sizeof(DLR) == sizeof(LDR), "mismatch");
    tree* t = rebuildTree(DLR, LDR, sizeof(DLR));
    traverseTree(t);
    destroyTree(t);
    return 0;
}