I insert new vertices in the tree as follows: left <root <= right. By the "maximum sub-tree" I mean that which is the highest.
My program works as follows:
1. Traversing tree using BFS start by visiting the root
2. Examine the subtree in each visited vertex to see if it contains duplicates, as follows:
a) check if the right son is not the same as the father
b) if not, check next left sons
3. If it contains, enqueue its children for traversal.
4. If not, enter the new subtree in the list
5. Find the subtree in the list which is the highest.
The function that checks if the tree has duplicates works correctly. However, I have a problem with the operations on the list. E.g. function print (which prints the list) doesn't work, so I believe I'm not creating the list properly.
Code:
typedef struct vertex {
int klucz;
struct vertex *left;
struct vertex *right;
} vertex, *pvertex;
typedef struct NondupeSubtree {
struct vertex *root;
struct NondupeSubtree *next;
} NondupeSubtree, *pNondupeSubtree;
int AnyDupes_temp(pvertex v,int k);
int AnyDupes(pvertex t){
if(t==NULL)
return 0;
int k = t->klucz;
pvertex v = t->right;
if(AnyDupes_temp(v,k))
return 1;
}
int AnyDupes_temp(pvertex v,int k){
if (v==NULL)
return 0;
if (v->klucz == k)
return 1;
if(v->klucz > k)
return AnyDupes_temp(v->left,k);
}
int AnyDupes_total(pvertex root)
{
int rear, front;
pvertex *queue = createQueue(&front, &rear);
pvertex temp_vertex = root;
while (temp_vertex)
{
if(AnyDupes(temp_vertex))
return 1;
// Enqueue left child
if (temp_vertex->left)
enQueue(queue, &rear, temp_vertex->left);
// Enqueue right child
if (temp_vertex->right)
enQueue(queue, &rear, temp_vertex->right);
temp_vertex = deQueue(queue, &front);
}
}
/* Print all the elements in the linked list */
void print(pNondupeSubtree head) {
pNondupeSubtree current_node = head;
while(current_node){
printf("%d ", current_node->root->klucz);
current_node = current_node->next;
}
}
/* Add a new node to the top of a list */
pNondupeSubtree insert_top(pvertex t, pNondupeSubtree head) {
pNondupeSubtree new_node;
new_node = (pNondupeSubtree ) malloc(sizeof(NondupeSubtree));
new_node->root = t;
new_node->next= head;
head = new_node;
return head;
}
pvertex MaxHeightTree(pNondupeSubtree head)
{
pNondupeSubtree p, pmax;
pmax = head;
if(head)
for(p = head->next; p; p = p->next)
if(Height(p->root) > Height(pmax->root))
pmax = p;
return pmax->root;
}
pvertex Function(pvertex t, pNondupeSubtree pq)
{
int rear, front;
pvertex *queue = createQueue(&front, &rear);
pvertex temp_vertex = t;
while (temp_vertex){
if(!AnyDupes(temp_vertex)){
pq->next = insert_top(temp_vertex, pq);
pq=pq->next;
temp_vertex = deQueue(queue, &front);
}
else{
if (temp_vertex->left)
enQueue(queue, &rear, temp_vertex->left);
if (temp_vertex->right)
enQueue(queue, &rear, temp_vertex->right);
/*Dequeue vertex and make it temp_vertex*/
temp_vertex = deQueue(queue, &front);
}
}
MaxHeightTree(pq);
}
int main()
{
pNondupeSubtree head;
head = (pNondupeSubtree)malloc(sizeof(NondupeSubtree));
pvertex t = NULL;
DisplayTree(Funkcja(t, head));
return 0;
}