Tree

[voidStream]

How would I go about creating a tree like structure using linked lists, I am thinking of making a rubix cube solver program, what I want to do create nodes that each do one operation like turn left, right, up, down but I dont know how to go about starting this

[AbstractionAnon]

Search this web site. There are a lot of threads about trees and nodes.

That said, you need to start by have an understanding of the data structures you're going to represent and how you're going to operate on them.

[Duthomhas]

Basic Linked List

A linked list is a structure with a pointer to another of the same type of structure.

struct node_t
  {
  int     value;
  node_t* next;
  };

I find it exceedingly useful to have a constructor that allows you to push a new node on the front of the list.

struct node_t
  {
  int     value;
  node_t* next;

  node_t( int value, node_t* next = NULL ): value( value ), next( next ) { }
  };

Now you can easily create a linked list:

1 2 3 4 5 6 7 8

node_t* head; head = new node_t( 3 ); head = new node_t( 2, head ); head = new node_t( 1, head ); for (node_t* n = head; n != NULL; n = n->next) cout << n->value << " ";

1 2 3

It is worth your time to add additional functions (member or not, it doesn't matter) that do things for you like count the number of nodes, find the end of the list, add or delete nodes, etc.

Doubly-Linked List

A doubly-linked list has two pointers -- one for the next and one for the previous.

struct node_t
  {
  int     value;
  node_t* next;
  node_t* prev;
  
  node_t( int value, node_t* next = NULL, node_t* prev = NULL ): 
    value( value ), next( next ), prev( prev ) 
    { }
  };

Bookkeeping becomes a bit more complicated, but it's not hard to follow if you get out a piece of paper and a pencil and draw how to insert and remove a node.

But enough of that. On to:

Linked Trees
This is where the interesting stuff starts. A tree is a linked list where there is more than one 'next' node. A binary tree is one where each node has two children:

struct node_t
  {
  int     value;
  node_t* next[ 2 ];
  };

Keep in mind that, just like a regular linked list, one or both 'next' node pointers may be null. And, as with the doubly-linked list, bookkeeping becomes even more difficult to follow. (Don't forget the paper and pencil!)

Now it becomes really important to have all the bookkeeping functions/methods to manage the list, such as adding a node or balancing the tree.


Rubik's Cube

I don't think you really need linked-anything to solve the cube... You do need to track the cube's state, but there are better ways to do it, particularly as it applies to the method to track moves to make.

Check out the Wikipedia article on solving the Rubik's cube. There are some good pointers there.
http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube

Good luck!