Cài đặt trie

code:


#include<algorithm>
#include<iostream>

using namespace std;

class trie
{
private:
struct nodeTrie
{
char c; // ki tu cua nut hien tai
bool eow; // danh dau nut nay het mot tu
int prefixes; // cho biet co bao nhieu nut truoc nut nay
nodeTrie* edge[26]; //
}*root;
void preorder_display(nodeTrie* leaf);
void destroy_trie(nodeTrie* leaf);
void delete_node(nodeTrie* leaf);

public:
trie();
~trie();

void insert_word(char* w);
void delete_word(char* w);
bool search_word(char* w);
void display();

};

trie::trie()
{
root = new nodeTrie();
root->c = '\0';
root->prefixes = 0;
root->eow = false;
for(int i = 0; i < 26; i++)
root->edge[i] = NULL;
}
void trie::destroy_trie(nodeTrie* leaf)
{
for(int i = 0; i < 26; i++)
if(leaf->edge[i] != NULL) destroy_trie(leaf->edge[i]);
delete(leaf);
}
trie::~trie()
{
destroy_trie(root);
}

void trie::insert_word(char* w)
{
nodeTrie* leaf = root;
while(*w != '\0')
{
int index = toupper(*w) - 'A';
if(leaf->edge[index] == NULL)
{
nodeTrie* child = new nodeTrie();
child->c = *w;
child->eow = false;
child->prefixes = 1;
for(int i = 0; i < 26; i++)
child->edge[i] = NULL;
leaf->edge[index] = child;
leaf = child;
}
else
{
leaf = leaf->edge[index];
leaf->prefixes++;
}
w++;
}
leaf->eow = true;
}
bool trie::search_word(char * w)
{
nodeTrie* leaf = root;
while(*w != '\0')
{
int index = toupper(*w) - 'A';
if(leaf->edge[index] == NULL) return false;
leaf = leaf->edge[index];
w++;
}
return leaf->eow;
}
void trie::delete_word(char* w)
{
nodeTrie* leaf = root;
while(*w != '\0')
{
int index = toupper(*w) - 'A';
if(leaf->edge[index] == NULL) return;
else if(leaf->edge[index]->prefixes == 1)
{
destroy_trie(leaf->edge[index]);
leaf->edge[index] = NULL;
return;
}
else
{
//if(leaf->count > 1) leaf->count--;
leaf=leaf->edge[index];
}
w++;
}
}
void trie::preorder_display(nodeTrie* leaf)
{
if(leaf == NULL) return;
cout << leaf->c << ":" << leaf->eow << ":" << leaf->prefixes << endl;
for(int i=0; i< 26; i++)
if(leaf->edge[i] != NULL)
preorder_display(leaf->edge[i]);
}
void trie::display()
{
preorder_display(root);
}


int main()
{
trie mytrie;
    char *s[] = {"tree","trie","algo","assoc","all","also","ass"};
    for(int i=0;i<sizeof(s)/sizeof(*s);i++)
    {
        mytrie.insert_word(s[i]);
    }

    mytrie.display();

    if(mytrie.search_word("all") == true) cout << "all exist" << endl;
    else cout << "all do not exist" << endl;

    mytrie.delete_word("all");

    if(mytrie.search_word("all") == true) cout << "all exist" << endl;
    else cout << "all do not exist" << endl;

    mytrie.display();

if(mytrie.search_word("also") == true) cout << "all exist" << endl;
    else cout << "all do not exist" << endl;

system("pause");

return 0;
}

Binary Tree

#include<iostream>

using namespace std;

struct node
{
int data;
node* left;
node* right;
};

class btree
{
public:
btree();
~btree();

void insert (int data);
node* search(int data);
void destroy_tree();
int size();
int minValue();
int maxValue();
int maxDepth();
void printTree();
void printPostorder();
void mirror();


private:
void destroy_tree(node* leaf);
void insert(int data, node* leaf);
node* search(int data, node* leaf);
int size(node* leaf);
int minValue(node* leaf);
int maxValue(node* leaf);
int maxDepth(node* leaf);
void printTree(node* leaf);
void printPostorder(node* leaf);
void mirror(node* leaf);



node* root;
};

