A disjoint Set can be used for creating minimal spanning trees.
The union-find algorithm is fast, faster than linked lists for some uses.
See: Wikipedia Disjoint Set

It's fast and simple. Just add a DisjointSetNode object to the
objects that you want to create a tree of.

# This is a disjoint set implementing union-find
# It can be used for generating a minimal spanning
# tree using Kruskal's algorithm.
# http://en.wikipedia.org/wiki/Kruskal's_algorithm

class DisjointSetNode
  attr_accessor :parent, :rank

  def initialize
    @parent = self
    @rank = 0
  end

  # An optimised union by rank. Attaches smaller tree to larger.
  def union(other)
    self_root = self.find
    other_root = other.find
    if self_root.rank > other_root.rank
      other_root.parent = self_root
    elsif self_root.rank < other_root.rank
      self_root.parent = other_root
    elsif self_root != other_root
      other_root.parent = self_root
      self_root.rank += 1
    end
  end

  def find
    if self.parent === self
      self
    else
      self.parent = self.parent.find
    end
  end

end   # class DisjointSetNode

Some simple test code:

require 'disjointsetnode'
require 'test/unit'
require 'test/unit/ui/console/testrunner'

    class DisjointSetTest < Test::Unit::TestCase
      N_Nodes = 1000

      def setup
        @nodes = Array.new
        (1..N_Nodes).each do |node|
        @nodes << DisjointSetNode.new
        end
      end

      # def teardown
      # end

      def test_creation
        @nodes.each do |node|
          assert !node.nil?, "A Node is nil!"
        end
      end

      def test_initial_values
        @nodes.each do |node|
          assert node.parent === node, "self #{node}, parent #{node.parent} not equal."
          assert node.rank == 0, " A node's rtank is not 0."
        end
      end

      def test_union
        # Join all nodes in sequence
        @nodes.each do |node|
          if !@lastnode.nil?
            node.union(@lastnode)
            node_f = node.find
            lnode_f = @lastnode.find
            assert node_f == lnode_f, "Join not completed: node_f: #{node_f}, lnode_f: #{lnode_f}"
          end
          @lastnode = node
        end
      end

      def test_random_union
        (1..N_Nodes-1).each do |n|
          node = @nodes[n]
          other = @nodes[rand(N_Nodes-1)]
          node.union(other)
          node_f = node.find
          onode_f = other.find
          assert node_f == onode_f, "Join not completed: node_f: #{node_f}, onode_f: #{onode_f}"
        end
      end
    end

# This runs the tests for ya! 
Test::Unit::UI::Console::TestRunner.run(DisjointSetTest)

The is a straight-forward implementation of Prim's Algorithm for finding the minimum spanning tree of a graph.

A detailed explanation is given here.

#include <stdio.h>

/*
	The input file (weight.txt) look something like this
		4
		0 0 0 21
		0 0 8 17
		0 8 0 16
		21 17 16 0

	The first line contains n, the number of nodes.
	Next is an nxn matrix containg the distances between the nodes
	NOTE: The distance between a node and itself should be 0
*/

int n; /* The number of nodes in the graph */

int weight[100][100]; /* weight[i][j] is the distance between node i and node j;
			if there is no path between i and j, weight[i][j] should
			be 0 */

char inTree[100]; /* inTree[i] is 1 if the node i is already in the minimum
			spanning tree; 0 otherwise*/

int d[100]; /* d[i] is the distance between node i and the minimum spanning
		tree; this is initially infinity (100000); if i is already in
		the tree, then d[i] is undefined;
		this is just a temporary variable. It's not necessary but speeds
		up execution considerably (by a factor of n) */

int whoTo[100]; /* whoTo[i] holds the index of the node i would have to be
			linked to in order to get a distance of d[i] */

/* updateDistances(int target)
	should be called immediately after target is added to the tree;
	updates d so that the values are correct (goes through target's
	neighbours making sure that the distances between them and the tree
	are indeed minimum)
*/
void updateDistances(int target) {
	int i;
	for (i = 0; i < n; ++i)
		if ((weight[target][i] != 0) && (d[i] > weight[target][i])) {
			d[i] = weight[target][i];
			whoTo[i] = target;
		}
}

