如何在二叉树中插入字符？
如何在二叉树中插入字符？
提问于 2020-12-09 21:14:22
我正在用C语言做一个二叉树的摩尔斯电码解码器，我已经设法按字母顺序插入了所有字符，但我希望它们按照我在char *characters[]中使用的顺序，所以它将是：
*
/ \
E T
/ \ / \
I A N M
...我怎么能为树插入字符，使其变成这样呢？
typedef struct BTree {
char value[100];
struct BTree *dot, *dash;
} BTree, *tree_ptr;
BTree *insert(BTree *root, char morse[200]) {
int j;
char *code[100];
if (root == NULL) {
BTree *new_node = (BTree*) malloc(sizeof(BTree));
new_node->dot = NULL;
new_node->dash = NULL;
strcpy(new_node ->value, morse);
root = new_node;
}
else if (strcmp(morse, root->value) < 0) {
root ->dot = insert(root->dot, morse);
} else if (strcmp(morse, root->value) > 0){
root ->dash = insert(root->dash, morse);
} else {
}
return root;
}
void inorder ( tree_ptr root )
{
if ( root == NULL ){
return ;
} else {
inorder ( root ->dot );
printf ("%s ", root ->value ) ;
inorder ( root ->dash ) ;
}
}
void preorder ( tree_ptr root )
{
if ( root == NULL )
return ;
printf ("%s ", root ->value ) ;
preorder ( root ->dot );
preorder ( root ->dash ) ;
}
void postorder ( tree_ptr root )
{
if ( root == NULL )
return ;
postorder ( root ->dot ) ;
postorder ( root ->dash ) ;
printf ("%s ", root ->value ) ;
}
int main(void) {
int i;
BTree *root = NULL;
char *characters[] = {"E", "T", "I", "A", "N", "M", "S", "U", "R", "W", "D", "K", "G", "O", "H", "V", "F", "L", "P", "J", "B", "X", "C", "Y", "Z", "Q" ,"\0"};
char *morsecode[] = {".", "-", "..", ".-", "-.", "--","...","..-",".-.",".--", "-..","-.-","--.","---
","....","...-","..-.", ".-..",".--.",".---","-...", "-..-","-.-.","-.--","-
-..","--.-", "\0"};
for (i = 0; strcmp( characters[i], "\0") != 0; i++){
root = insert(root, characters[i]);
}
/*inorder(root);*/
preorder(root);
/*postorder(root);*/
return 0;
}最后，我会使用一个点向左移动，一个破折号向右移动来遍历树，如果我做得不正确，请
回答 2
Stack Overflow用户
回答已采纳
发布于 2020-12-09 22:35:08
您当前的代码实际上对字符使用了字典顺序的代码，因此您通常会获得一个排序的字母表。如果要构建与每个字母的摩尔斯电码一致的二叉树，则必须将摩尔斯电码传递给插入函数并使用它。
下面是一个可能的函数：
// Insert letter *c (as a C string) having morse code morse into root
BTree *insert(BTree *root, const char *c, const char *morse) {
if (root == NULL) { // Node does not exist
BTree *new_node = (BTree*) malloc(sizeof(BTree));
new_node->dot = NULL;
new_node->dash = NULL;
new_node->value[0] = '\0'; // initialize as an empty letter
root = new_node;
}
if (*morse == '\0') { // reached the end of the morse code
strncpy(root->value, c, sizeof (root->value)); // current root receives the letter
}
else if (*morse == '.') { // process for a dot
root ->dot = insert(root->dot, c, morse + 1); // step in the morse code
} else if (*morse == '-') {
root ->dash = insert(root->dash, c, morse + 1);
} else {
fprintf(stderr, "Wrong character in morse: %c\n", *morse);
}
return root;
}当然，您必须相应地调用它：
for (i = 0; strcmp( characters[i], "\0") != 0; i++){
root = insert(root, characters[i], morsecode[i]);
}Stack Overflow用户
发布于 2020-12-10 00:12:49
我会用稍微不同的方式来做：
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
void * xcalloc(size_t count, size_t size);
struct btree {
char v;
struct btree *dot, *dash;
} btree, *tree_ptr;
struct btree *
insert(struct btree **root, char *morse, char v)
{
struct btree *b = *root;
if( b == NULL ){
b = *root = xcalloc(1, sizeof **root);
}
if( *morse ){
assert( morse[0] == '-' || morse[0] == '.' );
b = insert( *morse == '-' ? &(*root)->dash : &(*root)->dot,
morse + 1, v);
}
if( *morse == '\0' ){
b->v = v;
}
return b;
}
void
preorder(struct btree *root)
{
if( root ){
printf("%c", root->v) ;
preorder(root->dot);
preorder(root->dash);
}
}
char *alphamorse[] = {
".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", /* A - H */
"..", ".---", "-.-", ".-..", "--", "-.", /* I - M */
"---", ".--.", "--.-", ".-.", "...", "-", /* N - T */
"..-", "...-", ".--", "-..-", "-.--", "--.." /* W - Z */
};
char *nummorse[]={
"-----", ".----", "..---", "...--", "....-",
".....", "-....", "--...", "---..", "----."
};
int
main(void)
{
int i;
struct btree *root = NULL;
/* char characters[] = "ETIANMSURWDKGOHVFLPJBXCYZQ"; */
insert(&root, alphamorse[4], 'A' + 4);
for(i = 0; i < 26; i++ ){
insert(&root, alphamorse[i], 'A' + i);
}
for(i = 0; i < 10; i++ ){
insert(&root, nummorse[i], '0' + i);
}
preorder(root);
putchar('\n');
return 0;
}
void *
xcalloc(size_t count, size_t size)
{
void *r = calloc(count, size);
if( r == NULL ){
perror("calloc");
exit(EXIT_FAILURE);
}
return r;
} 页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65217545
复制相关文章
相似问题
腾讯云开发者
