我正在搜索树以查找传递的值.不幸的是,它不起作用.我开始用打印机调试它,奇怪的是它实际上找到了值,但是跳过了return语句.
/**
* Returns the node with the passed value
*/
private TreeNode searchNodeBeingDeleted(Comparable c, TreeNode node)
{
if(node == null)
{
return null;
}
if(c.equals((Comparable)node.getValue()))
{
System.out.println("Here");
return node;
}
else
{
if(node.getLeft() != null)
{
System.out.println("left");
searchNodeBeingDeleted(c, node.getLeft());
}
if(node.getRight() != null)
{
System.out.println("right");
searchNodeBeingDeleted(c, node.getRight());
}
}
return null; //i think this gives me my null pointer at bottom
}
它打印出如下结果:
left
left
right
right
Here
right
left
right
left
right
Exception in thread "main" java.lang.NullPointerException
at …假设以下功能:
int binaryTree::findHeight(node *n) {
if (n == NULL) {
return 0;
} else {
return 1 + max(findHeight(n->left), findHeight(n->right));
}
}
treeHeight对于给定的二叉搜索树,相当标准的递归函数binaryTree.现在,我正在帮助一个朋友(他正在学习算法课程),我遇到了一个奇怪的问题,我无法100%向他解释这个功能.
将max定义为max(a,b) ((a)>(b)?(a):(b))(恰好是最大定义windef.h),递归函数变得怪异(它运行的n^n时间就像n树高一样).这显然使得检查具有3000个元素的树的高度非常非常长.
但是,如果max是通过模板定义的,就像std它一样,一切都很好.所以使用std::max修复他的问题.我只想知道原因.
另外,为什么countLeaves函数工作正常,使用相同的程序递归？
int binaryTree::countLeaves(node *n) {
if (n == NULL) {
return 0;
} else if (n->left == NULL && n->right == NULL) {
return 1;
} else {
return countLeaves(n->left) + countLeaves(n->right);
}
}
是因为在返回三元函数时,值a => …
我正在寻找.NET 4中的内置二进制搜索树实现.有一个吗？
简而言之,我想学习/开发一种优雅的方法来将二叉树保存到磁盘(一般树,不一定是BST).这是我的问题的描述:
我正在实施一个"20个问题"的游戏.我写了一个二叉树,其内部节点是问题,叶子是答案.如果有人对你当前的问题回答"是",那么节点的左子节点就是你要遵循的路径,而正确的孩子则是"否"的答案.请注意,这不是二叉搜索树,只是一个二叉树,其左子节点为"是",右侧为"否".
如果通过要求用户将她的答案与计算机所考虑的答案区分开来,该程序遇到一个空的叶子,该程序会向树中添加一个节点.
这很简洁,因为树会在用户播放时自行构建.什么不整洁是我没有一个很好的方法将树保存到磁盘.
我已经考虑过将树保存为数组表示(对于节点i,左边的子节点是2i + 1,右边是2i + 2,父节点是(i-1)/ 2),但它不干净,我最终得到了浪费了很多空间.
有关将稀疏二叉树保存到磁盘的优雅解决方案的任何想法？
想知道最有效的方法是通过读入1000字的字典文件,然后让它检查另一个说有几段的文件,将二元搜索树变成拼写检查器.
如果仅给出后序列表,我怎样才能找到树的预订列表,反之亦然.此外,在树中,每个非叶节点都有两个子节点(即每个节点有两个或零个子节点.)
编辑:另一个给定的假设是每个节点的标签是唯一的,并且有一个字段,将其标识为内部节点或叶子.我认为应该摆脱单个预订单或后序的模糊性能够唯一地识别树.
通过一些练习来磨练我的二叉树技能,我决定实现一个splay树,如维基百科:Splay树中所述.
我没有得到的一件事是关于插入的部分.
它说:
首先,我们在splay树中搜索x.如果x尚不存在,那么我们将找不到它,而是它的父节点y.其次,我们对y执行一个splay操作,它将y移动到splay树的根.第三,我们以适当的方式将新节点x作为root插入.以这种方式,y是新根x的左或右子.
我的问题是:与文章中的其他例子相比,上述文字似乎过于简洁,为什么会这样？似乎这里遗漏了一些问题.例如,在将y节点向上扩展到根之后,我不能盲目地用x替换root,并将x作为左或右子进行处理.
我们假设树中不存在该值.
我有这棵树:
10
/ \
5 15
/ \ \
1 6 20
我想插入8.通过上面的描述,我将找到6节点,并且在普通的二叉树中,8将被添加为6节点的右子节点,但是在这里我首先必须展开6节点到root:
6
/ \
5 10
/ \
1 15
\
20
那么这两个中的任何一个都是明显错误的:
8 8
\ /
6 6
/ \ / \
5 10 5 10
/ \ / \
1 15 1 15
\ \
20 20
6 is not greater than 8 10 is not less than 8
在我看来,首先进行splaying,然后以root身份正确添加新值的唯一方法意味着我必须检查以下条件(将splayed节点添加为新root的左子节点):
但是,如果我要拆分我显示的节点,通过选择正确的子节点并将其作为新节点的右子节点附加,我会得到:
8
/ \ …我需要计算二叉树中的节点总数.当我执行此代码时,问题就出现了,它为节点总数提供了垃圾值.我的程序输出就像993814.应该是7.
如何解决这个问题？
#include<stdlib.h>
#include<stdio.h>
struct binarytree
{
int data;
struct binarytree * right, * left;
};
typedef struct binarytree node;
void insert(node ** tree, int val)
{
node *temp = NULL;
if(!(*tree))
{
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val;
*tree = temp;
return;
}
if(val < (*tree)->data)
{
insert(&(*tree)->left, val);
}
else if(val > (*tree)->data)
{
insert(&(*tree)->right, val);
}
}
void print_preorder(node * tree)
{
if (tree)
{
printf("%d\n",tree->data);
print_preorder(tree->left); …在"对Haskell的温和介绍"中,我们有Tree类型的声明:
data Tree a = Leaf a | Branch (Tree a) (Tree a)
deriving (Eq,Ord,Show,Read)
让我们来做一些这种类型的值:
a1 = Leaf 1
a2 = Leaf 2
a3 = Leaf 3
a4 = a1 `Branch` a2
a5 = a2 `Branch` a3
a6 = a4 `Branch` a5
在ghci:
*Main> :t a6
a6 :: Tree Integer
但a6根本不是树,请参阅:
a6
/ \
a4 a5
/ \ / \
a1 a2 a3
这个图表中有一个循环!怎么了？树的类型定义是否正确？或许,我不能在理解这个例子时遇到一些错误......