int main(int argc, char *argv[]) {
	FILE *f = fopen("dist.txt", "r");
	fscanf(f, "%d", &n);
	int i, j;
	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j)
			fscanf(f, "%d", &weight[i][j]);
	fclose(f);

	/* Initialise d with infinity */
	for (i = 0; i < n; ++i)
		d[i] = 100000;

	/* Mark all nodes as NOT beeing in the minimum spanning tree */
	for (i = 0; i < n; ++i)
		inTree[i] = 0;

	/* Add the first node to the tree */
	printf("Adding node %c\n", 0 + 'A');
	inTree[0] = 1;
	updateDistances(0);

	int total = 0;
	int treeSize;
	for (treeSize = 1; treeSize < n; ++treeSize) {
		/* Find the node with the smallest distance to the tree */
		int min = -1;
		for (i = 0; i < n; ++i)
			if (!inTree[i])
				if ((min == -1) || (d[min] > d[i]))
					min = i;

		/* And add it */
		printf("Adding edge %c-%c\n", whoTo[min] + 'A', min + 'A');
		inTree[min] = 1;
		total += d[min];

		updateDistances(min);
	}

	printf("Total distance: %d\n", total);

	return 0;
}

EvalExp(s) turns the string s into an expression tree and returns it.

Inorder, preorder and postorder can then be used to turn transform the tree into inorder, preorder or postorder expressions.

function inorder(T) {
  if ((T.cargo  == '+') || (T.cargo  == '-') || (T.cargo  == '*') || (T.cargo  == '/'))
    return [].concat(inorder(T.left)).concat(T.cargo).concat(inorder(T.right));

  return new Array(T.cargo);
}

function preorder(T) {
  if ((T.cargo  == '+') || (T.cargo  == '-') || (T.cargo  == '*') || (T.cargo  == '/'))
    return [].concat(T.cargo).concat(preorder(T.left)).concat(preorder(T.right));

  return new Array(T.cargo);
}

function postorder(T) {
  if ((T.cargo  == '+') || (T.cargo  == '-') || (T.cargo  == '*') || (T.cargo  == '/'))
    return [].concat(postorder(T.left)).concat(postorder(T.right)).concat(T.cargo);

  return new Array(T.cargo);
}

function Tree(cargo, left, right) {
  this.cargo = cargo;
  this.left = left;
  this.right = right;
}

function split(s) {
  var r = [];
  var cur = '';
  for (var i = 0; i < s.length; ++i) {
    var c = s.charAt(i);
    if ((c == '+') || (c == '-') || (c == '*') || (c == '/') || (c == '(') || (c == ')')) {
      cur.replace(" ", "");
      if (cur.length > 0) {
        r.push(cur);
        cur = '';
      }
      r.push(c);
    } else {
      cur += c;
    }
  }
  if (cur.length > 0)
    r.push(cur);

  return r;
}

function getToken(tokens, expected) {
  if (tokens[0] == expected) {
    tokens.splice(0, 1);
    return true;
  }
    return false;
}

function getVar(tokens) {
  if (getToken(tokens, '(')) {
    var a = getSum(tokens);
    getToken(tokens, ')');

    return a;
  } else {
    var aux = tokens[0];
    tokens.splice(0, 1);

    return new Tree(aux, undefined, undefined);
  }
}

function getProduct(tokens) {
  var a = getVar(tokens);

  if (getToken(tokens, '*')) {
    var b = getProduct(tokens);

    return new Tree('*', a, b);
  } else if (getToken(tokens, '/')) {
    var b = getProduct(tokens);

    return new Tree('/', a, b);
  }

  return a;
}

function getSum(tokens) {
  var a = getProduct(tokens);

  if (getToken(tokens, '+')) {
    var b = getSum(tokens);

    return new Tree('+', a, b);
  } else if (getToken(tokens, '-')) {
    var b = getSum(tokens);

    return new Tree('-', a, b);
  }

  return a;
}

function evalExp(s) {
  var tokens = split(s);

  //alert(tokens);

  return t = getSum(tokens);
}

Simplest AST visitor. More on this blog post :
http://www.biais.org/blog/index.php/2007/01/10/9-visit-python-abstract-syntax-tree

import compiler
 
class CodePrinter:
    def __init__(self):
        self.src = ''
 
    def visitName(self,t):
        self.src += t.name
 
    def visitConst(self,t):
        self.src += str(t.value)
 
    def visitStmt(self, t):
        for i in t:
            a = pretty_print(i)
            self.src += a + "\n"
 
    def visitAssName(self, t):
        self.src += t.name + " = "
 
