Instantly share code, notes, and snippets.

@caljim caljim/test.c
Created Jan 17, 2013

Embed
What would you like to do?
Simple Ternary Search Tree Implement for C
#include "trident.h"
int main(void)
{
ROOT = create_node(' ',YES);
printf("ROOT addr:%X\n",ROOT);
char* a = "he";
insert_node(a,ROOT);
insert_node("你好",ROOT);
insert_node("中国",ROOT);
insert_node("你妈好",ROOT);
insert_node("中华人民",ROOT);
printf("find 'hong' at %x\n",find_node("hong"));
printf("find 'ab' at %x\n",find_node("ab"));
print_words_with_prefix("h");
print_words_with_prefix("");
return 0;
}
#GDB的用法戳这里 http://fanqiang.chinaunix.net/program/other/2006-07-14/4834.shtml
#静态编译的知识戳这里 http://blog.163.com/jiangh_1982/blog/static/1219505200971413544680/
#include "trident.h"
Node* create_node (char w, enum ntype t)
{
Node *_node = (struct Node*)malloc(sizeof (struct Node));
_node->word = w;
_node->lChild = NULL;
_node->mChild = NULL;
_node->rChild= NULL;
_node->type = t;
return _node;
}
Node* insert_node (const char* string, Node* node)
{
int i = strlen(string);
if(NULL == node)
node = create_node(string[0], NO);
if(string[0] < node->word)
node->lChild = insert_node(string, node->lChild);
else if(string[0] > node->word)
node->rChild = insert_node(string, node->rChild);
else {
if(i == 1) {
node->type = YES;
return node;
} else
node->mChild = insert_node(++string,node->mChild);
}
return node;
}
struct Node* find_node(const char* string)
{
int i = 0;
Node* _node = ROOT;
while(i < strlen(string)) {
if(NULL == _node)
break;
if(string[i] < _node->word)
_node = _node->lChild;
else if(string[i] > _node->word)
_node = _node->rChild;
else {
if(i++ == strlen(string) - 1 && _node->type == YES)
return _node;
else
_node = _node->mChild;
}
}
return NULL;
}
struct Node* find_node2(const char* string)
{
int i = 0;
Node* _node = ROOT;
while(i < strlen(string)) {
if(NULL == _node)
break;
if(string[i] < _node->word)
_node = _node->lChild;
else if(string[i] > _node->word)
_node = _node->rChild;
else {
if(i++ == strlen(string) - 1)
return _node;
else
_node = _node->mChild;
}
}
return NULL;
}
void deep_search(const char* pattern, Node* start)
{
if(start->type != NO)
printf("FOUND:%s%c\n",pattern,start->word);
if(start->lChild != NULL)
deep_search(pattern, start->lChild);
if(start->rChild != NULL)
deep_search(pattern, start->rChild);
if(start->mChild != NULL) {
char *_pattern = (char *)malloc(strlen(pattern) + 2);
sprintf(_pattern,"%s%c",pattern,start->word);
deep_search(_pattern,start->mChild);
}
}
void print_words_with_prefix (const char* pattern)
{
Node* current = find_node2(pattern);
if(NULL == current)
printf("no words with prefix %s\n",pattern);
else {
deep_search(pattern,current->mChild);
}
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
enum ntype {NO,YES};
typedef struct Node {
char word;
struct Node* lChild;
struct Node* rChild;
struct Node* mChild;
enum ntype type;
}Node;
Node* ROOT;
Node* create_node (char w, enum ntype t);
Node* insert_node(const char* string, Node * node);
Node* find_node(const char* string);
void print_words_with_prefix(const char* pattern);
@caljim

This comment has been minimized.

Copy link
Owner Author

caljim commented Jan 17, 2013

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment