有没有理由我在Ruby中看不到二进制搜索树？
是否存在人们通常使用的等效数据结构或类？
我不是想解决一个具体问题; 只是想了解更多关于语言的知识.
谢谢!
我需要一些递归帮助.我正在尝试用C#做一个二叉树,我想知道是否有可能用递归函数演示所有Inorder/PostOrder和PreOrder遍历.
我已经为PreOrder完成了它然后尝试了InOrder然而导致了StackOverflow异常,我对Binary Tree的掌握最多是脆弱的,所以任何对此的帮助都会非常感激,即使它看起来像是一个愚蠢的问题.
以下代码是我用于PreOrder Traversal的代码;
public void recursivePreorder(BinaryTreeNode root)
{
Console.Write(root.Data.ToString());
if (root.Left != null)
{
recursivePreorder(root.Left);
}
if (root.Right != null)
{
recursivePreorder(root.Right);
}
}
public void preorderTraversal()
{
if (Root != null)
{
recursivePreorder(Root);
}
else
{
Console.WriteLine("There is no tree to process");
}
static void Main(string[] args)
{
// Build the tree
Test.Add(5);
Test.Add(2);
Test.Add(1);
Test.Add(3);
Test.Add(3); // Duplicates are OK
Test.Add(4);
Test.Add(6);
Test.Add(10);
Test.Add(7);
Test.Add(8);
Test.Add(9);
// Test if we can find values in the tree …在这里,我正在尝试制作二叉树,以便我可以使用它们进行不同的操作.
import java.util.*;
import java.lang.*;
public class Main {
public static void main(String[] args) {
}
}
//Building Binary Trees
class bTree {
static class Node { //remember to initilize a root
String value;
Node left, right;
Node(String value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
Node(String value) //THIS IS A SIBLING CONSTRUCTOR
{
this(value, null, null);
}
Node root = new Node("ROOT");
Node lefty = new Node("LEFT0");
Node righty = new …我正在读一本名为" 算法简介 "的书.我想很多人都知道.我刚刚碰到一个看似相当困难的问题:
编写一个O(n)-time非递归过程,给定一个n节点二叉树,打印出每个节点的密钥.在树本身之外使用不超过恒定的额外空间,并且在过程中不要修改树,即使是暂时的.
我看到还有另外一个问题:如何在没有额外内存的情况下在O(n)时间遍历二叉树,但主要区别在于我无法修改树.我正在考虑使用一些访问过的标志,但我还没有提出正确的解决方案.这可能是我看不到的明显的东西.你会如何设计一个解决这个问题的算法？即使是对答案的一些指示也会受到赞赏.
path = 0 # the lenght of the path
while self.right != None or self.left != None:
while self.right != None:
self = self.right
path = path +1
while self.left != None:
self = self.left
path = path +1
return path
这是我查找高度的示例代码,定义为从自身到叶子的节点数量的最长路径的长度.叶节点的高度为1.
它不起作用.
不确定问题应该在这里还是在程序员(或其他一些SE网站)上,但我对平衡二叉树和可索引的跳过列表之间的相关差异感到好奇.问题出现在这个问题的背景下.来自维基百科:
跳过列表是一种概率数据结构,似乎可能取代平衡树作为许多应用程序选择的实现方法.跳过列表算法与平衡树具有相同的渐近预期时间界限,并且更简单,更快速并且使用更少的空间.
跳过列表的空间要求是否取决于层次结构的深度？并且二叉树不是更容易使用,至少对于搜索(在平衡BST中授予,插入和删除可能是棘手的)？跳过列表还有其他优点/缺点吗？
language-agnostic algorithm binary-tree skip-lists data-structures
给定二叉搜索树中的一组数据,如数字1到10,是否可能存在多个平衡二叉搜索树？
或者,对于那组数据,是否只有一个独特的平衡BST？
谢谢
我试图在C++中实现BST.这是一个特定的成员函数,用于遍历和返回带有树元素的向量.现在问题出现在我设置为当前节点的stack pop()函数中.
void value not ignored as it ought to be
我理解空堆栈将在前面的pop()调用之后返回一个void值.但是这个解决方案是什么,导致这个遍历算法需要从堆栈中检索最后一个节点.
vector <int> BSTree::in_order_traversal()
{
vector <int> list;
stack <Node *> depthStack;
Node * cur = root;
while ( !depthStack.empty() || cur != NULL ) {
if (cur != NULL) {
depthStack.push(cur);
cur = cur->left;
}
else {
cur = depthStack.pop(); // Heres the line
list.push_back(cur->key);
cur = cur->right;
}
}
return list;
}
我不确定如何确定树是平衡的,完美平衡的,或者如果我将它作为图片而不是代码则不然
例如,如果我有这棵树我怎样才能检查它是否平衡,完美平衡或不平衡？并且有人能给我一个完美平衡树的例子吗？
[o]
/ \
[b] [p]
\ / \
[d] [m] [r]
很明显,如果它是这样的话,我可以说这棵树是不平衡的:
[b]
\
[d]
\
[r]
\
[c]
但是,如果它与上面的那个非常类似,我不知道如何得到它
这是一个完美平衡和平衡的树:
[k]
/ \
[A] [p]
/ \
[N] [R]
有人可以向我解释一下吗？
我遇到了以下实现并花了一些时间,但仍然无法掌握这个想法.有人可以逐行解释它在做什么吗？我只是不明白在什么时候它可以决定一个节点是一个祖先.
谢谢
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left != null && right != null) return root;
return left != null ? left : right;
}
}