def pretty_print(node):
    myvisitor = CodePrinter()
    # compiler.walk return the visitor instance : 2nd arg
    return compiler.walk(node, myvisitor).src

You should have a categories table with a parent_id field. Root categories should have the parent_id of 0.

I modified this post:
http://www.bigbold.com/snippets/posts/show/296

because the first one worked if you did stuff in your view to make the root categories come up, but I agree with the commenter that things should be contained to the helper - however I've managed to break the DRY rule in doing so. If anyone has any suggestions for a better way around this I'd love to hear it, so please comment. So anyway.. this should list your root categories ONLY and NOT your other sub-cats as well so that you have a very pretty little tree.

Slap this in your view:

<%= display_categories(@categories) %>

And put this in a helper file. You'll need it in the application helper most likely since you'll want to call it from multiple views.

      def display_categories(categories)
	    	   ret = "<ul>"
	   for category in categories
		   if category.parent_id == 0
			ret += "<li>"
			ret += link_to category.name
			ret += find_all_subcategories(category)
			ret += "</li>"
		   end
		   
	   end
	   ret += "</ul>"
    end
    
   def find_all_subcategories(category)
    if category.children.size > 0
      ret = '<ul>'
      category.children.each { |subcat| 
        if subcat.children.size > 0
          ret += '<li>'
          ret += link_to h(subcat.name), :action => 'edit', :id => subcat
          ret += find_all_subcategories(subcat)
          ret += '</li>'
        else
          ret += '<li>'
          ret += link_to h(subcat.name), :action => 'edit', :id => subcat 
          ret += '</li>'
        end
        }
      ret += '</ul>'
    end
  end

unit StreamAdapter.pas

//+ Jonas Raoni Soares Silva
//@ http://jsfromhell.com

unit StreamAdapter;

interface

uses
  Classes;

type
  IStream = interface( IInterface )
    ['{FBEF199A-09BC-4B61-89EA-1EF8B22C93A5}']
    function Read(var Buffer; const Count: Longint): Longint;
    function Write(const Buffer; const Count: Longint): Longint;
    function Seek(const Offset: Int64; Origin: TSeekOrigin): Int64;
    procedure ReadBuffer(var Buffer; const Count: Longint);
    procedure WriteBuffer(const Buffer; const Count: Longint);
    function CopyFrom(Source: TStream; const Count: Int64): Int64;
    function WriteTo(Dest: TStream; const Count: Int64): Int64;

    procedure SetPosition( const Value: Int64 );
    procedure SetSize( const Value: Int64 );
    function GetPosition: Int64;
    function GetSize: Int64;

    property Position: Int64 read GetPosition write SetPosition;
    property Size: Int64 read GetSize write SetSize;
  end;

  TStreamAdapter = class( TInterfacedObject, IStream )
  private
    FStream: TStream;
    procedure SetPosition( const Value: Int64 );
    procedure SetSize( const Value: Int64 );
    function GetPosition: Int64;
    function GetSize: Int64;

  public
    constructor Create( Stream: TStream );
    destructor Destroy; override;

    function Read(var Buffer; const Count: Longint): Longint;
    function Write(const Buffer; const Count: Longint): Longint;

    procedure ReadBuffer(var Buffer; const Count: Longint);
    procedure WriteBuffer(const Buffer; const Count: Longint);

    function CopyFrom(Source: TStream; const Count: Int64): Int64;
    function WriteTo(Dest: TStream; const Count: Int64): Int64;

    function Seek(const Offset: Int64; Origin: TSeekOrigin): Int64;

    property Position: Int64 read GetPosition write SetPosition;
    property Size: Int64 read GetSize write SetSize;
  end;

implementation

{ TStreamAdapter }

function TStreamAdapter.CopyFrom(Source: TStream; const Count: Int64): Int64;
begin
  Result := FStream.CopyFrom( Source, Count );
end;

constructor TStreamAdapter.Create(Stream: TStream);
begin
  FStream := Stream;
end;

destructor TStreamAdapter.Destroy;
begin
  FStream.Free;
  inherited;
end;

function TStreamAdapter.GetPosition: Int64;
begin
  Result := FStream.Position;
end;

function TStreamAdapter.GetSize: Int64;
begin
  Result := FStream.Size;
end;

