Thread: 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);
}

Binary trees are a common data structure. You should have no problem finding examples or discussion on the internet or in university libararies.