-1

Hey guys I have an assignment that I am completely stuck on. I have a binary tree class that has to be converted to a linked list class that was given to me. The way I was thinking of doing it was just making a function that passes in a root and the linked list and just pushing the root to the front of the linked list then calling the function again for root->right and root->left and passing in the same linked list so it stays updated. Unfortunately, this results in a linked list that is only the first root passed into the function for some reason. Any suggestions on what my issue could be?

Joerob624
  • 1
  • 1
  • Can't help if you don't give us anything to work with. (i.e. code, errors, return values...) – m_callens May 01 '17 at 19:55
  • Fix either your binary tree traversal, or your linked list insertion functions. One or both functions were buggy to being with if you can't simply traverse your tree, and on each node, just call `linkedlist.add()` or whatever function name you chose. – PaulMcKenzie May 01 '17 at 19:55
  • Without any code to look at, my Orb of Seeing is telling me that your issue is on line 42 and that you should not panic. – Thomas Matthews May 01 '17 at 20:00
  • Sorry, I wish I could post code, but my teacher doesn't like others helping that much. Basically I have an if statement of root != null, push the data in the front, then the two recursion statements with root->left and root->right – Joerob624 May 01 '17 at 20:37
  • It might have to do with me passing the linked list into the function each time? – Joerob624 May 01 '17 at 20:38
  • So you don't have a function that traverses your binary tree and visits each node in whatever order (inorder, postorder, preorder, breadth-first, depth-first)? That's all you need to build your linked list. Then the "visit" function would be just to insert the visited node's value to the front of the list. Like I said, if you have a function that visits each node, and your linked list function to add to the front of the list is working, this shouldn't have taken more than 5 or 10 minutes, since that is 99% of the work done. – PaulMcKenzie May 01 '17 at 21:20
  • No I don't have a function that does this, I believe I'm supposed to do it within the function that moves the binary tree to a linked list. I'm mainly having issues knowing where to declare the linked list because each him the recursion happens, it's resetting the linked list back to fresh – Joerob624 May 02 '17 at 01:59

1 Answers1

0

Follow this routine:

1: Traverse the tree (use postorder traversal).

2: Make the first node to be printed/processed by this traversal method as the head of the linked list and then add on the leaves subsequently to this LL.

  • I am trying this but it does not seem to work correctly. My linked list class does not have a function to make somehting the head of the list, but it has a push_front function which puts whatever is in the argument to the front of the linked list, so this is what I am using. Where do I delcare the linked list? I have it passed as an argument to the function but I think this might be where my mistake is – Joerob624 May 01 '17 at 20:53
  • *My linked list class does not have a function to make somehting the head of the list, but it has a push_front function which puts whatever is in the argument to the front of the linked list,* -- I don't understand -- putting an item at the front of the list **is** making it the head of the list. Also, if you can't pass your linked list to another function, regardless of what that function does, what good is the linked list? First, you need to specify what is your "linked list"? Is it a full-blown linked list class, or is it disjointed, free-standing code? – PaulMcKenzie May 01 '17 at 21:15
  • Its a full-blown linked list class. By the sounds of it, my function should be working but it is only putting one item in the linked list for some reason. – Joerob624 May 01 '17 at 21:34
  • And you're passing the linked list object how? `void merge(linked_list& myList);` -- Like that? You should really be posting, at the very least *how* you're calling your functions. – PaulMcKenzie May 01 '17 at 21:52
  • LL toLL_aux(binarytree::treenode* root, LL tempList) this is how I'm calling the function – Joerob624 May 01 '17 at 22:05
  • I'm pretty new to c++ so I probably am referencing the linked list wrong in my function definition or something along those lines – Joerob624 May 01 '17 at 23:34
  • @Joerob624 You are passing and returning your linked list by value. That means that copies of your linked list will be made, thus it better have correct copy semantics. This means that your copy constructor, assignment operator, and destructor better work properly. From what you've described, they do not work correctly or you forgot to override these operations. Read up on the [rule of 3](http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three). – PaulMcKenzie May 02 '17 at 02:13
  • Would it be better to have two functions, one that traverses the tree, and one that appends the current root to the linked list, then call the second one in the first function so each time it goes through it will add that root to the linked list? – Joerob624 May 02 '17 at 02:18
  • @Joerob624 That isn't the problem. I think you have the basic operations already coded. The problem is that you are not copying your linked lists properly by not implementing the requisite copy / assignment / destruction operations. It seems you [fell into this trap](http://stackoverflow.com/questions/43689025/how-to-merge-two-b-trees-). Read the last comment that I made. – PaulMcKenzie May 02 '17 at 02:19
  • The linked list class was given to me and definitely has the big 3 implemented correctly, so it must be the way I am using it that is incorrect. – Joerob624 May 02 '17 at 02:22
  • Without seeing it, nothing can be said about it. Also, school / teacher implementations are usually flawed, believe me. Second, you don't need any functions except one that visits each node in the binary tree and adds the value to the linked list. I've mentioned this 3 times already -- if you don't have a function to traverse the tree, then the tree is lacking in basic functionality. Last, you should be passing the linked list object by reference, not by value. – PaulMcKenzie May 02 '17 at 02:24
  • In class at the moment, but I will try some stuff out with the info you have given me. Thank you! – Joerob624 May 02 '17 at 02:30