function TStreamAdapter.Read(var Buffer; const Count: Integer): Longint;
begin
  Result := FStream.Read( Buffer, Count );
end;

procedure TStreamAdapter.ReadBuffer(var Buffer; const Count: Integer);
begin
  FStream.ReadBuffer( Buffer, Count );
end;

function TStreamAdapter.Seek(const Offset: Int64;
  Origin: TSeekOrigin): Int64;
begin
  Result := FStream.Seek( Offset, Origin );
end;

procedure TStreamAdapter.SetPosition(const Value: Int64);
begin
  FStream.Position := Value;
end;

procedure TStreamAdapter.SetSize(const Value: Int64);
begin
  FStream.Size := Value;
end;

function TStreamAdapter.Write(const Buffer; const Count: Integer): Longint;
begin
  Result := FStream.Write( Buffer, Count );
end;

procedure TStreamAdapter.WriteBuffer(const Buffer; const Count: Integer);
begin
  FStream.WriteBuffer( Buffer, Count );
end;

function TStreamAdapter.WriteTo(Dest: TStream; const Count: Int64): Int64;
begin
  Result := Dest.CopyFrom( FStream, Count );
end;

end.

unit PersistentTree.pas

//+ Jonas Raoni Soares Silva
//@ http://jsfromhell.com

unit PersistentTree;

interface

uses
  Windows, Classes, SysUtils, StreamAdapter;

type
  EPersistentTree = class( Exception );

  TPersistentTree = class;

  TPersistentTreeClass = class of TPersistentTree;

  TPersistentTree = class( TStream )
  private
    FStream: IStream;
    FList: TList;
    FBaseClass: TPersistentTreeClass;
    FOwner, FParent: TPersistentTree;
    FOwnStream: Boolean;
    FDataFilename, FFilename: string;
    FLastPosition, FDataBegin, FDataLength: Int64;

    function GetItem(const Index: Integer): TPersistentTree;
    function GetCount: Integer;
    function GetStream: TStream;
    function Import( Item: TPersistentTree ): Boolean;
    procedure ClearData;
    procedure RecreateStream( const Pos: Int64; const Deep: Boolean = False );
    procedure Synchronize;

  protected
    //override to provide writing/reading notifications
    procedure Loaded; virtual;
    procedure Saving; virtual;

    //derived from TStream
    function GetSize: Int64; override;
    procedure SetSize(NewSize: Longint); override;
    procedure SetSize(const NewSize: Int64); override;

  public
    constructor Create; virtual;
    destructor Destroy; override;

    //derived from TStream
    function Read( var Buffer; Count: Longint ): Longint; override;
    function Write( const Buffer; Count: Longint ): Longint; override;
    function Seek(const Offset: Int64; Origin: TSeekOrigin): Int64; override;

    function Truncate: Int64;
    function ReadString: string;
    procedure WriteString( const Data: string );

    procedure Save( const AFilename: string ); overload;
    procedure Save( Stream: TStream ); overload;
    procedure Load( const AFilename: string ); overload;
    procedure Load( Stream: IStream ); overload;
    procedure Load( Stream: TStream ); overload;

    function Add: TPersistentTree; overload;
    function Add( Item: TPersistentTree ): Integer; overload;
    procedure Insert( const Index: Integer; Item: TPersistentTree);
    function IndexOf( Item: TPersistentTree ): Integer;
    function Remove( Item: TPersistentTree ): Integer;
    procedure Delete( const Index: Integer);
    function Extract( Item: TPersistentTree ): TPersistentTree;
    procedure Exchange( const IndexA, IndexB: Integer );
    procedure Move(const CurIndex, NewIndex: Integer);
    procedure Clear;

    property Items[ const Index: Integer ]: TPersistentTree read GetItem; default;
    property Count: Integer read GetCount;
    property Owner: TPersistentTree read FOwner;
    property Parent: TPersistentTree read FParent;
    property Filename: string read FFilename;
    property BaseClass: TPersistentTreeClass read FBaseClass write FBaseClass;
  end;

  TPersistentTreeHeader = packed record
    Sig: array[0..4] of Char;
    Ver: Word;
  end;

const
  PERSISTENT_TREE_HEADER: TPersistentTreeHeader = ( Sig: 'PTREE'; Ver: 1 );

function GetTempFile: string;


implementation

function GetTempFile: string;
var
  Path: array[0..MAX_PATH-1] of Char;
