基数树与二叉查找树和Trie树很相似。它像BST一样是二叉的,向左表示0而不是BST的小于,
而向右则表示1而不是大于。它像Trie一样共享相同的结点来保存字符串中相同的前缀,从而
节省了空间,但它不像Trie那样每个结点有很多孩子(可以是26个,表示a到z),它用来处理
只包含0和1的字符串。
基数树和Trie都用来保存和排列字符串,那么现在来看看字典序,关于字典序有两条规则:
1. 字符串长度相同时,从左向右逐个字符比较。如011 < 100。
2. 字符串长度不同时,长度长的在字典序中值更大。如100 < 1011。
因此,根结点 < 左子树结点 < 右子树结点。
#include <stdio.h>
#include <stdlib.h>
typedef struct RadixNode {
struct RadixNode *lchild, *rchild;
char *str;
} RadixNode;
void radix_insert(RadixNode *node, char *str)
{
int i;
for (i = 0; str[i] != '\0'; i++) {
if (str[i] == '0') {
if (node->lchild == NULL)
node->lchild = calloc(sizeof(RadixNode), 1);
node = node->lchild;
}
else {
if (node->rchild == NULL)
node->rchild = calloc(sizeof(RadixNode), 1);
node = node->rchild;
}
}
node->str = str;
}
void radix_preorder_walk(RadixNode *node)
{
if (node != NULL) {
if (node->str != NULL)
printf("%s\n", node->str);
radix_preorder_walk(node->lchild);
radix_preorder_walk(node->rchild);
}
}
int main(void)
{
RadixNode *root = malloc(sizeof(RadixNode));
radix_insert(root, "1011");
radix_insert(root, "10");
radix_insert(root, "011");
radix_insert(root, "100");
radix_insert(root, "0");
radix_preorder_walk(root);
return 1;
}
分享到:
相关推荐
根据算法导论第12章二叉查找树内容编写,有详细的注释和测试程序
用C++实现的最优二叉查找树,简单,明了,是数据结构里经典必学算法,初学者适用
科大算法实验2红黑树和二叉查找树 支持彩色打印
在学习算法过程中自己的代码实现,与大家分享交流。版权所有:miracledan
算法导论 第二十五章 答案 算法导论 第二十五章 答案 算法导论 第二十五章 答案
运用c语言,贪心算法构造最优二叉查找树。
使用C++实现最优二叉查找树,对正在学习算法的同学应该挺有帮助的
C++编写的查找算法,用二叉排序树查找,是在VC++6.0上实现的
算法导论第二十四章答案 算法导论第二十四章答案 算法导论第二十四章答案
最近在研究数据结构这本书,自己动手实现的一个二叉查找排序树的类BinSortTree,实现数据的插入,查找,删除,层序遍历,中序遍历等操作,熟悉数据结构的朋友都知道,根据二叉排序树的定义,中序遍历后得到的序列...
设计一个算法程序,使得该程序从二叉检索树中删除一个结点,并仍然保持二叉检索树的特性不变 实验要求: 创建一棵二叉检索树,然后用中序遍历查找要删除的结点的后继结点
最优二叉查找树,包含习题15.5-1算法,为算法导论上的习题。
代码里有二叉排序树插入操作递归算法,二叉排序树插入操作非递归算法,二叉排序树删除操作,创建二叉排序树,二叉排序树查找递归算法,二叉排序树查找非递归算法
C#,自平衡二叉查找树(AVL Tree)的算法与源代码 自平衡二叉查找树(AVL Tree)中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL...
二叉查找树的插入、删除、遍历和查找等操作的C++实现,二叉查找树采用泛型结构
数据结构课程设计-综合查找算法(顺序查找、折半查找、二叉排序树、哈希表) 可以在Microsoft Visual C++ 上运行没有错误 包括论文word文档,答辩的ppt等
二叉查找与递归二叉查找算法
老师给的资源,对于数据结构入门的学生很有帮助的。
用C#实现的二叉查找树的算法,实现了算法。