Hey iMalc,
thanks for posting the code. I have one question though. to insert multiple nodes, wouldn't you still have to run your function through a for loop or recursively in the function?
efficiently inserting nodes into a binary search tree using linked lists?
You certainly have to call it once for each node you wish to insert. You would obviously use a simple loop for this if you have a lot to insert at once. There is no need to recurse for that though. The function as written also relies on caller allocation, btw.
You could use it like this to sort an array for example (not that I'm suggesting that would be a good usage):Minimal use of recursion again, as you can see.
You could use it like this to sort an array for example (not that I'm suggesting that would be a good usage):
template <class T>struct Node { Node *left, *right; T item; inline bool operator < (const Node &rhs) { return item < rhs.item; }};template <class T, class Size, class TNode>void TreeDumpToArray(T a[], Size &idx, TNode *node) { while (node != NULL) { TreeDumpToArray(a, idx, node->left); a[idx++] = node->item; node = node->right; }}template <class T, class Size>void BinaryTreeSort(T a[], Size n) { Size idx=0; Node<T> *head=NULL, *const buf = (Node<T>* const)malloc(sizeof(Node<T>) * n); for (Size i=0; i<n; ++i) { buf.item = a; TreeInsert(head, &buf); } TreeDumpToArray(a, idx, head); free(buf);}int main() { int foobar[8]; for (int i=0; i<8; ++i) foobar := rand()%100; BinaryTreeSort(foobar, 8); for (int i=0; i<8; ++i) cout << foobar << endl;}
Uhh, I might have missed something. How do you plan to store vertices in a BST?
The application isn't very useful. You might want to now code a BSP tree which is much more useful for 3d geometry.
If you want to find something to do with your BST make a symbol table or use it for parsing text.
If you want to have more fun now implement red-black trees and avl-trees. These are BSTs which will approximate a balanced tree in different ways. These are usually more useful than a simple BST because you are guaranteed (most of the time) faster lookups.
The application isn't very useful. You might want to now code a BSP tree which is much more useful for 3d geometry.
If you want to find something to do with your BST make a symbol table or use it for parsing text.
If you want to have more fun now implement red-black trees and avl-trees. These are BSTs which will approximate a balanced tree in different ways. These are usually more useful than a simple BST because you are guaranteed (most of the time) faster lookups.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