begin
  GetTempPath( MAX_PATH, Path );
  GetTempFileName( Path, 'BUF', 0, Path );
  Result := Path;
end;

{ TPersistentTree }

procedure TPersistentTree.Clear;
var
  I: Integer;
begin
  for I := FList.Count - 1 downto 0 do
  begin
    TPersistentTree( FList[I] ).Free;
    FList.Delete( I );
  end;
end;

constructor TPersistentTree.Create;
begin
  FBaseClass := TPersistentTreeClass( Self.ClassType );
  FList := TList.Create;
  FStream := TStreamAdapter.Create( GetStream );
  FOwnStream := True;
end;

destructor TPersistentTree.Destroy;
begin
  ClearData;
  FList.Free;
  inherited;
end;

procedure TPersistentTree.Exchange(const IndexA, IndexB: Integer);
begin
  FList.Exchange( IndexA, IndexB );
end;

function TPersistentTree.GetCount: Integer;
begin
  Result := FList.Count;
end;

function TPersistentTree.GetItem(const Index: Integer): TPersistentTree;
begin
  Result := FList[ Index ];
end;

function TPersistentTree.IndexOf(
  Item: TPersistentTree): Integer;
begin
  Result := FList.IndexOf( Item );
end;

procedure TPersistentTree.Load(const AFilename: string);
var
  FS: TFileStream;
  //Header: TPersistentTreeHeader;
begin
  FS := TFileStream.Create( AFilename, fmOpenRead or fmShareDenyWrite );
  try
    //FS.Read( Header, SizeOf( TPersistentTreeHeader ) );
    //if not CompareMem( @Header, @PERSISTENT_TREE_HEADER, SizeOf( TPersistentTreeHeader ) ) then
    //  raise EPersistentTree.CreateFmt( '%s.LoadFromFile :: "%s" Not Recognized', [ClassName, AFilename] );
    Load( FS );
    FFilename := AFilename;
  except
    FS.Free;
    raise;
  end;
end;

procedure TPersistentTree.Load(Stream: TStream);
begin
  Load( TStreamAdapter.Create( Stream ) );
end;

function TPersistentTree.Remove(Item: TPersistentTree): Integer;
begin
  Result := FList.Remove( Item );
  if Result >= 0 then
    Item.Free;
end;

procedure TPersistentTree.Save( const AFilename: string );
var
  FS: TFileStream;
begin
  FS := TFileStream.Create( AFilename, fmCreate or fmShareDenyWrite );
  try
    //FS.Write( PERSISTENT_TREE_HEADER, SizeOf( TPersistentTreeHeader ) );
    Save( FS );
  finally
    FS.Free;
  end;
end;

procedure TPersistentTree.Save(Stream: TStream);
var
  I: LongInt;
begin
  Seek( 0, soBeginning );
  Saving;

  FDataLength := Size;
  Stream.Write( FDataLength, SizeOf( FDataLength ) );
  Stream.CopyFrom( Self, 0 );

  I := FList.Count;
  Stream.Write( I, SizeOf( I ) );
  for I := 0 to FList.Count-1 do
    Self[I].Save( Stream );
end;

function TPersistentTree.Write( const Buffer; Count: Longint ): Longint;
begin
  if FOwnStream then
    Result := FStream.Write( Buffer, Count )
  else
  begin
    Synchronize;
    if Position + Count > Size then
      RecreateStream( Position );
    Result := FStream.Write( Buffer, Count );
    FLastPosition := FStream.Position;          
  end;

end;

function TPersistentTree.Read( var Buffer; Count: Longint): Longint;
begin
  if FOwnStream then
    Result := FStream.Read( Buffer, Count )
  else
  begin
    Synchronize;
    if Count < 0 then
      Count := 0
    else if Count > Size - Position then
      Count := Size - Position;
    Result := FStream.Read( Buffer, Count );
    FLastPosition := FStream.Position;
  end
end;

function TPersistentTree.Seek(const Offset: Int64;
  Origin: TSeekOrigin): Int64;
begin
  if FOwnStream then
    Result := FStream.Seek( Offset, Origin )
  else
  begin
    Synchronize;
    case Origin of
      soBeginning: Result := FDataBegin + Offset;
      soCurrent: Result := FStream.Position + Offset;
      soEnd: Result := FDataBegin + Size - Offset;
    else
      Result := 0;
    end;
    if Result >