btree::btree()
{
root = NULL;
}
btree::~btree()
{
destroy_tree();
}
void btree::destroy_tree(node* leaf)
{
if(leaf != NULL)
{
destroy_tree(leaf->left);
destroy_tree(leaf->right);
delete leaf;
}
}
void btree::insert(int data,node* leaf)
{
if(data < leaf->data)
{
if(leaf->left != NULL)
insert(data, leaf->left);
else
{
leaf->left = new node;
leaf->left->data = data;
leaf->left->left = NULL;
leaf->left->right = NULL;
}
}
else
{
if(leaf->right != NULL)
insert(data, leaf->right);
else
{
leaf->right = new node;
leaf->right->data = data;
leaf->right->left = NULL;
leaf->right->right = NULL;
}
}
}
node* btree::search(int data, node* leaf)
{
if(leaf != NULL)
{
if(data == leaf->data)
return leaf;
if(data < leaf->data)
return search(data, leaf->left);
return search(data, leaf->right);
}
return NULL;
}
void btree::insert(int data)
{
if(root != NULL)
insert(data, root);
else
{
root = new node;
root->data = data;
root->left = NULL;
root->right = NULL;
}
}
node* btree::search(int data)
{
return search(data, root);
}
void btree::destroy_tree()
{
destroy_tree(root);
}
int btree::size(node* leaf)
{
if(leaf == NULL)
return 0;
return size(leaf->left) + 1 + size(leaf->right);
}
int btree::size()
{
if(root == NULL)
return 0;
return size(root);
}
int btree::minValue(node* leaf)
{
while(leaf->left != NULL)
{
leaf = leaf->left;
}
return leaf->data;
}
int btree::minValue()
{
if(root == NULL)
return -1;
return minValue(root);
}
int btree::maxDepth(node* leaf)
{
if(leaf == NULL)
return 0;
int leftDepth = maxDepth(leaf->left);
int rightDepth = maxDepth(leaf->right);
if(leftDepth > rightDepth)
return leftDepth + 1;
return rightDepth + 1;
}
int btree::maxDepth()
{
return maxDepth(root);
}
int btree::maxValue(node* leaf)
{
while(leaf->right != NULL)
{
leaf = leaf->right;
}
return leaf->data;
}
int btree::maxValue()
{
if(root == NULL)
return -1;
return maxValue(root);
}
void btree::printTree(node* leaf)
{
if(leaf == NULL) return;
printTree(leaf->left);
printf("%d ",leaf->data);
printTree(leaf->right);
}
void btree::printTree()
{
printTree(root);
}
void btree::printPostorder(node* leaf)
{
if(leaf == NULL) return;
printPostorder(leaf->left);
printPostorder(leaf->right);
printf("%d ",leaf->data);
}

void btree::printPostorder()
{
printPostorder(root);
}

void btree::mirror(node* leaf)
{
if(leaf == NULL) return;
node* temp;

//Tiep tuc voi subtree
mirror(leaf->left);
mirror(leaf->right);

//trao doi con trai va con phai cua node nay.
temp = leaf->left;
leaf->left = leaf->right;
leaf->right = temp;
}

void btree::mirror()
{
mirror(root);
}





int main()
{
btree b;
b.insert(4);
b.insert(2);
b.insert(5);

if(b.search(5)==NULL)
cout << "NO" << endl;
else
cout << "YES" << endl;

cout << b.size() << endl;

cout << b.minValue() << endl;

b.printTree();

cout << endl;

b.printPostorder();

cout << endl;

b.mirror();

b.printTree();

cout << endl;
system("pause");
return 0;
}

Dijoint set

Các phép toán trên Dijoint set:

• MakeSet(x): Khởi tạo một tập con 1 phần tử {x}.
• MergeSet(x,y): Hợp nhất hai tập con chứa x, y lại.
• FindSet(x):Tìm gốc của tập hợp chứa x.

Cài đặt:

• Gọi p[x] là nút cha của x.
• rank[x] là chiều sâu của nút x khi đi từ gốc.
• Khởi tạo, p[x] = x, rank[x] = 0, mọi x.
• MergerSet(x,y):
• px = FindSet(x);
• py = FindSet(y);
• if(rank[px] > rank[py]) p[py] = px;
• else p[px] = py;
• if(rank[px]==rank[py]) rank[py] = rank[py] + 1;
• FindSet(x):
• if(x!=p[x]) return FindSet(p[x]);
• return x;

Code:


int p[101];
int rank[101];

void MakeSet(int NN)
{
for(int i=1;i<=NN;i++)
{
p[i]=i; rank[i]=0;
even[i]=1;
}
}
int FindSet(int x)
{
if(x!=p[x])return FindSet(p[x]);
return x;
}

void MergerSet(int x,int y)
{
int px = FindSet(x);
int py = FindSet(y);
if(rank[px]>rank[py])
p[py]=px;
else
p[px]=py;
if(rank[py]==rank[px])
rank[py]+=1;
}


Tham khảo:
http://en.wikipedia.org/wiki/Disjoint-set_data_structure
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure