好的,我已经阅读了所有其他相关问题,但找不到有助于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)
{ …如何在二叉树中找到两个节点之间的距离？同样,有哪些算法可以找到两个节点的最新共同祖先(最低共同祖先)？
我想使用隐式指针实现一个缓存无关的二叉树,它使用van Emde Boas布局存储在一个数组中.树中的所有项都是32位整数,并且树会变得相当大,因此存储指针意味着至少要多3倍的数据.
问题在于,在给定节点索引(我可以在遍历树时跟踪任何信息)时,我无法想到计算指向左右子节点的指针的任何非迭代方法.许多论文/讲座都是用隐式指针引用这些树,但我还没有看到计算指针的算法.有没有一种有效的方法呢？
关于红黑树的问题很多,但没有一个问题可以回答它们的工作原理.为什么叫红黑？这如何保持树的平衡(从而提高了不平衡的普通二叉搜索树的性能)？我只是在寻找它的工作原理和原因.
我有一个树数据类型:
data Tree a b = Branch b (Tree a b) (Tree a b) | Leaf a
......我需要将它作为一个实例Show而不使用deriving.我发现很好地显示一个带有两个叶子的小分支很容易:
instance (Show a, Show b) => Show (Tree a b) where
show (Leaf x) = show x
show (Branch val l r) = " " ++ show val ++ "\n" ++ show l ++ " " ++ show r
但是如何将一个漂亮的结构扩展到任意大小的树？似乎确定间距需要我知道底部有多少叶子(或者总共有多少叶子),以便我可以分配我需要的所有空间并且只需要工作. " 我可能需要调用一个大小函数.我可以看到这是可行的,但这是否使它变得更难？
上面的函数 AllPaths()将一个包含二叉树每个叶子的路径的数组附加到全局数组中 res。
该代码工作得很好，但我想删除全局变量 res并使函数返回一个数组。我怎样才能做到这一点？
class Node:
def __init__(self, value, left=None, right=None) -> None:
self.value = value
self.left = left
self.right = right
res = []
def allPaths(node, arr=[]):
if node:
tmp = [*arr, node.value]
if not node.left and not node.right: # Leaf
res.append(tmp)
allPaths(node.left, tmp)
allPaths(node.right, tmp)
root = Node(1)
root.left = Node(2);
root.left.left = Node(4);
root.left.right = Node(5);
root.right = Node(3);
root.right.right = Node(6);
"""
1 <-- root
/ \
2 3
/ \ \ …