Advanced Search

Return to Snippet

Revision: 38720
at January 6, 2011 09:34 by josipl
Initial Code 
#include <iostream>
#include <string>
#define MAX_ELEMENTS 100000

using namespace std;

struct node {
  string label;
  int child, sibling;
};

struct tree {
  node nodes[MAX_ELEMENTS];
  int root;
};

tree *tree_init(int root) {
  tree *T = new tree;
  T->root = root;
  T->nodes[root].child =  -1;
  T->nodes[root].sibling =  -1;

  return T;
}

node *node_init(int n, string label, int child, int sibling, tree *T) {
  node *x = new node;
  x->label = label;
  x->child = child;
  x->sibling = sibling;
  T->nodes[n] = *x;

  return x;
}

string node_label(int n, tree *T) {
  return T->nodes[n].label;
}

void node_set_label(int n, const string label, tree *T) {
  T->nodes[n].label = label;
}

int tree_root(tree *T) {
  return T->root;
}

int tree_parent(int n, tree *T) {
  if(n == T->root)
    return -1;

  for(int m = 0; m < MAX_ELEMENTS; m++)
    if(T->nodes[m].child == n)
      return m;
    else if(T->nodes[m].sibling == n)
      return tree_parent(m, T);

  return -1;
}

int tree_first_child(int n, tree *T) {
  return T->nodes[n].child;
}

int tree_next_sibling(int n, tree *T) {
  return T->nodes[n].sibling;
}

int tree_insert_node(int n, int N, tree *T) {
  node link = T->nodes[n];
  if(link.child == -1) {
    link.child = N;
    return n;
  }

  while(link.sibling != -1)
    link = T->nodes[link.sibling];

  link.sibling = N;
  return n;
}

void tree_delete_node(int n, tree *T, bool destructive) {
  node N = T->nodes[n];
  if(destructive) {
    if(N.child != -1)
      tree_delete_node(N.child, T, true);
    if(N.sibling != -1)
      tree_delete_node(N.sibling, T, true);
  }

  delete &N;
}

void tree_delete_node(int n, tree *T) {
  node N = T->nodes[n];
  if(N.child != -1)
    tree_delete_node(N.child, T, true);

  int parentN = tree_parent(n, T);
  if(parentN == -1)
    return;

  node parent = T->nodes[parentN];
  if(parent.child == n)
    parent.child = N.sibling;
  else {
    node prev = T->nodes[parent.child];
    while(prev.sibling != n)
      prev = T->nodes[prev.sibling];
    prev.sibling = N.sibling;
  }

  delete &N;
}
Initial URL 

                                

                                                            

                                    

                                        

                                        Initial Description
                                        

                                    

                                    

                                

                                                            

                                    

                                        

                                        Initial Title
                                        

                                    

                                    
Opcenito stablo

                                

                                                            

                                    

                                        

                                        Initial Tags
                                        

                                    

                                    

                                

                                                            

                                    

                                        

                                        Initial Language
                                        

                                    

                                    
C++