CSE 326: Data Structures
Extra Slides on Nested Lists

	Henry Kautz
	Winter 2002

These Slides Contain

	Example of a polymorphic node type.
	Method for representing a tree as a list containing the root followed by pointers to each child.
	Simpler LISP-like method for representing a tree as a list contain the root followed by the children (not pointers to the children).
	The LISP-like method, but using a generic Node template and a polymorphic object type.
		See file “poly.cpp” on the course web page for a file containing code for this final version.

Polymorphic* Node

	class node {
	public: enum Tag { I, P };
	private:
	union { int i; node * p; };
	Tag tag;
	void check(Tag t){ if (tag!=t) error();}
	node * next;
	public:
	Tag get_tag() { return tag; }
	int & ival() { check(I); return i; }
	node * & pval() { check(P); return p; }

Creating and Setting Nodes

	class node {
	...
	public:
	// Creating a new node
	node(int ii) { i=ii; tag=I; }
	node(node * pp) { p=pp; tag=P; }
	// Changing the value in a node
	void set(int ii) { i=ii; tag=I; }
	void set(node * pp) { p=pp; tag=P; }
	};

Method 1: Nested List Implementation of a Tree

	next

How To Represent?

Slide 7

“LISP” Nested List Implementation of a Tree

	next

How To Represent?

Slide 10

Using Distinct Node and Polymorphic Objects

	template <class t> struct node; //forward declaration
	class poly {
	public: enum Tag { I, P };
	private:
	union { int i; node<poly> * p; };
	Tag tag;
	void check(Tag t){ if (tag!=t) error("bad");}
	public:
	Tag get_tag() { return tag; }
	int & ival() { check(I); return i; }
	node<poly> * & pval() { check(P); return p; }

Using Distinct, ... continued

	public:
	// Creating a new poly
	poly() { i=0; tag=I; }
	poly(int ii) { i=ii; tag=I; }
	poly(node<poly> * pp) { p=pp; tag=P; }
	// Changing the value in a poly
	void set(int ii) { i=ii; tag=I; }
	void set(node<poly> * pp) { p=pp; tag=P; }
	void print_preorder(void);
	};
	template <class t> struct node {
	t data;
	node<t>* next; };

Slide 13

Other Choices

	Use an explicit List class as well as a Node class or structure
	pval() then is a List, rather than a pointer to Node
	print_preorder() or other routines that traverse the tree would need some way to efficiently step through the nodes in the list.
		I.e., don’t actually destroy the list using Pop()
		You could let the List() give you it’s first node, or you could define a list iterator type as described in the textbook.