三叉树演示
唉，yuma的百分贴是等不到了，估计他也没打算为这个东西出100分。代码写好两天了。作为一个简单的算法示例，对我来说它没有保存价值。对于连指针都折腾不明白的新手而言，它又过于复杂，很难说能从中学到什么。
算了，既然都写好了，扔了有点浪费。发上来吧。有一个能看懂就算我没白发。
也不打算用分数来吸引人。希望参与这贴的朋友为的是学点知识，而不是蹭点分。
感谢随风的指正，目前已经修改两处错误。
程序代码：#include<stdio.h>
#include<malloc.h>
typedef struct ternary_tree_node
{
char key;
int value;
struct ternary_tree_node * left;
struct ternary_tree_node * mid;
struct ternary_tree_node * right;
}TERNARY_NODE, * TERNARY_TREE;
void ternary_tree_clear(TERNARY_TREE * tree);
void ternary_tree_insert(TERNARY_TREE * tree, char * string, int value);
void ternary_tree_delete(TERNARY_TREE * tree, char * string);
void ternary_tree_travel(TERNARY_TREE tree);
int ternary_tree_search(TERNARY_TREE tree, char * string);
int ternary_tree_node_count(TERNARY_TREE tree);
int main()
{
TERNARY_TREE tt = NULL;
ternary_tree_insert(&tt, "abc", 1);
ternary_tree_insert(&tt, "abeh", 2);
ternary_tree_insert(&tt, "abdi", 3);
ternary_tree_insert(&tt, "abfj", 4);
ternary_tree_travel(tt);
printf("nodes count = %d\n\n", ternary_tree_node_count(tt));
ternary_tree_delete(&tt, "abeh");
ternary_tree_travel(tt);
printf("nodes count = %d\n\n", ternary_tree_node_count(tt));
ternary_tree_clear(&tt);
return 0;
}
void ternary_tree_clear(TERNARY_TREE * tree)
{
if(*tree == NULL) return;
ternary_tree_clear(&((*tree)->left));
ternary_tree_clear(&((*tree)->mid));
ternary_tree_clear(&((*tree)->right));
free(*tree);
*tree = NULL;
}
void ternary_tree_insert(TERNARY_TREE * tree, char * string, int value)
{
TERNARY_NODE * tmp;
if(*tree == NULL)
{
tmp = (TERNARY_NODE *)malloc(sizeof(TERNARY_NODE));
tmp->key = *string;
tmp->value = 0;
tmp->left = NULL;
tmp->mid = NULL;
tmp->right = NULL;
*tree = tmp;
if(string[1] == '\0')
{
tmp->value = value;
return;
}
ternary_tree_insert(&(tmp->mid), string + 1, value);
}
else if((*tree)->key > *string)
{
ternary_tree_insert(&((*tree)->left), string, value);
}
else if((*tree)->key == *string)
{
if(string[1] == '\0')
{
(*tree)->value = value;
return;
}
ternary_tree_insert(&((*tree)->mid), string + 1, value);
}
else
{
ternary_tree_insert(&((*tree)->right), string, value);
}
}
void ternary_tree_delete(TERNARY_TREE * tree, char * string)
{
TERNARY_NODE * pl, * pr, * pt;
if(*tree == NULL) return;
if(*string == '\0') return;
if((*tree)->key > *string) ternary_tree_delete(&((*tree)->left), string);
else if((*tree)->key < *string) ternary_tree_delete(&((*tree)->right), string);
else if(string[1] == '\0') (*tree)->value = 0;
else ternary_tree_delete(&((*tree)->mid), string + 1);
if((*tree)->mid != NULL || (*tree)->value != 0) return;
pl = (*tree)->left;
pr = (*tree)->right;
if(pl == NULL) pl = pr;
else if(pr != NULL)
{
for(pt = pl; pt->right != NULL; pt = pt->right);
pt ->right = pr;
}
free(*tree);
*tree = pl;
}
void ternary_tree_travel_sub(TERNARY_TREE tree, char * string, int deep)
{
if(tree == NULL) return;
ternary_tree_travel_sub(tree->left, string, deep);
string[deep] = tree->key;
if(tree->value != 0)
{
string[deep + 1] = '\0';
printf("%s <%d>\n", string, tree->value);
}
ternary_tree_travel_sub(tree->mid, string, deep + 1);
ternary_tree_travel_sub(tree->right, string, deep);
}
void ternary_tree_travel(TERNARY_TREE tree)
{
char tmp[1024];
ternary_tree_travel_sub(tree, tmp, 0);
}
int ternary_tree_search(TERNARY_TREE tree, char * string)
{
if(tree == NULL) return 0;
if(*string == '\0') return 0;
if(tree->key > *string) return ternary_tree_search(tree->left, string);
if(tree->key < *string) return ternary_tree_search(tree->right, string);
if(string[1] == '\0') return tree->value;
return ternary_tree_search(tree->mid, string + 1);
}
int ternary_tree_node_count(TERNARY_TREE tree)
{
int count;
if(tree == NULL) return 0;
count = ternary_tree_node_count(tree->left);
count += ternary_tree_node_count(tree->mid);
count += ternary_tree_node_count(tree->right);
return count + 1;
}[ 本帖最后由 beyondyf 于 2012-8-7 21:59 编辑 ]
