Advanced Search

Opcenito stablo

/ Published in: C++
Save to your folder(s)

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. #include <iostream>
  2. #include <string>
  3. #define MAX_ELEMENTS 100000
  4.  
  5. using namespace std;
  6.  
  7. struct node {
  8.   string label;
  9.   int child, sibling;
  10. };
  11.  
  12. struct tree {
  13.   node nodes[MAX_ELEMENTS];
  14.   int root;
  15. };
  16.  
  17. tree *tree_init(int root) {
  18.   tree *T = new tree;
  19.   T->root = root;
  20.   T->nodes[root].child =  -1;
  21.   T->nodes[root].sibling =  -1;
  22.  
  23.   return T;
  24. }
  25.  
  26. node *node_init(int n, string label, int child, int sibling, tree *T) {
  27.   node *x = new node;
  28.   x->label = label;
  29.   x->child = child;
  30.   x->sibling = sibling;
  31.   T->nodes[n] = *x;
  32.  
  33.   return x;
  34. }
  35.  
  36. string node_label(int n, tree *T) {
  37.   return T->nodes[n].label;
  38. }
  39.  
  40. void node_set_label(int n, const string label, tree *T) {
  41.   T->nodes[n].label = label;
  42. }
  43.  
  44. int tree_root(tree *T) {
  45.   return T->root;
  46. }
  47.  
  48. int tree_parent(int n, tree *T) {
  49.   if(n == T->root)
  50.     return -1;
  51.  
  52.   for(int m = 0; m < MAX_ELEMENTS; m++)
  53.     if(T->nodes[m].child == n)
  54.       return m;
  55.     else if(T->nodes[m].sibling == n)
  56.       return tree_parent(m, T);
  57.  
  58.   return -1;
  59. }
  60.  
  61. int tree_first_child(int n, tree *T) {
  62.   return T->nodes[n].child;
  63. }
  64.  
  65. int tree_next_sibling(int n, tree *T) {
  66.   return T->nodes[n].sibling;
  67. }
  68.  
  69. int tree_insert_node(int n, int N, tree *T) {
  70.   node link = T->nodes[n];
  71.   if(link.child == -1) {
  72.     link.child = N;
  73.     return n;
  74.   }
  75.  
  76.   while(link.sibling != -1)
  77.     link = T->nodes[link.sibling];
  78.  
  79.   link.sibling = N;
  80.   return n;
  81. }
  82.  
  83. void tree_delete_node(int n, tree *T, bool destructive) {
  84.   node N = T->nodes[n];
  85.   if(destructive) {
  86.     if(N.child != -1)
  87.       tree_delete_node(N.child, T, true);
  88.     if(N.sibling != -1)
  89.       tree_delete_node(N.sibling, T, true);
  90.   }
  91.  
  92.   delete &N;
  93. }
  94.  
  95. void tree_delete_node(int n, tree *T) {
  96.   node N = T->nodes[n];
  97.   if(N.child != -1)
  98.     tree_delete_node(N.child, T, true);
  99.  
  100.   int parentN = tree_parent(n, T);
  101.   if(parentN == -1)
  102.     return;
  103.  
  104.   node parent = T->nodes[parentN];
  105.   if(parent.child == n)
  106.     parent.child = N.sibling;
  107.   else {
  108.     node prev = T->nodes[parent.child];
  109.     while(prev.sibling != n)
  110.       prev = T->nodes[prev.sibling];
  111.     prev.sibling = N.sibling;
  112.   }
  113.  
  114.   delete &N;
  115. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.