How to create a tree using linked lists?

[tabseeker]

Although this question can be found in every books of C++，but I still think it is too complicated. So I want to create an easier version using linked lists, however, I have to create a list class, which is in turn requiring to create a class as the tree does, so how can I settle it? IF I build a tree based on list class, is it valid in C++， hope someone can help me！

[Mattrang]

What tree are you going to build ? An AVL, a binary tree can be built easier and believe me you can't use a list to build a tree. Look at the definitions and properties of tree and list. Things are as clear as crystal. What do you think ?

[philkr]

A binary tree is not difficult:

class Node
{
public:
  Node(value) { nValue = value; pLeft = pRight = NULL; }

  Node* pLeft;
  Node* pRight;
  int nValue;  // or any other data
}

class Tree
{
public:
  Node* pRoot;
  Tree() { pRoot = NULL; }

  Node* search(int value); //...
  void createLeaf(int value); //...
  // ...
}

[tabseeker]

Thank you! I will have a try.

[Odiee]

you can use lists to build a tree or to load tree structure from it but u must figure it out how to store data in colums. something like this:

NUM | NODE_ID | LEVEL | PARENT | NAME
1             836          0          NULL      root
2             33            1          836        node1
3             43            1          836        node2
4             77            2          33          node1_1

get the point?
after that u just have to write method that will load it in your TRee object
witch might look something like this

class oNode
{
 CString name;
 int ID;
 oNode *pparent;
 typdef vector<oNode*>my_child_nodes;
 my_child_nodes my_nodes;
 get ...
 set ... 
 ...
};

class oTree
{
 typedef vector <oNode *>root_nodes;
 root_nodes root;
 oNode *find(ID);
 oNode *putnode(oNode *node_in)
};

where oTree::find is recursive function witch will return pointer on node you want to put more nodes in.
Hope this helps.

[tabseeker]

Thx！But which is more efficient？ the one using linked lists or just random storage by the "new" operator?
BTW, if I want to implement an expression tree, and wish to have unary and binary operator in it, should I turn to multiway trees？Can I just calculate the unary operator with its operand at once, then store it as one operand?