-
Binary Trees?
Well, now I've learned linked lists and stacks, now how do I go about making a binary tree? How about implementing it in a practical application?
And while we're at it, give me a bunch of problems involving stacks and linked lists! Post your homework assignments! (Of course, I won't post the code, I just want the exercises)
-
do a RADIX sort using linked lists.
or for a more complex tree scenario, do huffman coding of a text file.
-
>>now how do I go about making a binary tree?
A binary tree is really just a linked list with two forward links instead of one :-)
Code:
#include <iostream>
#include <cstdlib>
using namespace std;
struct link {
int num;
link *left;
link *right;
link(int init, link *l = 0, link *r = 0): num(init), left(l), right(r){}
};
link *add(link *root, int num)
{
if (root == 0)
{
root = new link(num);
}
else if (num < root->num)
{
root->left = add(root->left, num);
}
else if (num > root->num)
{
root->right = add(root->right, num);
}
else
{
// Ignore duplicates
}
return root;
}
void print(link *root)
{
if (root == 0)
{
return;
}
print(root->left);
cout<< root->num <<flush;
print(root->right);
}
void destroy(link *root)
{
if (root == 0)
{
return;
}
destroy(root->left);
destroy(root->right);
delete root;
}
int main()
{
link *root = 0;
for (int i = 0; i < 10; i++)
{
root = add(root, rand() % 10);
}
print(root);
destroy(root);
}
-
>now how do I go about making a binary tree? How about implementing it in a practical application?
A practical application of binary trees is searching. Develop functions to create and maintain a binary tree and develop functions to perform actions like searching on it.
-
Huffman codes are good, also make a priority queue using a tree.
-
Binary trees are a common data structure. You should have no problem finding examples or discussion on the internet or in university libararies.