首先,我假设在考虑这个问题时我已经错过了一些重要的东西,但我仍然想发布它,看看我是否真的没有错过任何东西,用它...
我有一个非常重写的二叉树(写入和读取之间约为50/50),在回家的路上,我正在考虑如何优化这一点,特别是使写入更快 - 这就是我提出的.
考虑到向树T添加x的操作add(T,x)首先由find(T,x)组成,以查看x是否已经存在,并且在这种情况下它不返回父,所以我们可以添加它而不是其中一个父母空叶.
如果我们将一个哈希表作为中间缓存添加到add操作,那么当我们调用add(T,x)时,真正发生的是x被散列并插入到哈希映射M中.就是这样.优化发生在我们其他地方要求查找(T,x)时,现在当我们搜索树时,我们将来到叶节点,因为x尚未插入树(它只存在于哈希映射M中) ,我们哈希x并将其与M中的键进行比较,以查看它是否应该在树中.如果它在M中找到,那么我们将它添加到树中并从M中删除它.
这将消除add(T,x)上的find(T,x)运算并将其减少为添加(M,x),即O(1).然后(ab) - 使用我们在第一次插入节点时执行的find(T,x)操作.
language-agnostic optimization binary-tree hashtable data-structures
template<typename T>
void traverse_binary_tree(BinaryTreeNode<T>* root,int order = 0)// 0:pre, 1:in , 2:post
{
if( root == NULL ) return;
if(order == 0) cout << root->data << " ";
traverse_binary_tree(root->left,order);
if(order == 1) cout << root->data << " ";
traverse_binary_tree(root->right,order);
if(order == 2) cout << root->data << " ";
}
有没有更好的方法来编写这个功能？
我正在使用Haskell函数从二进制搜索树中删除节点.我知道有关采取行动的规则取决于目标父母的子女数量.
没有孩子 - 删除,1个孩子 - 用孩子替换,2个孩子 - 在右子树中找到min并用值替换节点,然后,递归地从右子树中删除最小值
data BST = MakeNode BST String BST
| Empty
deleteNode :: String -> BST
treeBuilder :: [String] -> BST
treeBuilder = foldr add Empty
add :: String -> BST -> BST
add new Empty = (MakeNode Empty new Empty)
add string tree@(MakeNode left value right)
| string > value = MakeNode left value (add string right)
| string < value = MakeNode (add string left) value right
| otherwise = tree
无法弄清楚为什么treeBuilder也无法正常工作.它只是向右对角打印字符串.
这已经在这里讨论了,但我在下面有一个实现(从未在线程中讨论),
public boolean isBalanced(BSTNode node) {
if(maxHeight() > (int)(Math.log(size())/Math.log(2)) + 1)
return false;
else
return true;
}
其中maxHeight()返回树的最大高度.基本上我正在检查maxHeight> log(n),其中n是树中元素的数量.这是正确的解决方案吗？
给定二叉树,找到同一垂直线上的节点的垂直和.通过不同的垂直线打印所有总和.
要了解同一垂直线是什么,我们需要先定义水平距离.如果两个节点具有相同的水平距离(HD),则它们位于同一垂直线上.HD的想法很简单.根的HD为0,右边缘(连接到右子树的边缘)被认为是+1水平距离而左边缘被认为是-1水平距离.例如,在上面的树中,节点4的HD为-2,节点2的HD为-1,5和6的HD为0,节点7的HD为+2.
例子:
1
/ \
2 3
/ \ / \
4 5 6 7
树有5条垂直线
Vertical-Line-1只有一个节点4 => vertical sum是4
Vertical-Line-2:只有一个节点2 =>垂直和是2
Vertical-Line-3:有三个节点:1,5,6 =>垂直和是1 + 5 + 6 = 12
Vertical-Line-4:只有一个节点3 =>垂直和为3
Vertical-Line-5:只有一个节点7 =>垂直和是7
因此预期产量为4,2,12,3和7
我的解决方案: 我想出了这个问题的ao(nlong(n))解决方案.这个想法是:
(1)使用preorder遍历获取每个节点的HD,并将HD及其相关节点存储在一个数组中.
(2)通过HD对数组进行排序
(3)遍历排序数组以打印结果.
我敢肯定这不是解决这个问题的最好方法.有人能帮我提供更好的解决方案吗？
我试图在java中找到二叉树的直径(树中包含最大节点数的任意两个节点之间的路径长度.).
我的代码片段:
public int diametre(Node node, int d)
{
if(node==null)
return 0;
lh=diametre(node.left, d);
rh=diametre(node.right, d);
if(lh+rh+1>d)
d=lh+rh+1;
return findMax(lh, rh)+1;
}
主要方法:
System.out.println( bst.diametre(root,0) );
逻辑:它实际上是后序逻辑.变量'd'指的是子树的直径(在那个迭代中).当发现一些较大的值时,它将被更新.'lh'指的是:左子树的高度.'rh'指的是:右子树的高度.
但它给出错误的输出.
树考虑:
5
/ \
/ \
1 8
\ /\
\ / \
3 6 9
空闲输出:5
但是这段代码给出了3.
有人可以找出问题所在......
这是级别顺序遍历的代码:
public void bfsTraveral() {
if (root == null) {
throw new NullPointerException("The root cannot be null.");
}
int currentLevelNodes = 0;
int nextLevelNodes = 0;
final Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
currentLevelNodes++;
while(!queue.isEmpty()) {
final TreeNode node = queue.poll();
System.out.print(node.element + ",");
currentLevelNodes--;
if (node.left != null) { queue.add(node.left); nextLevelNodes++;}
if (node.right != null) { queue.add(node.right); nextLevelNodes++;}
if (currentLevelNodes == 0) {
currentLevelNodes = nextLevelNodes;
nextLevelNodes = 0;
System.out.println();
}
}
在我看来,空间复杂度应为O(2 ^ h),其中h是树的高度,这仅仅是因为它是执行期间队列可达到的最大大小.在互联网上,我发现空间复杂度为O(n).这听起来不对我.请分享您的意见.
谢谢,
我有一个小的haskell代码实现二叉树.我想在树上应用折叠功能.这是代码 -
data Btree a = Tip a | Bin (Btree a) (Btree a) deriving Show
foldbtree :: (a->a->a) -> Btree a-> a
foldbtree f (Tip x) = x
foldbtree f (Bin t1 t2) = (foldbtree f t1) f (foldbtree f t2)
但我收到编译错误 -
Occurs check: cannot construct the infinite type:
t2 = t0 -> t1 -> t2
In the return type of a call of `foldbtree'
Probable cause: `foldbtree' is applied to too many arguments
In the expression: (foldbtree …我使用本书中描述的二叉树 解决算法和数据结构问题
class BinaryTree:
def __init__(self,rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None
已经存在如下定义的预序遍历方法.
def preorder(tree):
if tree:
print(tree.self.key)
preorder(tree.getLeftChild())
preorder(tree.getRightChild())
我只想添加访问的节点列表的返回值.所以我可以做点什么
for i in preorder(tree):
etc...
我无法从递归方法返回列表.一旦它到达'返回',我就尝试使用变量,递归就会停止
return [tree.self.key] + preorder()
要么
yield ...
有任何想法吗？
我是该页面的新手，我真的被大学的作业困住了，以重新创建一个无需递归即可将节点插入树的函数。给我递归方法，我需要将其转换为迭代。这是给定的递归代码：
TreeNode *InsertTree(TreeNode *root, TreeNode *newnode)
{
if (!root)
{
root = newnode;
root->left = root->right=NULL;
}
else if (newnode->entry < root->entry)
{
root->left = InsertTree(root->left, newnode);
}
else
{
root->right = InsertTree(root->right, newnode);
}
return root;
}
我做了这个：
TreeNode *InsertTree(TreeNode *root, TreeNode *newnode)
{
if (!root)
{
root = newnode;
root->left = root->right=NULL;
}
else
{
TreeNode * temp = root, *prev = NULL;
while(temp)
{
if (temp->entry < newnode->entry)
temp = temp->right;
else
temp = temp->left;
}
newnode; …