[AISP] LV4

#include <stdio.h>
#include <stdlib.h>

// Maximum stack size
#define MAX_SIZE 100

struct cvor{ char x; struct cvor *left, *right; }; //Deklaracija strukture
struct Stack
    {
        int size;
        int top;
        struct cvor* *array;
    };
//struct cvor{ char x; struct cvor *left, *right; }; //Deklaracija strukture
    void ubaci(struct cvor *r, struct cvor *p){
    if ((r->right == NULL) && (p->x > r->x)){ r->right = p; }
    //Funkcija za dodavanje èvora u stablo
    else if ((r->right != NULL) && (p->x > r->x)){ ubaci(r->right, p); }
    //Sluèaj kada je vrijednost novog èvora veæa od nadreðenog.
        //Sluèaj kada je vrijednost novog èvora veæa od nadreðenog.
        if ((r->left == NULL) && (p->x < r->x)){ r->left = p; }
    //Sluèaj kada je vrijednost novog èvora manja od nadreðenog.
        else if ((r->left != NULL) && (p->x < r->x)){ ubaci(r->left, p); }
    //Sluèaj kada je vrijednost novog èvora manja od nadreðenog.
} //zavrsetak funkcije ubaci()

    int isFull(struct Stack* stack)
    {
        return stack->top - 1 == stack->size;
    }

    int isEmpty(struct Stack* stack)
    {
        return stack->top == -1;
    }

    void push(struct Stack* stack, struct cvor* node)
    {
        if (isFull(stack))
            return;
        stack->array[++stack->top] = node;
    }

    struct cvor* pop(struct Stack* stack)
    {
        if (isEmpty(stack))
            return NULL;
        return stack->array[stack->top--];
    }

    struct cvor* peek(struct Stack* stack)
    {
        if (isEmpty(stack))
            return NULL;
        return stack->array[stack->top];
    }

    struct Stack* createStack(int size)
    {
        struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
        stack->size = size;
        stack->top = -1;
        stack->array = (struct cvor**) malloc(stack->size * sizeof(struct cvor*));
        return stack;
    }

    void preOrder(struct cvor* root){ if (root == NULL) return;   else{ printf("%c ", root->x);   preOrder(root->left);   preOrder(root->right); } }


    void inOrder(struct cvor* root){ if (root == NULL) return;   else{ inOrder(root->left);   printf("%c ", root->x);   inOrder(root->right); } }


    void postOrderIterative(struct cvor* root)
        {
            // Check for empty tree
            if (root == NULL)
                return;

            struct Stack* stack = createStack(MAX_SIZE);
            do
            {
                // Move to leftmost node
                while (root)
                {
                    // Push root's right child and then root to stack.
                    if (root->right)
                        push(stack, root->right);
                    push(stack, root);

                    // Set root as root's left child
                    root = root->left;
                }

                // Pop an item from stack and set it as root
                root = pop(stack);

                // If the popped item has a right child and the right child is not
                // processed yet, then make sure right child is processed before root
                if (root->right && peek(stack) == root->right)
                {
                    pop(stack);  // remove right child from stack
                    push(stack, root);  // push root back to stack
                    root = root->right; // change root so that the right
                    // child is processed next
                }
                else  // Else print root's data and set root as NULL
                {
                    printf("%c ", root->x);
                    root = NULL;
                }
            } while (!isEmpty(stack));
        }




    struct cvor* newNode(char data)
        {
            struct cvor* node = (struct cvor*) malloc(sizeof(struct cvor));
            node->x = data;
            node->left = node->right = NULL;
            return node;
        }

    int main()
    {

        struct cvor* root = NULL;
        root = newNode('i');
        struct cvor* slovo2 = newNode('m');
        struct cvor* slovo3 = newNode('e');
        struct cvor* slovo4 = newNode('p');
        struct cvor* slovo5 = newNode('r');
        struct cvor* slovo6 = newNode('e');
        struct cvor* slovo7 = newNode('z');
        struct cvor* slovo8 = newNode('i');
        struct cvor* slovo9 = newNode('m');
        struct cvor* slovo10 = newNode('e');

        ubaci(root, slovo2);
        ubaci(root, slovo3);
        ubaci(root, slovo4);
        ubaci(root, slovo5);
        ubaci(root, slovo6);
        ubaci(root, slovo7);
        ubaci(root, slovo8);
        ubaci(root, slovo9);
        ubaci(root, slovo10);

                printf("preOrder jest:\n");
        preOrder(root);
                printf("\ninOrder jest:\n");
        inOrder(root);
                printf("\npostOrder jest:\n");
        postOrderIterative(root);



        return 0;
    }

