Problem in Converting a binary tree to a threaded binary tree
0
I want to convert a binary tree to threaded binary tree.
this is my algorithm and code to convert.
but i get the error "Exception of type 'System.StackOverflowException' was thrown.
"
public void ConvertToTBT(Node r, int inorder)
{
for (int i = 0; i < inorder.Length; i++)
{
Node temp = Search(r, inorder[i]);
if (i <= inorder.Length - 2)
if (temp.rightChild == null)
{
temp.rightChild = Search(r, inorder[i + 1]);
temp.is_right_thread = true;
}
if (i != 0)
if (temp.leftChild == null)
{
temp.leftChild = Search(r, inorder[i - 1]);
temp.is_left_thread = true;
}
}
}
and this is the search method(that finds a node and return that) i found here and use in my code
public Node Search(Node root, int data)
{
if (root != null)
{
if (root.data == data)
return root;
else
{
Node foundNode = Search(root.leftChild, data);
if (foundNode == null)
foundNode = Search(root.rightChild, data);
return foundNode;
}
}
else
return null;
}
where do i make mistake?!
if you have a better idea for converting a BT to TBT , So please help me!
NOTE that my tree is a binary one NOT Binary search
also my biuldTree method
public Node BuildTree(int inorder, int preorder, int instart, int inend)
{
if (instart > inend)
return null;
if (preindex >= inorder.Length)
return null;
int pickedpre = preorder[preindex];
preindex++;
Node newnode = new Node(pickedpre);
if (instart == inend)
return newnode;
for (int i = 0; i < inorder.Length; i++)
{
if (inorder[i] == pickedpre)
{
inindex = i;
break;
}
}
newnode.leftChild = BuildTree(inorder, preorder, instart, inindex - 1);
newnode.rightChild = BuildTree(inorder, preorder, inindex + 1, inend);
root = newnode;
return newnode;
}
c# binary-tree binary-search-tree
edited Dec 29 '18 at 2:24
Daniel A. White
148k36293372
asked Dec 29 '18 at 2:17
ali 4langiali 4langi
104
add a comment |
0
I want to convert a binary tree to threaded binary tree.
this is my algorithm and code to convert.
but i get the error "Exception of type 'System.StackOverflowException' was thrown.
"
public void ConvertToTBT(Node r, int inorder)
{
for (int i = 0; i < inorder.Length; i++)
{
Node temp = Search(r, inorder[i]);
if (i <= inorder.Length - 2)
if (temp.rightChild == null)
{
temp.rightChild = Search(r, inorder[i + 1]);
temp.is_right_thread = true;
}
if (i != 0)
if (temp.leftChild == null)
{
temp.leftChild = Search(r, inorder[i - 1]);
temp.is_left_thread = true;
}
}
}
and this is the search method(that finds a node and return that) i found here and use in my code
public Node Search(Node root, int data)
{
if (root != null)
{
if (root.data == data)
return root;
else
{
Node foundNode = Search(root.leftChild, data);
if (foundNode == null)
foundNode = Search(root.rightChild, data);
return foundNode;
}
}
else
return null;
}
where do i make mistake?!
if you have a better idea for converting a BT to TBT , So please help me!
NOTE that my tree is a binary one NOT Binary search
also my biuldTree method
public Node BuildTree(int inorder, int preorder, int instart, int inend)
{
if (instart > inend)
return null;
if (preindex >= inorder.Length)
return null;
int pickedpre = preorder[preindex];
preindex++;
Node newnode = new Node(pickedpre);
if (instart == inend)
return newnode;
for (int i = 0; i < inorder.Length; i++)
{
if (inorder[i] == pickedpre)
{
inindex = i;
break;
}
}
newnode.leftChild = BuildTree(inorder, preorder, instart, inindex - 1);
newnode.rightChild = BuildTree(inorder, preorder, inindex + 1, inend);
root = newnode;
return newnode;
}
c# binary-tree binary-search-tree
edited Dec 29 '18 at 2:24
Daniel A. White
148k36293372
asked Dec 29 '18 at 2:17
ali 4langiali 4langi
104
Where does the StackOverlow exception occur? In your Search or your BuildTree method?
– Klaus Gütter
Dec 29 '18 at 6:52
@KlausGütter StackOverlow exception occur in my Search method.BuildTree is fine.the problem is with either Search or ConvertToTBT method. when i trace search method , for the third node to thread, it can not get outside the search method
– ali 4langi
Dec 29 '18 at 9:49
@KlausGütter this is my project for Data Structure.i really got tired on this! i can explain my code if needed
– ali 4langi
Dec 29 '18 at 9:59
Your Search method will Stack-overflow if your "tree" contains cycles, i.e. if a left_child or right_child references a node that has already been visited. You might add some additional code to your ConvertToTBT method to verify that this invariant is maintained.
– Klaus Gütter
Dec 29 '18 at 12:49
Can you provide full code so I can run it and try to understand better what you try to accomplish?
– Aldert
Dec 29 '18 at 16:41
add a comment |
0
0
0
1
I want to convert a binary tree to threaded binary tree.
this is my algorithm and code to convert.
but i get the error "Exception of type 'System.StackOverflowException' was thrown.
"
public void ConvertToTBT(Node r, int inorder)
{
for (int i = 0; i < inorder.Length; i++)
{
Node temp = Search(r, inorder[i]);
if (i <= inorder.Length - 2)
if (temp.rightChild == null)
{
temp.rightChild = Search(r, inorder[i + 1]);
temp.is_right_thread = true;
}
if (i != 0)
if (temp.leftChild == null)
{
temp.leftChild = Search(r, inorder[i - 1]);
temp.is_left_thread = true;
}
}
}
and this is the search method(that finds a node and return that) i found here and use in my code
public Node Search(Node root, int data)
{
if (root != null)
{
if (root.data == data)
return root;
else
{
Node foundNode = Search(root.leftChild, data);
if (foundNode == null)
foundNode = Search(root.rightChild, data);
return foundNode;
}
}
else
return null;
}
where do i make mistake?!
if you have a better idea for converting a BT to TBT , So please help me!
NOTE that my tree is a binary one NOT Binary search
also my biuldTree method
public Node BuildTree(int inorder, int preorder, int instart, int inend)
{
if (instart > inend)
return null;
if (preindex >= inorder.Length)
return null;
int pickedpre = preorder[preindex];
preindex++;
Node newnode = new Node(pickedpre);
if (instart == inend)
return newnode;
for (int i = 0; i < inorder.Length; i++)
{
if (inorder[i] == pickedpre)
{
inindex = i;
break;
}
}
newnode.leftChild = BuildTree(inorder, preorder, instart, inindex - 1);
newnode.rightChild = BuildTree(inorder, preorder, inindex + 1, inend);
root = newnode;
return newnode;
}
c# binary-tree binary-search-tree
edited Dec 29 '18 at 2:24
Daniel A. White
148k36293372
asked Dec 29 '18 at 2:17
ali 4langiali 4langi
104
I want to convert a binary tree to threaded binary tree.
this is my algorithm and code to convert.
but i get the error "Exception of type 'System.StackOverflowException' was thrown.
"
public void ConvertToTBT(Node r, int inorder)
{
for (int i = 0; i < inorder.Length; i++)
{
Node temp = Search(r, inorder[i]);
if (i <= inorder.Length - 2)
if (temp.rightChild == null)
{
temp.rightChild = Search(r, inorder[i + 1]);
temp.is_right_thread = true;
}
if (i != 0)
if (temp.leftChild == null)
{
temp.leftChild = Search(r, inorder[i - 1]);
temp.is_left_thread = true;
}
}
}
and this is the search method(that finds a node and return that) i found here and use in my code
public Node Search(Node root, int data)
{
if (root != null)
{
if (root.data == data)
return root;
else
{
Node foundNode = Search(root.leftChild, data);
if (foundNode == null)
foundNode = Search(root.rightChild, data);
return foundNode;
}
}
else
return null;
}
where do i make mistake?!
if you have a better idea for converting a BT to TBT , So please help me!
NOTE that my tree is a binary one NOT Binary search
also my biuldTree method
public Node BuildTree(int inorder, int preorder, int instart, int inend)
{
if (instart > inend)
return null;
if (preindex >= inorder.Length)
return null;
int pickedpre = preorder[preindex];
preindex++;
Node newnode = new Node(pickedpre);
if (instart == inend)
return newnode;
for (int i = 0; i < inorder.Length; i++)
{
if (inorder[i] == pickedpre)
{
inindex = i;
break;
}
}
newnode.leftChild = BuildTree(inorder, preorder, instart, inindex - 1);
newnode.rightChild = BuildTree(inorder, preorder, inindex + 1, inend);
root = newnode;
return newnode;
}
c# binary-tree binary-search-tree
c# binary-tree binary-search-tree
edited Dec 29 '18 at 2:24
Daniel A. White
148k36293372
asked Dec 29 '18 at 2:17
ali 4langiali 4langi
104
edited Dec 29 '18 at 2:24
Daniel A. White
148k36293372
asked Dec 29 '18 at 2:17
ali 4langiali 4langi
104
edited Dec 29 '18 at 2:24
Daniel A. White
148k36293372
edited Dec 29 '18 at 2:24
Daniel A. White
148k36293372
edited Dec 29 '18 at 2:24
Daniel A. White
148k36293372
148k36293372
asked Dec 29 '18 at 2:17
ali 4langiali 4langi
104
asked Dec 29 '18 at 2:17
ali 4langiali 4langi
104
asked Dec 29 '18 at 2:17
ali 4langiali 4langi
104
104
Where does the StackOverlow exception occur? In your Search or your BuildTree method?
– Klaus Gütter
Dec 29 '18 at 6:52
@KlausGütter StackOverlow exception occur in my Search method.BuildTree is fine.the problem is with either Search or ConvertToTBT method. when i trace search method , for the third node to thread, it can not get outside the search method
– ali 4langi
Dec 29 '18 at 9:49
@KlausGütter this is my project for Data Structure.i really got tired on this! i can explain my code if needed
– ali 4langi
Dec 29 '18 at 9:59
Your Search method will Stack-overflow if your "tree" contains cycles, i.e. if a left_child or right_child references a node that has already been visited. You might add some additional code to your ConvertToTBT method to verify that this invariant is maintained.
– Klaus Gütter
Dec 29 '18 at 12:49
Can you provide full code so I can run it and try to understand better what you try to accomplish?
– Aldert
Dec 29 '18 at 16:41
add a comment |
Where does the StackOverlow exception occur? In your Search or your BuildTree method?
– Klaus Gütter
Dec 29 '18 at 6:52
@KlausGütter StackOverlow exception occur in my Search method.BuildTree is fine.the problem is with either Search or ConvertToTBT method. when i trace search method , for the third node to thread, it can not get outside the search method
– ali 4langi
Dec 29 '18 at 9:49
@KlausGütter this is my project for Data Structure.i really got tired on this! i can explain my code if needed
– ali 4langi
Dec 29 '18 at 9:59
Your Search method will Stack-overflow if your "tree" contains cycles, i.e. if a left_child or right_child references a node that has already been visited. You might add some additional code to your ConvertToTBT method to verify that this invariant is maintained.
– Klaus Gütter
Dec 29 '18 at 12:49
Can you provide full code so I can run it and try to understand better what you try to accomplish?
– Aldert
Dec 29 '18 at 16:41
Where does the StackOverlow exception occur? In your Search or your BuildTree method?
– Klaus Gütter
Dec 29 '18 at 6:52
Where does the StackOverlow exception occur? In your Search or your BuildTree method?
– Klaus Gütter
Dec 29 '18 at 6:52
@KlausGütter StackOverlow exception occur in my Search method.BuildTree is fine.the problem is with either Search or ConvertToTBT method. when i trace search method , for the third node to thread, it can not get outside the search method
– ali 4langi
Dec 29 '18 at 9:49
@KlausGütter StackOverlow exception occur in my Search method.BuildTree is fine.the problem is with either Search or ConvertToTBT method. when i trace search method , for the third node to thread, it can not get outside the search method
– ali 4langi
Dec 29 '18 at 9:49
@KlausGütter this is my project for Data Structure.i really got tired on this! i can explain my code if needed
– ali 4langi
Dec 29 '18 at 9:59
@KlausGütter this is my project for Data Structure.i really got tired on this! i can explain my code if needed
– ali 4langi
Dec 29 '18 at 9:59
Your Search method will Stack-overflow if your "tree" contains cycles, i.e. if a left_child or right_child references a node that has already been visited. You might add some additional code to your ConvertToTBT method to verify that this invariant is maintained.
– Klaus Gütter
Dec 29 '18 at 12:49
Your Search method will Stack-overflow if your "tree" contains cycles, i.e. if a left_child or right_child references a node that has already been visited. You might add some additional code to your ConvertToTBT method to verify that this invariant is maintained.
– Klaus Gütter
Dec 29 '18 at 12:49
Can you provide full code so I can run it and try to understand better what you try to accomplish?
– Aldert
Dec 29 '18 at 16:41
Can you provide full code so I can run it and try to understand better what you try to accomplish?
– Aldert
Dec 29 '18 at 16:41
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
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%2f53966170%2fproblem-in-converting-a-binary-tree-to-a-threaded-binary-tree%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
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%2f53966170%2fproblem-in-converting-a-binary-tree-to-a-threaded-binary-tree%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
Where does the StackOverlow exception occur? In your Search or your BuildTree method?
– Klaus Gütter
Dec 29 '18 at 6:52
@KlausGütter StackOverlow exception occur in my Search method.BuildTree is fine.the problem is with either Search or ConvertToTBT method. when i trace search method , for the third node to thread, it can not get outside the search method
– ali 4langi
Dec 29 '18 at 9:49
@KlausGütter this is my project for Data Structure.i really got tired on this! i can explain my code if needed
– ali 4langi
Dec 29 '18 at 9:59
Your Search method will Stack-overflow if your "tree" contains cycles, i.e. if a left_child or right_child references a node that has already been visited. You might add some additional code to your ConvertToTBT method to verify that this invariant is maintained.
– Klaus Gütter
Dec 29 '18 at 12:49
Can you provide full code so I can run it and try to understand better what you try to accomplish?
– Aldert
Dec 29 '18 at 16:41