I've to simulate exactly a recursive algorithm with an iterative one.
Assuming that I have a binary search tree that contains only a key and two references at his right and left child I want to do this count:
CountOddRec(T)
ret = 0
if T != NIL then
if T->key % 2 = 1 then
ret = T->key
rsx = CountOddRec(T->sx);
rdx = CountOddRec(T->dx);
ret = ret + rsx + rdx;
return ret
Basically my idea is to use the general scheme of iterative binary tree visit to do that:
VisitIter(T)
last = NIL
curr = T
stk = NULL
while (curr != NIL || stk != NIL) do
if curr != NIL then
//Pre-order visit
stk = push(stk, curr)
next = curr->sx
else
curr = Top(stk)
if (last != curr-> dx) then
//In-order visit
if (last != curr-> dx && curr->dx != NULL) then
next = curr->dx
else
//Post-order visit
stk = pop(stk)
next = NIL
last = curr
curr = next
Now I know that this one should be in Pre-order block:
if T->key % 2 = 1 then
ret = T->key
The rsx =
assignment should be in-order, and rdx =
assignment and last block should be in post-order.
Now here I'm stuck, I ask if someone could help me to understand how finish the algorithm.
This is my first attempt that should work:
CountOddIter(T)
last = NIL
curr = T
stk = NULL //stack
Sret = NULL //stack
Srsx = NULL //stack
ret = 0
while (curr != NIL || stk != NIL) do
ret = 0
if curr != NIL then
//Pre-order block
if (curr->key % 2 == 1) then
ret = curr->key
Sret = push(Sret, ret)
stk = push(stk, curr)
next = curr->sx
else
curr = Top(stk)
if (last != curr-> dx) then
//In-order block
Srsx = push(Srsx, pop(Sret))
if (last != curr-> dx && curr->dx != NULL) then
next = curr->dx
else
//Post-order block
rdx = pop(Sret)
rsx = pop(Srsx)
r = pop(Sret)
ret = rdx + rsx + r
Sret = push(Sret, ret)
stk = pop(stk)
next = NIL
last = curr
curr = next
This solutions works if I assume that a pop on an empty stack returns 0. Any other suggestions? Improvements? Is it really correct? Please can I have some feedback? Many thanks
Working code (main.c):
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#include "stack_int.h"
#include "tree.h"
int countOddRic(tree_p T){
int ret = 0;
if(T != NULL){
if(T->key % 2 == 1){
ret = T->key;
}
int rsx = countOddRic(T->left);
int rdx = countOddRic(T->right);
ret = ret + rsx + rdx;
}
return ret;
}
int countOddIte(tree_p T){
tree_p curr = T;
tree_p next = NULL;
tree_p last = NULL;
stack *S = init_stack(100);
stack_int *Sret = init_stackInt(100);
stack_int *Srsx = init_stackInt(100);
int ret = 0;
while(curr != NULL || !isEmptyStack(S)){
ret = 0;
if(curr != NULL){
//printf("pre-order: %d\n", curr->key);
if(curr->key % 2 == 1){
ret = curr->key;
}
Sret = pushInt(Sret, ret);
S = push(S, curr);
next = curr->left;
}else{
curr = top(S);
if(last != curr->right){
//printf("in-order: %d\n", curr->key);
Srsx = pushInt(Srsx, popInt(Sret));
}
if(last != curr->right && curr->right != NULL){
next = curr->right;
}else{
//printf("post-order: %d\n", curr->key);
int rdx = popInt(Sret);
int rsx = popInt(Srsx);
int r = popInt(Sret);
ret = rdx + rsx + r;
Sret = pushInt(Sret, ret);
pop(S);
next = NULL;
}
}
last = curr;
curr = next;
}
printf("\nRet = %d\n", ret);
}
int main(void){
tree_p T = NULL;
insert(&T, 54);
insert(&T, 12);
insert(&T, 46);
insert(&T, 78);
insert(&T, 6);
insert(&T, 434);
insert(&T, 44);
insert(&T, 4);
insert(&T, 552);
insert(&T, 216);
insert(&T, 47);
insert(&T, 892);
insert(&T, 74);
insert(&T, 62);
insert(&T, 414);
insert(&T, 4442);
insert(&T, 86);
insert(&T, 4618);
insert(&T, 798);
insert(&T, 74);
insert(&T, 554);
insert(&T, 45);
insert(&T, 776);
insert(&T, 98);
insert(&T, 36);
insert(&T, 211);
insert(&T, 24);
printf("Count: %d\n", countOddRic(T));
countOddIte(T);
return 0;
}
stack.c:
#include "stack.h"
stack *init_stack(int size) {
stack *S = (stack*) malloc(sizeof(stack));
if (S == NULL) {
exit(-1);
}
S->size = size;
S->array = (tree_p*) malloc(size * sizeof(tree_p));
if (S->array == NULL) {
exit(-1);
}
S->last = 0;
return S;
}
int isEmptyStack(stack *S) {
return S->last == 0;
}
int isFullStack(stack *S) {
return S->last == S->size - 1;
}
stack *push(stack *S, tree_p elem) {
if (isFullStack(S))
return S;
S->last++;
S->array[S->last] = elem;
return S;
}
tree_p pop(stack *S) {
if (isEmptyStack(S))
return ERR_EMPTY_STACK;
S->last--;
return S->array[S->last + 1];
}
tree_p top(stack *S) {
if (isEmptyStack(S))
return ERR_EMPTY_STACK;
return S->array[S->last];
}
void freeStack(stack *S){
if(S != NULL){
free(S->array);
S->array = NULL;
free(S);
}
}
void printStack(stack *S) {
if (isEmptyStack(S))
return;
tree_p e = pop(S);
printf("|%d", e->key);
printStack(S);
push(S, e);
}
stack.h:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "tree.h"
#ifndef STACK_H_
#define STACK_H_
#define ERR_EMPTY_STACK NULL
typedef struct {
int size;
int last;
tree_p *array;
} stack;
stack *init_stack(int size);
void fillRandomStack(stack *S, int nElem);
int isEmptyStack(stack *S);
int isFullStack(stack *S);
stack *push(stack *S, tree_p elem);
tree_p pop(stack *S);
tree_p top(stack *S);
void freeStack(stack *S);
void printStack(stack *S);
#endif
stack_int.c:
#include "stack_int.h"
stack_int *init_stackInt(int size) {
stack_int *S = (stack_int*) malloc(sizeof(stack_int));
if (S == NULL) {
exit(-1);
}
S->size = size;
S->array = (int*) calloc(size + 1, sizeof(int));
if (S->array == NULL) {
exit(-1);
}
return S;
}
void fillRandomStackInt(stack_int *S, int nElem){
while(!isFullStackInt(S) && nElem > 0){
pushInt(S, rand() % 500);
nElem--;
}
}
int isEmptyStackInt(stack_int *S) {
return S->array[0] == 0;
}
int isFullStackInt(stack_int *S) {
return S->array[0] == S->size - 1;
}
stack_int *pushInt(stack_int *S, int elem) {
if (isFullStackInt(S))
return S;
S->array[0]++;
S->array[S->array[0]] = elem;
return S;
}
int popInt(stack_int *S) {
if (isEmptyStackInt(S))
return ERR_EMPTY_STACK_INT;
S->array[0]--;
return S->array[S->array[0] + 1];
}
int topInt(stack_int *S) {
if (isEmptyStackInt(S))
return ERR_EMPTY_STACK_INT;
return S->array[S->array[0]];
}
void freeStackInt(stack_int *S){
if(S != NULL){
free(S->array);
S->array = NULL;
free(S);
}
}
stack_int.h:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#ifndef STACK_INT_H_
#define STACK_INT_H_
#define ERR_EMPTY_STACK_INT 0
typedef struct {
int size;
int *array;
} stack_int;
stack_int *init_stackInt(int size);
void fillRandomStackInt(stack_int *S, int nElem);
int isEmptyStackInt(stack_int *S);
int isFullStackInt(stack_int *S);
stack_int *pushInt(stack_int *S, int elem);
int popInt(stack_int *S);
int topInt(stack_int *S);
void freeStackInt(stack_int *S);
void printStackInt(stack_int *S);
#endif
tree.c:
#include "tree.h"
void insert(tree_p *tree, int val) {
tree_p temp = NULL;
if(!(*tree)) {
temp = (tree_p) malloc(sizeof(tree));
temp->left = temp->right = NULL;
temp->key = val;
*tree = temp;
return;
}
if(val < (*tree)->key)
insert(&(*tree)->left,val);
else if(val > (*tree)->key)
insert(&(*tree)->right,val);
else
return;
}
tree.h
#include <stdlib.h>
#include <stdio.h>
#ifndef TREE_H_
#define TREE_H_
typedef struct tree {
int key;
struct tree *left;
struct tree *right;
} tree, *tree_p;
void insert(tree_p *tree, int val);
#endif