Simple Ternary Search Tree Implement for C

test.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;
}

tst.c

#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);
	}
}

tst.h

#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);

wikipead http://en.wikipedia.org/wiki/Ternary_search_tree