Finding Index of a Node in a Huffman Tree / BST-ish
up vote
1
down vote
favorite
Assume we have a tree of nodes that hold string values in them. How would I go about traversing the tree and spitting out an index of a specific node if I had a tree like this? The numbers I drew inside the circles would be the index I want (especially 12 or 13).
java binary-search-tree
asked Nov 11 at 0:56
King Arthur the Third
234
add a comment |
up vote
1
down vote
favorite
Assume we have a tree of nodes that hold string values in them. How would I go about traversing the tree and spitting out an index of a specific node if I had a tree like this? The numbers I drew inside the circles would be the index I want (especially 12 or 13).
java binary-search-tree
asked Nov 11 at 0:56
King Arthur the Third
234
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Assume we have a tree of nodes that hold string values in them. How would I go about traversing the tree and spitting out an index of a specific node if I had a tree like this? The numbers I drew inside the circles would be the index I want (especially 12 or 13).
java binary-search-tree
asked Nov 11 at 0:56
King Arthur the Third
234
Assume we have a tree of nodes that hold string values in them. How would I go about traversing the tree and spitting out an index of a specific node if I had a tree like this? The numbers I drew inside the circles would be the index I want (especially 12 or 13).
java binary-search-tree
java binary-search-tree
asked Nov 11 at 0:56
King Arthur the Third
234
asked Nov 11 at 0:56
King Arthur the Third
234
edited Nov 11 at 2:17
asked Nov 11 at 0:56
King Arthur the Third
234
asked Nov 11 at 0:56
King Arthur the Third
234
asked Nov 11 at 0:56
King Arthur the Third
234
234
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
The tree you are showing is not a binary search tree. The central property of a binary search tree that allows it to be searched efficiently is that the left descendants of a node are smaller, and the right descendants bigger than the node itself (in terms of the index value).
If you have a proper binary search tree, you can find a node with given index by comparing with nodes and following the corresponding branch, starting with the root.
answered Nov 11 at 1:25
Henning Koehler
1,100610
Quoting my question: "Assume we have a tree of nodes that hold string values in them" and "The numbers I drew inside the circles would be the index I want (especially 12 or 13)."
– King Arthur the Third
Nov 11 at 1:50
I'm working on an assignment that is dealing with more of a Huffman Tree like structure
– King Arthur the Third
Nov 11 at 1:53
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
The tree you are showing is not a binary search tree. The central property of a binary search tree that allows it to be searched efficiently is that the left descendants of a node are smaller, and the right descendants bigger than the node itself (in terms of the index value).
If you have a proper binary search tree, you can find a node with given index by comparing with nodes and following the corresponding branch, starting with the root.
answered Nov 11 at 1:25
Henning Koehler
1,100610
Quoting my question: "Assume we have a tree of nodes that hold string values in them" and "The numbers I drew inside the circles would be the index I want (especially 12 or 13)."
– King Arthur the Third
Nov 11 at 1:50
I'm working on an assignment that is dealing with more of a Huffman Tree like structure
– King Arthur the Third
Nov 11 at 1:53
add a comment |
up vote
0
down vote
The tree you are showing is not a binary search tree. The central property of a binary search tree that allows it to be searched efficiently is that the left descendants of a node are smaller, and the right descendants bigger than the node itself (in terms of the index value).
If you have a proper binary search tree, you can find a node with given index by comparing with nodes and following the corresponding branch, starting with the root.
answered Nov 11 at 1:25
Henning Koehler
1,100610
Quoting my question: "Assume we have a tree of nodes that hold string values in them" and "The numbers I drew inside the circles would be the index I want (especially 12 or 13)."
– King Arthur the Third
Nov 11 at 1:50
I'm working on an assignment that is dealing with more of a Huffman Tree like structure
– King Arthur the Third
Nov 11 at 1:53
add a comment |
up vote
0
down vote
up vote
0
down vote
The tree you are showing is not a binary search tree. The central property of a binary search tree that allows it to be searched efficiently is that the left descendants of a node are smaller, and the right descendants bigger than the node itself (in terms of the index value).
If you have a proper binary search tree, you can find a node with given index by comparing with nodes and following the corresponding branch, starting with the root.
answered Nov 11 at 1:25
Henning Koehler
1,100610
The tree you are showing is not a binary search tree. The central property of a binary search tree that allows it to be searched efficiently is that the left descendants of a node are smaller, and the right descendants bigger than the node itself (in terms of the index value).
If you have a proper binary search tree, you can find a node with given index by comparing with nodes and following the corresponding branch, starting with the root.
answered Nov 11 at 1:25
Henning Koehler
1,100610
answered Nov 11 at 1:25
Henning Koehler
1,100610
answered Nov 11 at 1:25
Henning Koehler
1,100610
answered Nov 11 at 1:25
Henning Koehler
1,100610
1,100610
Quoting my question: "Assume we have a tree of nodes that hold string values in them" and "The numbers I drew inside the circles would be the index I want (especially 12 or 13)."
– King Arthur the Third
Nov 11 at 1:50
I'm working on an assignment that is dealing with more of a Huffman Tree like structure
– King Arthur the Third
Nov 11 at 1:53
add a comment |
Quoting my question: "Assume we have a tree of nodes that hold string values in them" and "The numbers I drew inside the circles would be the index I want (especially 12 or 13)."
– King Arthur the Third
Nov 11 at 1:50
I'm working on an assignment that is dealing with more of a Huffman Tree like structure
– King Arthur the Third
Nov 11 at 1:53
Quoting my question: "Assume we have a tree of nodes that hold string values in them" and "The numbers I drew inside the circles would be the index I want (especially 12 or 13)."
– King Arthur the Third
Nov 11 at 1:50
Quoting my question: "Assume we have a tree of nodes that hold string values in them" and "The numbers I drew inside the circles would be the index I want (especially 12 or 13)."
– King Arthur the Third
Nov 11 at 1:50
I'm working on an assignment that is dealing with more of a Huffman Tree like structure
– King Arthur the Third
Nov 11 at 1:53
I'm working on an assignment that is dealing with more of a Huffman Tree like structure
– King Arthur the Third
Nov 11 at 1:53
add a comment |
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53244895%2ffinding-index-of-a-node-in-a-huffman-tree-bst-ish%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