// ---------------------------------------

#include "stdafx.h"
#include <iostream>
using namespace std;

char a[8] = { 'm','a','r','k','o','c','i','t' };



struct cvor {
    char d;
    struct cvor*desni;
    struct cvor *lijevi;


};

struct cvor *stvori_cvor(char x, struct cvor *l, struct cvor *d) {
    struct cvor *t;
    t = new struct cvor;
    t->d = x;
    t->desni = d;
    t->lijevi = l;
    return t;
}

struct cvor* stvori_stablo(char*a, int i, int vel) {
    if (i >= vel) {
        return NULL;
    }

    return (stvori_cvor(a[i], stvori_stablo(a, 2 * i + 1, vel), stvori_stablo(a, 2 * i + 2, vel)));


}
//
////void ubaci(struct cvor *r, struct cvor* p) {
//
//  if ((r->desni == NULL) && (p ->d> r->d)) {
//
//      r->desni = p;
//  }
//  else if ((r->desni != NULL) && (p->d > r->d)) {
//      return ubaci(r->desni, p);
//  }
//  if ((r->lijevi == NULL) && (p->d < r->d)) {
//      r->lijevi = p;
//  }
//  else if ((r->lijevi != NULL) && (p->d < r->d)) {
//      ubaci(r->lijevi, p);
//  }
//}

void preorder(struct cvor *root) {

    if (root == NULL)return;
    else {

        cout << root->d << endl;
        preorder(root->lijevi);
        preorder(root->desni);

    }
}



void inorder(struct cvor *root) {

    if (root == NULL)return;
    else {

        inorder(root->lijevi);
        cout << root->d << endl;
        inorder(root->desni);

    }
}

void postorder(struct cvor *root) {

    if (root == NULL)return;
    else {

        postorder(root->lijevi);
        postorder(root->desni);
        cout << root->d;
    }
}


struct cvor *stog[8];
int sp = -1;

void push(struct cvor*head) {

    sp += 1;
    stog[sp] = head;

}

struct cvor*pop() {
    struct cvor*ret = stog[sp];
    --sp;
    return ret;
}

struct cvor* peek() {
    return stog[sp];

}



void Preorder(struct cvor *glava) {

    struct cvor*p = glava;
    struct cvor*p_t = glava;
    push(p);
    while (sp!=-1) {

        p_t = pop();
        cout << p_t->d << endl;
        if (p_t->desni) {
            push(p_t->desni);
        }
        if (p_t->lijevi) {
            push(p_t->lijevi);
        }

    }

}

void Inorder(struct cvor *glava) {


        cvor * p = glava;
        while (true) {
            while (p != NULL) {
                push(p);
                p = p->lijevi;
            }
            if (sp==-1) {
                break;
            }
            p = pop();
            printf("%c\n", p->d);
            p = p->desni;
        }
    }



void Postorder(struct cvor *glava) {
    struct cvor*current = NULL;

    while (sp != -1) {
        if (glava != NULL) {
            push(glava);
            glava = glava->lijevi;
        }
        else {
            struct cvor*temporary = peek();

            if (temporary->desni != NULL && current != temporary->desni) {
                glava = temporary->desni;
            }
            else {
                cout << temporary->d;
                current= pop();
            }
        }
    }
}



int main()
{
    struct cvor*me;
    me = stvori_stablo(a, 0, 8);

    Postorder(me);

    return 0;
}