0
голосов
4ответов
2477 просмотров

Java recursive binary tree

Welcome! I have a recursive public static method named less that takes a tree node (an original binary tree, not really a search tree) and a int parameter that returns if all the values in the tree are less than the integer. So, I would use a public class TN { public int value; public TN left...

0
голосов
3ответов
2506 просмотров

How to fill a binary tree from a string, java

I'm suppose to fill a binary tree with integers based upon a string like this. [int](LT)(RT) LT is an expression of the same form for the left part of the tree. Same with RT. A valid string would be something like this: 4(2(1)(3))(6(5)(7). How can I fill this tree? This is not a sorted tree ...

96
голосов
7ответов
38312 просмотров

Is Big O(logn) log base e?

For binary search tree type of data structures, I see the Big O notation is typically noted as O(logn). With a lowercase 'l' in log, does this imply log base e (n) as described by the natural logarithm? Sorry for the simple question but I've always had trouble distinguishing between the differ...

3
голосов
3ответов
2125 просмотров

Java Algorithm for finding the largest set of independent nodes in a binary tree

By independent nodes, I mean that the returned set can not contain nodes that are in immediate relations, parent and child cannot both be included. I tried to use Google, with no success. I don't think I have the right search words. A link, any help would be very much appreciated. Just started ...

2
голосов
3ответов
2394 просмотров

Tool for displaying binary decision tree

The system I'm currently working on involves the creation of binary decision trees. Lots of them. Some of them are stored in XML format so they can be analyzed manually if needed. The tree structure is basically nested tags. Each node may also have a few child tags defining the properties of th...

2
голосов
4ответов
497 просмотров

pointer problem in implementing Tree in C

I am implementing an avl tree for my assignment. #include <string.h> #include <stdlib.h> #include <stdio.h> #include <assert.h> struct TreeNode { char *item; struct TreeNode *left; struct TreeNode *right; signed char balance; }; typedef struct TreeNode Node; vo...

14
голосов
8ответов
12410 просмотров

compare Hash with Binary search tree

We all know that a hash table has O(1) time for both inserts and look-ups if the hash function was well chosen. So, what are the reason we want to use Binary Search Tree? Just because a perfect hash function was hard to design? Here how I come up with this question? I notice that Standard C++ ...

11
голосов
1ответов
6766 просмотров

Prove that binary trees with the same inorder and preorder traversals are identical?

Does anybody know how to prove that if two binary trees have the same inorder and preorder traversals, then they are identical? (perhaps by showing that you can't have two different binary trees with identical inorder and preorder traversals) Alternatively, show a case that would disprove this, ...

2
голосов
1ответов
1942 просмотров

How to implement tail recursion for tree algorithms in prolog

How could I convert the following into a tail recursive version. sum(void,0). sum(t(V,L,R),S) :- sum(L,S1), sum(R,S2), S is V + S1 + S2. It seems impossible to maintain a single accumulator as the branching is in 2^n magnitude. A possible solution would be to have the accumulator add a...

3
голосов
1ответов
3962 просмотров

Iterative version of Binary Tree Search

Basic Tree-search algorithm for searching a node (with value k) in a binary search tree. 'x' denotes the node of the binary search tree. TREE-SEARCH (x, k) if x= NIL or k = key[x] then return x if k < key[x] then return TREE-SEARCH(left[x], k) else return TREE-SEARCH(right[x], k...

-3
голосов
5ответов
3523 просмотров

How can I create binary trees in Perl?

How do can I create binary trees in Perl?

188
голосов
34ответов
179678 просмотров

How to find the lowest common ancestor of two nodes in any binary tree?

The Binary Tree here is may not necessarily be a Binary Search Tree. The structure could be taken as - struct node { int data; struct node *left; struct node *right; }; The maximum solution I could work out with a friend was something of this sort - Consider this binary tree : T...

3
голосов
2ответов
653 просмотров

Enumerate search trees

According to this question the number of different search trees of a certain size is equal to a catalan number. Is it possible to enumerate those trees? That is, can someone implement the following two functions: Node* id2tree(int id); // return root of tree int tree2id(Node* root); // return...

20
голосов
6ответов
37458 просмотров

Determine if two binary trees are equal

What would be the efficient algorithm to find if two given binary trees are equal - in structure and content?

1
голосов
1ответов
1756 просмотров

Java Binary Tree, how to implement Node?

In the tree class I'm suppose to compare two node, for you know searching and adding items. I have some issues with how to make it comparable. When one adds data(generic, anything) to the tree one calls the Tree class which then makes a new Node object. How can I declare the variable data/element...

1
голосов
3ответов
7513 просмотров

tree iterations c++

Looking for examples on simple tree iterations in C++, both recursive and iterative. (post, pre and in-order)

1
голосов
1ответов
1551 просмотров

How can delete a binary tree node with all possibility?

I created a binary tree with some integer values, I can search the tree by my code. But I don't know how to proceed delete node operation. So, how can I delete a node?

7
голосов
16ответов
25567 просмотров

How to determine whether a binary tree is complete?

A complete binary tree is defined as a binary tree in which every level, except possibly the deepest, is completely filled. At deepest level, all nodes must be as far left as possible. I'd think a simple recursive algorithm will be able to tell whether a given binary tree is complete, but I can'...

7
голосов
5ответов
4455 просмотров

IntervalTree DeleteNode Java Implementation

I need an IntervalTree or RangeTree implementation in Java, and am having trouble finding one with working deletion support. There's a built-in one at sun.jvm.hotspot.utilities.IntervalTree, but the deleteNode method in the RBTree superclass states: /** * FIXME: this does not work properly yet...

24
голосов
6ответов
5273 просмотров

Are AVL Trees Evil?

I was reading the article from Steve Yegge about singletons. In it he mentions his teacher told him AVL Trees were evil. Is it just that red and black trees are a better solution?

0
голосов
4ответов
6832 просмотров

How can I find a binary tree from a given traversal?

How can I find a binary tree from a given traversal method (inorder, post-order, or pre-order)?

1
голосов
2ответов
110 просмотров

A little problem with BST implementation

I`m writing STL-like container for binary-search tree. I have template class for Tree itself and nested class TreeNode. My question is where should I put the binary-predicate function which compairing keys - Into the tree class or into the Node class? If I decide to put it in a Tree class, all o...

21
голосов
3ответов
12180 просмотров

The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?

This has been bothering me for a while. I know that given N keys to arrange in the form of a binary search tree, the possible number of trees that can be created correspond to the Nth number from the Catalan sequence. I have been trying to determine why this is; unable to find anything that mig...

1
голосов
5ответов
2503 просмотров

Shortest branch in a binary tree?

A binary tree can be encoded using two functions l and r such that for a node n, l(n) give the left child of n, r(n) give the right child of n. A branch of a tree is a path from the root to a leaf, the length of a branch to a particular leaf is the number of arcs on the path from the root to tha...

1
голосов
4ответов
585 просмотров

Binary Tree Node Fault

Here's the node definition: struct node{ int data; stuct node * left; struct node * right; }; What I am trying to do is list all the nodes that point to an ancestor node. After posting the wrong solution and taking advice from the answers, my new solution is: Recursively go throug...

1
голосов
5ответов
2362 просмотров

Tree iterator, can you optimize this any further?

As a follow up to my original question about a small piece of this code I decided to ask a follow up to see if you can do better then what we came up with so far. The code below iterates over a binary tree (left/right = child/next ). I do believe there is room for one less conditional in here (t...

59
голосов
28ответов
98989 просмотров

Post order traversal of binary tree without recursion

What is the algorithm for doing a post order traversal of a binary tree WITHOUT using recursion?

2
голосов
6ответов
4198 просмотров

Sorting a binary search tree on different key value

Say I have a binary tree with the following definition for a node. struct node { int key1 ; int key2 ; } The binary search tree is created on the basis of key1. Now is it possible to rearrange the binary search tree on basis of key2 in O(1) space. Although I can do this in variable space usi...

0
голосов
4ответов
3034 просмотров

Algorithm to return length of shortest branch in a binary tree

A binary tree can be encoded using two functions l and r such that for a node n, l(n) give the left child of n , r(n) give the right child of n. A branch of a tree is a path from the root to a leaf, the length of a branch to a particular leaf is the number of arcs on the path from the roo...

4
голосов
3ответов
17360 просмотров

Convert Preorder listing of a binary tree to postorder and vice versa

How can I find the preorder listing of a tree if only the postorder listing is given and vice versa. Also, in the tree, every non-leaf node has two children (i.e. Each node has either two or zero children.) EDIT: Another given assumption is that the label of each node is unique and has a field t...