tree 相关问题

如何添加概率来评估行为树节点？

我正在 Unity 中开发一款游戏，并决定使用 BehaviourTrees 来管理敌人 AI。 其中一名敌人有能力躲避玩家的攻击。然而，这种能力应该只发生少数

通过中序和先序遍历构造二叉树

我有以下序列： 中序：{4,2,5,1,6,3} 预购：{1,2,4,5,3,6} 我想了解如何从这些序列构建二叉树以及为什么可以用这个

如何根据“parentOf”关系对有根树进行拓扑排序？

我有一个 N 节点有根树，其节点标记为 0 到 N-1。我得到了parentOf关系，也就是说，对于每个节点i，parentOf[i]是单个节点j，使得j是i的父节点。我...

将公式作为有向树进行导航以查找符号的所有出现

在R中，公式可以看作一棵树，其中父节点位于索引[[1]]上，左右项位于后续索引中。 例如，公式 f 定义为： <- y ~ (a*...

CTreeCtrl 项目的边界矩形

过去我们使用 Stingray 树控件来描绘地图的图例。 现在我们要应用 MFC CTreeCtrl 来完成这项工作。 Stingray 控件的优点是可以轻松更改

构建红黑树过程中的问题

我在构建红黑树时遇到了问题。 insertFixUp等过程中出现分段错误。我不知道该怎么办。 #包括 #包括 我在构建红黑树时遇到了问题。 insertFixUp等过程中出现分段错误。我不知道该怎么办。 #include <stdio.h> #include <stdlib.h> #include <time.h> struct tree_node { int key; int color; struct tree_node *parent; struct tree_node *left_child; struct tree_node *right_child; }; struct tree { int cardinality; struct tree_node *root; struct tree_node *Nil; }; struct tree_node *getNewNode (int keys){ struct tree_node* newNode = (struct tree_node*) malloc(sizeof(struct tree_node)); newNode-> key = keys; newNode-> color = 0; newNode-> parent = NULL; newNode-> right_child = NULL; newNode-> left_child = NULL; return newNode; } void TreeLeftRotate(struct tree *T, struct tree_node *x) { struct tree_node *y = x->right_child; x->right_child = y->left_child; if (y->left_child != T->Nil) { y->left_child->parent = x; } if (x->parent == T->Nil) { T->root = y; } else if (x == x->parent->left_child) { x->parent->left_child = y; } else { x->parent->right_child = y; } y->left_child = x; x->parent = y; } struct tree_node* BSTTreeMinimum(struct tree_node *x){ if(x->left_child== NULL){ return x;} else{ return BSTTreeMinimum(x->left_child);} }; struct tree_node *BSTTreeSearch(struct tree_node *x, int k){ if ((x==NULL)||(x->key=k)){ return x; } if(k<=x->key){ return BSTTreeSearch(x->left_child, k); } else { return BSTTreeSearch(x->right_child, k); } } void BSTTreeInsert(struct tree *T, struct tree_node *z) { struct tree_node *x = NULL; struct tree_node *y = NULL; x = T->root; while (x!=NULL){ y=x; if(z->key <= x->key){ x=x->left_child; } else { x=x->right_child; } } z->parent =y; if(y==NULL){ T->root = z; } if((y!=NULL)&&(z->key <= y->key)) { y->left_child = z; } if((y!=NULL)&&(z->key > y->key)) { y->right_child = z; } } void BSTTreeTransplant(struct tree *T, struct tree_node *u, struct tree_node *v){ if (u->parent==NULL){ T->root = v; } if((u->parent != NULL)&&(u=u->parent->left_child)){ T->root = v; } if((u->parent!=NULL)&&(u=u->parent->right_child)){ u->parent->right_child=v; } if(v!=NULL){ v->parent = u->parent; } } void BSTTreeDelete(struct tree *T, struct tree_node *z){ struct tree_node *y = NULL; if (z->left_child == NULL){ BSTTreeTransplant(T,z,z->right_child); } if((z->left_child != NULL) && (z->right_child == NULL)){ BSTTreeTransplant(T,z,z->left_child); } if((z->left_child != NULL)&&(z->right_child != NULL)){ y=BSTTreeMinimum(z->right_child); if (y->parent != z){ BSTTreeTransplant(T,y,y->right_child); y->right_child = z->right_child; y->right_child->parent =y; } BSTTreeTransplant(T,z,y); y->left_child = z->left_child; y->left_child->parent = y; } } void TreeRightRotate(struct tree *T, struct tree_node *x) { struct tree_node *y = x->left_child; x->left_child = y->right_child; if (y->right_child != T->Nil) { y->right_child->parent = x; } if (x->parent == T->Nil) { T->root = y; } else if (x == x->parent->right_child) { x->parent->right_child = y; } else { x->parent->left_child = y; } y->right_child = x; x->parent = y; } void RBTreeInsertFixUpLeft(struct tree*T, struct tree_node *z){ struct tree_node *y = z->parent->parent->right_child; if (y->color == 1) { z->parent->color = 0; y->color = 0; z->parent->parent->color=1; z=z->parent->parent; } else{ if (z==(z->parent->right_child)){ z=z->parent; TreeLeftRotate(T,z); } z->parent->color = 0; z->parent->parent->color=1; TreeRightRotate(T,z->parent->parent); }; }; void RBTreeInsertFixUpRight(struct tree*T, struct tree_node *z){ struct tree_node *y = z->parent->parent->left_child; if (y->color == 1) { z->parent->color = 0; y->color = 0; z->parent->parent->color=1; z=z->parent->parent; } else{ if (z==z->parent->left_child){ z=z->parent; TreeRightRotate(T,z); } z->parent->color = 0; z->parent->parent->color=1; TreeLeftRotate(T,z->parent->parent); }; }; void RBTreeInsertFixup(struct tree *T, struct tree_node *z){ while (z->parent->color = 1){ //segmentation fault if(z->parent == z->parent->parent->left_child){ RBTreeInsertFixUpLeft(T,z); } else { RBTreeInsertFixUpRight(T,z); } } T->root->color=0; }; void RBTreeInsert(struct tree *T, struct tree_node *z) { struct tree_node *y = T->Nil; struct tree_node *x = T->root; while (x!=T->Nil){ y=x; if (z->key < x->key) { x=x->left_child; } else { x=x->right_child; } } z->parent = malloc(sizeof(struct tree_node)); z->parent = y; if (y==T->Nil){ T->root = z; } if((y!=T->Nil)&&(z->key < y->key)){ y->left_child=z; } if ((y!=T->Nil)&&(z->key >= y->key)){ y->right_child = z; } z->left_child = T->Nil; z->right_child = T->Nil; z->color = 1; RBTreeInsertFixup(T,z); }; void RBTransplant(struct tree *T, struct tree_node *u, struct tree_node *v){ if (u->parent == T->Nil) { T->root = v; } else if (u==u->parent->left_child){ u->parent->left_child = v; } else { u->parent->right_child=v; } v->parent = u->parent; }; void RBDeleteFixup(struct tree *T, struct tree_node *x){ if (x == x->parent->left_child){ struct tree_node *w = x->parent->right_child; if (w->color == 1) { w->color = 0; x->parent->color = 1; TreeLeftRotate(T,x->parent); w=x->parent->right_child; } if (w->left_child->color == 0 && w->right_child->color == 0){ w->color = 1; x = x->parent; } else if (w->right_child->color == 0){ w->left_child->color = 0; w->color = 1; TreeRightRotate(T,w); w = x->parent->right_child; } w->color = x->parent->color; x->parent->color = 0; w->right_child->color = 0; TreeLeftRotate(T,x->parent); x=T->root; } else { struct tree_node *w = x->parent->left_child; if (w->color == 1) { w->color = 0; x->parent->color = 1; TreeRightRotate(T,x->parent); w=x->parent->left_child; } if (w->right_child->color == 0 && w->left_child->color == 0){ w->color = 1; x = x->parent; } else if (w->left_child->color == 0){ w->right_child->color = 0; w->color = 1; TreeLeftRotate(T,w); w = x->parent->left_child; } w->color = x->parent->color; x->parent->color = 0; w->left_child->color = 0; TreeRightRotate(T,x->parent); x=T->root; } } void RBDelete(struct tree *T, struct tree_node *z) { struct tree_node *x = NULL; struct tree_node *y = z; int y_original_color = y->color; if (z->left_child == T->Nil){ x = z->right_child; RBTransplant(T,z,z->right_child); } else if(z->right_child == T->Nil){ x = z->left_child; RBTransplant(T,z,z->left_child); } else { y=BSTTreeMinimum(z->right_child); y_original_color = y->color; x = y->right_child; if (y->parent == z){ x->parent = y; } else { RBTransplant(T,y,y->right_child); y->right_child = z->right_child; y->right_child->parent = y; } RBTransplant(T,z,y); y->left_child = z->left_child; y->left_child->parent = y; y->color = z->color; } if (y_original_color == 0) { RBDeleteFixup(T, x); } } double SingleExperimentBST (int max_keys, int max_search, int max_delete, int max_instances) { int t_tot = 0; int t_elapsed = 0; clock_t t_start = 0, t_final = 0 ; int A[max_keys]; int B[max_search]; int C[max_delete]; struct tree_node *z =NULL; z = malloc(sizeof(struct tree_node)); struct nodo *x =NULL; x = malloc(sizeof(struct tree_node)); for (int instance= 1; instance <= max_instances; instance++){ for (int j= 0; j < max_keys; j++){ A[j] = 1 + rand() % 100; } struct tree *T= NULL; T=malloc(sizeof(struct tree)); t_start = clock(); for (int key =1; key<= max_keys; key++){ struct tree_node* z = getNewNode(A[key]); z->parent = malloc(sizeof(struct tree_node)); z->parent = getNewNode(A[key]); BSTTreeInsert(T, z); } for (int key = 1; key<= max_search; key++){ B[key] = 1 + rand() % 100; int k= B[key]; struct tree_node *x = T->root; BSTTreeSearch(x, k) ; } for (int key = 1; key<= max_delete; key++){ C[key] = 1 + rand() % 100; struct tree_node* z1 = getNewNode(C[key]); BSTTreeDelete(T, z1) ; } t_final = clock(); t_elapsed = t_final - t_start; t_tot = t_tot + t_elapsed; T->root =NULL; } t_final= t_tot / max_keys; return t_final; } double SingleExperimentRBT (int max_keys, int max_search, int max_delete, int max_instances){ int t_tot = 0; int t_elapsed =0; clock_t t_start = 0, t_end = 0 ; int A[max_keys]; int B[max_search]; int C[max_delete]; struct tree_node *z =NULL; z = malloc(sizeof(struct tree_node)); struct tree_node *x =NULL; x = malloc(sizeof(struct tree_node)); for (int instance = 1; instance <=max_instances; instance++){ struct tree *T= NULL; T=malloc(sizeof(struct tree)); for (int j= 0; j < max_keys; j++){ A[j] = 1 + rand() % 100; } t_start = clock(); for (int key=1; key<=max_keys; key++) { struct tree_node *z = getNewNode(A[key]); RBTreeInsert(T, z); } for (int key = 1; key<= max_search; key++){ B[key] = 1 + rand() % 100; int k= B[key]; struct tree_node *x = T->root; BSTTreeSearch(x, k) ; } for (int key = 1; key<= max_delete; key++){ C[key] = 1 + rand() % 100; struct tree_node* z1 = getNewNode(C[key]); RBDelete(T, z1) ; } t_end = clock(); t_elapsed = t_end + t_elapsed; t_tot = t_tot + t_elapsed; T->root = NULL; } return t_tot/max_keys; } void Experiment(int min_keys, int max_keys){ time_t t; int step = 10; int max_instances = 5; int percentage_search = 60; for (int keys = min_keys; keys<=max_keys; keys+step){ srand((unsigned) time(&t)); double max_search = keys*percentage_search/100; double max_delete = keys - max_search; double timeBST =SingleExperimentBST(keys, max_search, max_delete, max_instances); srand((unsigned) time(&t)); double timeRBT = SingleExperimentRBT(keys, max_search, max_delete, max_instances); printf("%f\t\t\t%f\n", timeBST, timeRBT); t = t + 1; } } int main() { int min_key = 10; int max_key = 150; Experiment(min_key, max_key); return 0; } 此代码应该计算 RB Tree 上的插入、删除、研究操作的时间，但它不打印任何内容。代码相当复杂，如果还有其他错误，请告诉我。编译期间它不显示任何内容。调试时出现分段错误。 while (z->parent->color = 1){ //segmentation fault 这是作业=，而不是比较==。 此代码有错误 void RBTreeInsertFixUpLeft(struct tree*T, struct tree_node *z){ struct tree_node *y = z->parent->parent->right_child; if (y->color == 1) { 有可能刚插入一个节点时，父节点存在，但叔节点可能不存在。它可能为 NULL。所以 y 可能为 NULL 但是如果为 NULL，则节点的“颜色”为黑色，如果为非 NULL，则节点->颜色 您应该编写一个返回节点颜色的内联函数 bool IsBlack(const tree_node *curr) { return (curr == NULL || curr->color == 0); } 并使用它。 请注意，删除修正也会发生相同的情况。 如果删除一个叶子黑色节点并且它有父节点，那么兄弟节点存在并且必须是黑色的，它是一个真正的节点。但兄弟姐妹的孩子可能不存在，但他们应该被视为黑人。您的删除代码必须考虑到这一点。

寻找阿伯茨福德树木服务的建议

我在阿伯茨福德，需要聘请阿伯茨福德树木服务公司来解决我院子里的一些与树木相关的问题。有人可以推荐阿伯茨福德地区可靠的树木服务吗？ 我很具体...

给定n个叶子生成所有可能的二叉树

因此，正如标题所示，任何人都拥有/知道一种算法（如果可能的话，用java）来生成所有可能的二叉树，给定叶子数量，如下面第二个链接的示例所示？ ` 不...

在 Ocaml 中检测无向图中的循环

有人知道如何检测 OCaml 中无向图中是否存在循环吗？ 这是我用于图表的类型： 输入 '图表 = { 节点：'列表； 边 : ('a * 'a * int) 列表 } ...

Reingold-Tilford 算法的步骤是什么？我该如何对其进行编程？

从演示文稿：第 3 页的图表和树中，可以直观地演示 Reigngold-Tilford 过程中发生的情况；之前它还对这个算法给出了一个模糊的总结...

叶到根的最大总和

给定一棵二叉树，找到从叶子到根的最大和路径。 https://practice.geeksforgeeks.org/problems/maximum-sum-leaf-to-root-path/1 类解决方案： def maxPathSum(自身, 根): ...

从根节点到叶节点的最长路径上的节点之和返回错误

我正在尝试解决GeeksforGeeks问题从根到叶节点的最长路径上的节点总和： 给定一个大小为 N 的二叉树。你的任务是完成函数 sumOfLongRootToLeafPath(), ...

gfg问题：从根节点到叶节点最长路径上的节点之和

类解决方案 { 班级信息 { 整数计数； 整数总和； 信息（整数计数，整数总和） { this.count=计数； this.sum=总和； } } public Info findSum(节点根,Info ans) { 如果（根==空） { ans.count=...

更改 MFC CTreeCtrl 中现有项目的位置

目前我正在试验C++ MFC的CTreeCtrl组件。我想通过使用项目的新父项将现有项目移动到树中的另一个位置。这很重要...

具有二元和一元节点的波兰表示法树（前缀）的高度

我需要获取具有二元和一元节点的波兰表示法树（前缀）的深度。这里的解决方案可以通过简单地预先反转表达式字符串来实现；但是，如果前缀表示...

如何在Python中将文件的行读取为列表而不是字符串

我有一个文件，其中每一行都是树的列表表示。例如，文件中的这些行之一是： [1, [[2,[]], [3, [ [5,[]], [6, [ [10,[]] ] ] ]], [4, [ [7,[]], [8 ,[]], [9,[]] ]] ]...

树数据结构中“阶”和“度”有什么区别

B 树定义 他们在以下情况中使用“顺序”术语： 根据Knuth的定义，m阶B树是满足以下性质的树： 1. 每个节点最多有 m 个子节点。 ......

使用Python脚本将树状数据集插入MySQL

你好，我对 MySQL 很陌生。我在将大型“树状”数据插入数据库时遇到一些问题。 数据：我有一个包含各种主题、子主题、子子主题和......的树状数据

获取 XML 文件的节点属性名称

我正在尝试获取 XML 文件的属性节点的名称。我能够读取节点和属性值，但不能读取名称。 在此 xml 示例中： 我正在尝试获取 XML 文件的属性节点的名称..我能够读取节点和属性值，但不能读取名称。 在此 xml 示例中： <?xml version="1.0" encoding="UTF-8"?> -<Root> -<body surname="Rott" name="Pig"> <city>London</city> </body> -<body surname="Lip" name="Jack"> <city>Los Angeles</city> </body> -<body colorB="White" colorA="Yellow"> <city>Rome</city> </body> </Root> 我正在尝试获取“姓氏”、“姓名”、“colorB”、“colorA”等。 我做了这个 vb.net 示例，但我无法获取属性（需要类似 reader.GetNameAttribute 命令的东西）？存在吗？ 我尝试做这个程序： OpenFileDialog1.Multiselect = False OpenFileDialog1.ShowDialog() Dim fileName As String = Path.GetFileName(OpenFileDialog1.FileName) Dim filePath As String = OpenFileDialog1.FileName Me.Text = filePath Dim docXML As New XmlDocument docXML.Load(filePath) Dim reader As XmlNodeReader = New XmlNodeReader(docXML) While reader.Read Dim lettura = reader.NodeType Dim valueA As String Dim attr_name As String = "none" 'attr_name = reader.GetNameAttribute() here ? get name attribute???? valueA = reader.Name If reader.HasAttributes Then Dim conteggio As Integer = reader.AttributeCount For x = 0 To conteggio - 1 MsgBox("Node is: " + valueA + " and has an attribute named: " + attr_name + " = " + reader.GetAttribute(x)) Next End If End While 看看这是否有帮助 Dim xe As XElement ' = XElement.Load(filePath) 'for production ' for testing used literal xe = <Root> <body surname="Rott" name="Pig"> <city>London</city> </body> <body surname="Lip" name="Jack"> <city>Los Angeles</city> </body> <body colorB="White" colorA="Yellow"> <city>Rome</city> </body> </Root> Dim nms As New List(Of String) nms = (From el In xe...<body> From attr In el.Attributes Select attr.Name.LocalName).ToList

如何制作产品类别树？

我使用fastapi、postgresDB，我需要创建一个返回产品类别树的端点 类 CategoryTree(BaseModel): id：整数 名称：str 子项：列表[CategoryTree] |无=无...