两个二叉树是同构的意味着什么？我一直在网上看,我似乎无法找到明确的解释.
据我所知,如果它们具有相同的形状,则两棵树是同构的.所以我猜两个相同的树,它们可以在节点中包含不同的值.
这不是功课,我不需要回答它,但现在我已经变得痴迷:)
问题是:
大约一年前我在互联网上找到了这个问题的解决方案,但现在我已经忘记了,我想知道:)
据我记忆,这个技巧涉及使用树来实现队列,利用算法的破坏性.链接列表时,您还将项目推入队列.
每次我尝试解决这个问题,我都会丢失节点(比如每次我链接下一个节点/添加到队列中),我需要额外的存储空间,或者我无法弄清楚我需要回到一个复杂的方法具有我需要的指针的节点.
即使链接到原始文章/帖子对我也很有用:)谷歌没有给我带来快乐.
编辑:
Jérémie指出,如果你有一个父指针,有一个相当简单(和众所周知的答案).虽然我现在认为他对包含父指针的原始解决方案是正确的,但我真的想在没有它的情况下解决问题:)
精炼的需求将此定义用于节点:
struct tree_node
{
int value;
tree_node* left;
tree_node* right;
};
给定二叉搜索树和目标值,找到总计达目标值的所有路径(如果存在多个路径).它可以是树中的任何路径.它不必来自根.
例如,在以下二叉搜索树中:
2
/ \
1 3
当总和应为6时,1 -> 2 -> 3应打印路径.
我试图找出如何获取从二进制树上的根到给定节点的路径.
它不是二叉搜索树.
每个非叶子节点只有两个指向其子节点的指针.
按顺序,预订,后订单遍历不起作用.
我曾尝试做预购,但无法弄清楚如何.例如,我们有一个二叉树:它不是二叉搜索树.我们使用排序顺序节点来更容易地找到路径.
1
/ \
2 3
/ \ / \
4 5 6 7
我们想要找到1到7的路径:
通过预购,我们有:
1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
从流程中,我们得到路径从1 - > 7,其上包含所有节点.
显然,它不应该.
任何帮助都非常感谢.
我使用以下方法遍历*300 000级别的二叉树:
Node* find(int v){
if(value==v)
return this;
else if(right && value<v)
return right->find(v);
else if(left && value>v)
return left->find(v);
}
但是由于堆栈溢出,我得到了分段错误.关于如何在没有递归函数调用开销的情况下遍历深层树的任何想法？
*"遍历"我的意思是"搜索具有给定值的节点",而不是完整的树遍历.
c++ algorithm binary-tree binary-search-tree data-structures
好的,我已经阅读了所有其他相关问题,但找不到有助于java的问题.我从破译其他语言的内容中得到了一般性的想法; 但我还没搞清楚.
问题:我想进行排序(我使用递归工作)并将其打印出树的一般形状.
所以说我有这个:
1
/ \
2 3
/ / \
4 5 6
我的代码打印出这样的级别顺序:
1 2 3 4 5 6
我想像这样打印出来:
1
2 3
4 5 6
在你给我一个关于做我的工作的道德讲话之前......我已经完成了我的AP Comp Sci项目并且当我的老师提到了广度优先搜索的东西时对此感到好奇.
我不知道它是否会有所帮助,但到目前为止我的代码是:
/**
* Calls the levelOrder helper method and prints out in levelOrder.
*/
public void levelOrder()
{
q = new QueueList();
treeHeight = height();
levelOrder(myRoot, q, myLevel);
}
/**
* Helper method that uses recursion to print out the tree in
* levelOrder
*/
private void levelOrder(TreeNode …如何在BST中找到第N个最大节点？
在进行BST的In Order Traversal时,我是否保留计数变量？当count = N时返回元素???
我们给出了一个2 m - 1个不同的,可比较的元素的数组,从1开始索引.
我们可以将数组视为完整的二叉树:
Node is placed at index i.
Left child is placed at 2i.
Right child is placed at 2i+1.
例如,数组
[7 6 4 5 2 3 1]
是树
7
/ \
6 4
/ \ / \
5 2 3 1
现在,当被视为二叉树时,这些元素满足堆属性,节点大于其子节点:
A[i] > A[2i] and A[i] > A[2i+1]
是否存在相当快速的就地算法来重新排列数组的元素,以便生成的二叉树(如上所述)是二叉搜索树？
回想一下,在二叉搜索树中,节点大于其所有左后代,并且少于其所有右后代.
例如,上述阵列的重新洗牌将是
[4 2 6 1 3 5 7]
它对应于二叉搜索树
4
/ \
2 6
/ \ / \
1 3 5 7
我试图使用java在二叉树中打印所有根到叶子路径.
public void printAllRootToLeafPaths(Node node,ArrayList path)
{
if(node==null)
{
return;
}
path.add(node.data);
if(node.left==null && node.right==null)
{
System.out.println(path);
return;
}
else
{
printAllRootToLeafPaths(node.left,path);
printAllRootToLeafPaths(node.right,path);
}
}
主要方法:
bst.printAllRootToLeafPaths(root, new ArrayList());
但它给出错误的输出.
给定的树:
5
/ \
/ \
1 8
\ /\
\ / \
3 6 9
预期产量:
[5,1,3]
[5,8,6]
[5,8,9]
但产量产生:
[5,1,3]
[5,1,3,8,6]
[5,1,3,8,6,9]
有人可以搞清楚......
我有简单的二叉搜索树
public class BNode
{
public int item;
public BNode right;
public BNode left;
public BNode(int item)
{
this.item = item;
}
}
public class BTree
{
private BNode _root;
private int _count;
private IComparer<int> _comparer = Comparer<int>.Default;
public BTree()
{
_root = null;
_count = 0;
}
public bool Add(int Item)
{
if (_root == null)
{
_root = new BNode(Item);
_count++;
return true;
}
else
{
return Add_Sub(_root, Item);
}
}
private bool Add_Sub(BNode Node, int Item)
{ …