DS(Tree)

#include <bits/stdc++.h>
using namespace std;

#define MAX 20

typedef struct BTNode {
    char data;
    struct BTNode* lchild;
    struct BTNode* rchild;
} * BiTree;

void createBiTree(BiTree* t) {
    char s;
    BiTree q;
    cout << endl;
    cout << " Please input data :( Withdraw from use #)";
    s = getchar();
    if (s == '#') {
        *t = nullptr;
        return;
    }
    q = (BiTree)malloc(sizeof(struct BTNode));
    if (q == nullptr) {
        cout << " memory allocation failed !" << endl;
        exit(0);
    }
    q->data = s;
    *t = q;
    createBiTree(&q->lchild);  // Recursively build the left subtree 
    createBiTree(&q->rchild);  // Recursively build right subtree 
}

void PreOrder(BiTree p) {
    if (p != nullptr) {  // Traversing a binary tree in order 
        cout << setw(5) << p->data;
        PreOrder(p->lchild);
        PreOrder(p->rchild);
    }
}

void InOrder(BiTree p) {
    if (p != nullptr) {  // Middle order ergodic binary tree 
        InOrder(p->lchild);
        cout << setw(5) << p->data;
        InOrder(p->rchild);
    }
}

void PostOrder(BiTree p) {
    if (p != nullptr) {  // Then traverse the binary tree 
        PostOrder(p->lchild);
        PostOrder(p->rchild);
        cout << setw(5) << p->data;
    }
}

void Preorder_n(BiTree p) {  // A non recursive algorithm for preorder traversal 
    BiTree stack[MAX], q;
    int top = 0, i;
    for (i = 0; i < MAX; ++i) {
        stack[i] = NULL;  // Initialization stack 
    }
    q = p;
    while (q != NULL) {
        cout << setw(5) << p->data;
        if (q->rchild != NULL) {
            stack[top++] = q->rchild;
        }
        if (q->lchild != NULL) {
            q = q->rchild;
        } else if (top > 0) {
            q = stack[--top];
        } else {
            q = nullptr;
        }
    }
}

void release(BiTree t) {  // Free up binary tree space 
    if (t != NULL) {
        release(t->lchild);
        release(t->rchild);
        free(t);
    }
}

int main(int argc, char* argv[]) {
    BiTree t = NULL;
    createBiTree(&t);
    cout << endl;
    cout << " Preorder traversal tree is :" << endl;
    PreOrder(t);
    cout << endl;
    cout << " The middle order traversal tree is :" << endl;
    InOrder(t);
    cout << endl;
    cout << " The postorder traversal tree is :" << endl;
    PostOrder(t);
    cout << endl;
    cout << " First, we traverse the sequence ( Non recursive ):" << endl;
    Preorder_n(t);
    release(t);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define MAX 21

typedef struct {
    char data;   // Node values 
    int weight;  // Node weight 
    int parent;  // Parent node 
    int left;    // Left node 
    int right;   // Right node 
} huffnode;

typedef struct {
    char cd[MAX];
    int start;
} huffcode;

int main(int argc, char** argv) {
    huffnode ht[2 * MAX];
    huffcode hcd[MAX], d;
    int i, k, f, l, r, n, c, m1, m2;
    cout << " Element number :";
    cin >> n;
    for (i = 1; i <= n; ++i) {
        cout << " The first " << i << " Elements => Node values :";
        cin >> ht[i].data;
        cout << " The weight :";
        cin >> ht[i].weight;
    }
    for (i = 1; i <= 2 * n - 1; ++i) {
        ht[i].parent = ht[i].left = ht[i].right = 0;
    }
    for (i = n + 1; i <= 2 * n - 1; ++i) {
        m1 = m2 = 32767;
        l = r = 0;
        for (k = 1; k <= i - 1; ++k) {
            if (ht[k].parent == 0) {
                if (ht[k].weight < m1) {
                    m2 = m1;
                    r = 1;
                    m1 = ht[k].weight;
                    l = k;
                } else if (ht[k].weight < m2) {
                    m2 = ht[k].weight;
                    r = k;
                }
                ht[1].parent = i;
                ht[r].parent = i;
                ht[i].weight = ht[1].weight + ht[r].weight;
                ht[i].left = 1;
                ht[i].right = r;
            }
        }
    }
    for (i = 1; i <= n; ++i) {
        d.start = n + 1;
        c = i;
        f = ht[i].parent;
        while (f != 0) {
            if (ht[f].left == c) {
                d.cd[--d.start] = '0';
            } else {
                d.cd[--d.start] = '1';
            }
            c = f;
            f = ht[f].parent;
        }
        hcd[i] = d;
    }

    cout << " Output Huffman code :" << endl;
    for (i = 1; i <= n; ++i) {
        cout << setw(5) << ht[i].data;
        for (k = hcd[i].start; k <= n; ++k) {
            cout << setw(5) << hcd[i].cd[k];
        }
        cout << endl;
    }

    return 0;
}