我需要在Java中使用IntervalTree或RangeTree,并且无法找到具有工作删除支持的实现.
在sun.jvm.hotspot.utilities.IntervalTree中有一个内置的,但RBTree超类中的deleteNode方法指出:
/**
* FIXME: this does not work properly yet for augmented red-black
* trees since it doesn't update nodes. Need to figure out exactly
* from which points we need to propagate updates upwards.
*/
尝试从树中删除节点最终会抛出异常:
节点的最大端点未正确更新
delete在sun.jvm.hotspot.utilities.IntervalTree的子类中正确实现功能有多难？或者是否有另一个Interval Tree实现已经正确实现了这个？
目前我只是在擦除树并在每次删除时重新填充它,这远非理想(注意:在RBTree中设置DEBUGGING = false会大大加快速度).
完整的二叉树被定义为二叉树,其中除了可能是最深的之外,每个级别都被完全填充.在最深层,所有节点必须尽可能远.
我认为一个简单的递归算法将能够判断给定的二叉树是否完整,但我似乎无法弄明白.
我正在做一个从预订和顺序遍历(每个节点中的一个字符串)构建二叉树的任务,并试图围绕如何构建实际的树包裹我的大脑.
以下是关于如何实现此目标的思考过程:
我已经完成了步骤1-4,但是我不太确定如何正确构建我的树,并且想知道是否有人有任何指针.谢谢.
我想要计算叶子节点的数量:注意:不能使用全局/类级别变量我跟随算法,它工作正常.但我希望方法签名是
countLeaves(Node node)
我知道我可以重载methds并从1个args调用2 args方法sig,但是不想这样做.任何人都可以建议任何其他方法吗？
int countLeaves(Node node,int count){
if(node==null)
return 0;
if(node.left==null && node.right==null){
return 1+count;
}else{
int lc = countLeaves(node.left, count);
int total = countLeaves(node.right, lc);
return total;
}
}
请你好 - 这是我的第一个问题.= P
基本上作为夏季项目,我一直在浏览维基百科页面上的数据结构列表并尝试实现它们.我上学期参加了C++课程并发现它非常有趣,作为我实施二项式堆的最终项目 - 这也非常有趣.也许我很讨厌,但我喜欢数据结构.
无论如何,足够的背景故事.项目进展顺利,我从二叉树开始.为了更进一步,我需要创建迭代器来遍历树.我已经决定为每个遍历方法(常规迭代器和常量迭代器)创建两种类型的迭代器,我只是不知道如何做到这一点.我听说过从stl的迭代器继承,甚至使用boosts iterator_facade(这似乎是个不错的选择)
我还没有尝试编写迭代器代码,因为我不知道从哪里开始,但我确实在github上有我当前的代码.你可以在这里查看.
如果你反对github,我会粘贴相关的类定义.这些功能的实现实际上没有任何帮助,但如果您出于某种原因需要它们,请告诉我.此外,节点类具有用于迭代目的的父指针.
#ifndef __TREES_HXX
#define __TREES_HXX
#include <cstdlib> // For NULL
#include <algorithm> // for std::max
// Node class definition. These nodes are to be used for any
// tree where the structure is
// node
// /\
// left right
// /\ /\
//
// etc., basically two children.
template <typename T>
class Node
{
public:
T data_;
Node<T>* left_;
Node<T>* right_;
Node<T>* parent_; // Needed …我有两个二叉搜索树.例如,A和B.接下来,我被要求从树A中删除树B.
通过删除,我的意思是从A中删除B中存在的所有节点.注意:B不一定是A的子树.
例如:
A:
Run Code Online (Sandbox Code Playgroud)50 / \ 10 75 / / \ 1 60 90
B:
Run Code Online (Sandbox Code Playgroud)10 / \ 1 75
结果树应该是:
Run Code Online (Sandbox Code Playgroud)50 \ 60 \ 90
我想到了两种方法:
A1:
node*deleteTree(node*A,node*B);
取树B的根.从树A中删除此节点(通过正常的BSt删除方法).接下来将问题分为两部分 - B的左子树和B的右子树.对于每个子树,递归.对于左子树,占用已删除节点的节点应作为树A的根.对于右子树,已删除节点的inorder后继应作为树A的根服务器.
A2:另一种方法有点奇怪.我找到了树A的inorder和preorder遍历.使用二进制搜索和递归查找并删除树B中的所有节点(我们不修改预订).最后从inorder(剩余)和预订(未更改)重新构建我们的bst.
问题A:找到一种有效的BST方式.
问题B:为任何二叉树(不仅仅是BST)找到一种有效的方法.
我正在使用PHP(CodeIgniter)和MySQL为网站实现MLM树.我需要在数据库中实现二叉树实现.以下事项应予以考虑:
对于每个节点,左子树中子项/节点数的最小值和右子树中子项/节点的数量称为一对.对于每对,一个节点获得1个点 - 应该存储在数据库中(节点代表用户)
当创建新节点(无论在哪里)时,许多节点的对可能会递增.因此,无论何时创建节点,都应更新每个节点的点(在适用时加1)
另一个约束是每天任何节点不能超过100个点.
我还需要构建(在网页中显示)树.只显示4-5个级别.
数据库可能有100000个节点
我发现主要有4个模型用于实现MySQL,PHP中的hieararchical数据
所以我想找到一个解决方案,它将减少插入开销并成功更新所有适用节点的点数.
我已经尝试了邻接List解决方案.
node ( id, parentid, leftChildId,rightChildId,leftCount,rightCount )
userStat(id,sdate,pairs,mlmIncome)
每次插入一个节点时,我向上移动并继续递增子计数.如果新对生成,那么我也增加它并增加点...我正在使用存储过程执行这些操作.
我在嵌套集上选择此解决方案的原因是:对于插入的每个节点,要为嵌套集更新的节点数总是大于邻接列表.
虽然构建树的速度不仅仅是插入.嵌套集更好地构建树.
我在正确的方向吗？请帮忙 !
Thnx提前!
作为Java赋值的一部分,我必须使用输入算术表达式并将其存储在二叉树中.
除了我在表达式的字符串中读取的部分并将其存储在二叉树中之外,我已完成了赋值所需的所有操作.
我创建了一个名为BinaryTree的类.它唯一的领域是一个名为root的treenode.这个treenode被定义为BinaryTree中的内部类.它有3个字段,一个通用数据字段,以及两个类型为BinaryTree的子节点(左和右).
我很难在一个表达式中定义一个读取算法
(5*(2 + 3)^ 3)/ 2
并将其存储在这样的树中
/
^ 2
* 3
5 +
2 3
任何人都可以帮助算法吗？
我试图理解删除二叉搜索树的递归方法是如何工作的.我在许多地方遇到的代码如下所示:
void destroy_tree(struct node *leaf)
{
if( leaf != 0 )
{
destroy_tree(leaf->left);
destroy_tree(leaf->right);
free( leaf );
}
}
我无法理解a)如果例程中没有返回,它是如何工作的？b)当free()被调用时？我想想,例如,这样一棵树:
10
/ \
6 14
/ \ / \
5 8 11 18
所以我的理解是我遍历10-> 6-> 5,然后我调用destroy_tree(5->左).因此,leaf if if为NULL,并且if-dependent不执行,因此5不被删除.我在哪里弄错了这个推理？如何在这里进行卷绕和退绕？任何帮助都很感激:-)
可以在O(n logn)时间内从列表构造堆,因为将元素插入堆需要O(logn)时间并且有n个元素.
类似地,可以在O(n logn)时间内从列表构造二叉搜索树,因为将元素插入到BST中需要平均登录时间并且存在n个元素.
从最小到最大遍历堆需要O(n logn)时间(因为我们必须弹出n个元素,并且每个pop需要O(logn)接收器操作).从最小到最大遍历BST需要O(n)时间(字面上只是顺序遍历).
所以,在我看来,构造两个结构需要相同的时间,但BST迭代的速度更快.那么,为什么我们使用"Heapsort"代替"BSTsort"呢？
编辑:感谢Tobias和lrlreon的回答!总之,以下是我们使用堆而不是BST进行排序的要点.