Tag: 树

C中的Cons Cell数据结构

在构建一个小型Scheme解释器的早期阶段，我是C的新手。 对于项目的这一部分，我正在尝试构建一个简单的cons单元数据结构。 它应该采取像这样的列表 (abc) 并在内部表示如下： [ ][ ] -> [ ][ ] -> [ ][/] | | | ABC 为了测试它是否正常工作，我有一个打印function来回显输入。 这是不起作用的代码： #include #include #include #include “lexer.h” #include “parse.h” char token[20]; struct conscell { char *data; struct conscell *first, *rest; }; void S_Expression () { /* function from lexer to receive input a split into tokens […]

最大functionc树高

在c中有一个最大函数，所以我可以做这样的事情来计算树高：或者可能有更好的方法来计算树高。 int height(struct node *tree) { if (tree == NULL) return 0; return 1 + max(height (tree->left), height (tree->right)); } 如果是的话包括我需要什么？ 目前我收到此错误： dict-tree.o：在函数’height’中： /home/ex10/dict-tree.c:36：对’max’的未定义引用

将二叉树转换为链接列表

我正在尝试从二叉树创建链接列表。 问题是，是否可以使用简单的链表而不是双链表？ 我试过这个： typedef struct arvbin* ABin; typedef struct arvbin { int value; ABin right; ABin left; } arvb; typedef struct slist { int value; struct slist* next; } *SList; void preorder(ABin tree, SList *l) { if(tree) { (*l)->value = tree->value; (*l)->next = (SList) malloc(sizeof(struct slist)); l = &((*l)->next); printf(“tese\n”); preorder(tree->left, l); preorder(tree->right, l); } […]

如何在c中创建一个n-ary树

#include #include struct node{ char *word; int depth, children; struct node **child; }; typedef struct node node; node *createTree(); node *createNode(char *word,int depth); int main(int argv,char *argc[]){ node *root,*current_node; root=createNode(“root”,0); char *array[]={“string1″,”string2″,”string3”}; current_node=root; printf(“root has been created with word: %s \n”,current_node->word); int i; for (i=0; ichild[i]=createNode(array[i],(current_node->depth)+1); current_node->children++; printf(“%s has been inserted to the tree\n”,current_node->word); } […]

没有递归的遍历树和C中的堆栈

如何在没有C（无C ++）递归的情况下有效地遍历树的每个节点？ 假设我有该树的以下节点结构： struct Node { struct Node* next; /* sibling node linked list */ struct Node* parent; /* parent of current node */ struct Node* child; /* first child node */ } 这不是功课。 我首先喜欢深度。 我不喜欢需要额外的数据结构（例如堆栈）。 我更喜欢速度方面最有效的方式（而不是空间）。 您可以更改或添加Node结构的成员来存储其他信息。

如何生成最大不平衡的AVL树

我编写了一个AVL树的C语言库作为通用分类容器 。 出于测试目的，我希望有一种方法来填充树，使其最大程度地不平衡，即，使其具有包含的节点数的最大高度。 AVL树具有很好的属性，如果从空树开始，按升序（或降序）顺序插入节点，则树始终是完全平衡的（即，对于给定数量的节点，它具有其最小高度）。 从空树T 0开始，为每个节点数n生成精确平衡的AVL树T n的一个整数键序列就是简单的 k 1 = 0 k n + 1 = k n +1，即k n = n-1 我正在寻找一个（希望很简单的）整数键序列，当插入最初空的树T 0时 ，生成最大不平衡的AVL树T 0 ，…，T n 。 我也感兴趣的是一种解决方案，其中只有最后一棵树T n最大程度地不平衡（节点数n将是算法的参数）。 满足约束的解决方案 max（k 1 ，…，k n ） – min（k 1 ，…，k n ）+1≤2n 是可取的，但不是严格要求的。 4 n而不是2 n的关键范围可能是合理的目标。 我无法在互联网上找到关于通过插入生成最大高度的AVL树的任何内容。 当然，我正在寻找的生成树的序列将包括所有所谓的Fibonacci树，它们是具有最小节点数的给定深度的AVL树。 有趣的是，英语维基百科甚至没有在AVL树的文章中提到斐波那契树（也不是斐波那契数字！），而德语维基百科有一篇非常好的文章完全致力于它们。 但对于我的问题，我仍然处于黑暗中。 C语言有点刺耳的黑客是受欢迎的。

如何实现具有延迟传播的分段树？

我在互联网上搜索了关于Segment树的实现但是在懒惰传播时没有发现任何东西。 之前有一些关于堆栈溢出的问题，但他们专注于解决SPOJ的一些特殊问题。 虽然我认为这是具有伪代码的分段树的最佳解释，但我需要使用延迟传播来实现它。 我发现以下链接： http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Segment_Trees 除了上面的链接，一些博客也在那里，但他们都提供了相同的线程参考。 例 应用这种数据结构的一个例子就是说，我已经获得了从1到n的一系列数字。 现在我执行一些操作，例如向特定范围添加一些常数或从特定范围中减去一些常数。 执行操作后，我应该告诉给定数字中的最小和最大数字。 一个明显的解决方案是逐个对给定范围内的每个数字执行加法或减法。 但是，在没有执行任何操作的情况下，这是不可行的。 更好的方法是使用具有延迟传播技术的分段树。 它表示不是单独对每个数字执行更新操作，而是跟踪所有操作，直到完成所有操作。 然后最后执行更新操作以获得该范围内的最小和最大数量。 实际数据示例 假设我给出了范围[1,10]，这意味着数字是1,2,3,4,5,6,7,8,9,10。 现在假设我执行的操作将范围[3,6]中的数字减少4，所以现在数字看起来像1,2，-1,0,1,2,7,8,9,10。 现在我执行另一个操作，将范围[5,9]中的数字增加1，因此数字现在看起来像1,2，-1,0,2,3,8,9,10,10。 现在，如果我要求您告诉我最大和最小数字，那么答案将是： Maximum = 10 Minimum = -1 这只是一个简单的例子。实际问题可能包含数千个这样的加法/减法操作。我希望现在很清楚。 这是我到目前为止所理解的，但我想互联网上没有统一的链接，可以更好地解释概念和实现。 任何人都可以给出一些很好的解释，包括在段树中延迟传播的伪代码吗？ 谢谢。

使用C ++进行2D段/四叉树解释

PS这可能不重复。 我搜索了SO并确保我没有得到我想要的东西。 我是一个ACM问题求解器，最近我学习了线性数组的Segment Tree和延迟传播的Segment Tree。 但是我遇到了一些需要2D段树的问题（在某处被称为Quad树）。 但我找不到任何好的教程。 我搜索了SO并找到了一个链接http://e-maxx.ru/algo/segment_tree这是一个俄语教程。 我需要在2D段树上用源代码（最好用C ++）做一些很好的解释。 需要注意的是，我非常了解典型的分段树。

OpenCL – 将树复制到设备内存

我在C代码中实现了二进制搜索树。 我的每个树节点都是这样的： typedef struct treeNode { int key; struct treeNode *right; struct treeNode *left; } treeNode_t; 由主人制作的树的构造。 设备所做树的查询。 现在，让我们假设我已经在主机内存中完成了我的树构建。 我想将树的根复制到我的设备的内存中。 复制树的根本它是不够的。 因为右\左子不在设备内存中。 这是个问题。 所以，我的问题是将整个树复制到设备内存的最简单方法是什么？

知识树中的段错误

我在c中实现了一个可以从文件中读取的知识树。 我在newStr函数中遇到了一个seg错误。 我无法使用此问题测试其余代码。 我对c没有多少经验。 任何帮助将不胜感激。 我的.c文件#include #include #include“animal.h”#include #include /*returns a new node for the given value*/ struct Node * newNode (char *newValue) { struct Node * tree; tree = (struct Node*)malloc(sizeof(struct Node)); tree -> value = newStr(newValue); return tree; } /* returns a new string with value passed as an argument*/ char * newStr […]