(2011.08.06)分岐接点と葉接点の異なる表現を実現する3つの異なる方法

3つの異なる方法で分岐接点と葉接点の異なる表現を実現する
リーフノードとブランチノードを区別する方法の1つは,C++の結合構造を用いることであるが,リーフノードタイプとブランチノードタイプの長さの差が大きすぎると,結合構造が代効する.
第2の第3の方法は、継承方法を使用して、このようにリーフノードとブランチノードをよりよく区別することができ、ベースクラスは、ブランチノードに属するかリーフノードに属するかを区別するために虚継承isLeaf関数を定義し、第2の方法と第3の方法の違いは、traverse関数が実現する位置が異なり、すべてのノードを周遊するのが便利であることである.もう一つは独立して分岐して周遊することができます.

//                       

/**********************************************************************
　　                  C++     ，  ，     
                  ，           。
　　       ，        ，                
 ，          isLeaf                   ，
              ，  traverse         ，    
           ，            。
**********************************************************************/


///////////////////////////////////////////////////////////////////////

// 1.                      

enum Nodetype{ leaf, internal};		// Enumerate node types

class VarBinNode					// Generic node class
{
public:
	Nodetype mytype;				// Stores the type for this node
	union
	{
		struct						// Structure for internal node
		{
			VarBinNode* left;		// left child
			VarBinNode* right;		// right child
			operator opx;			// Internal node value
		}intl;
		Operand var;				// Leaves just store a value
	};
	VarBinNode (const Operand& val)	// Constructor: leaf
		{my type = leaf; var = val;}
	VarBinNode(const Operator& op, VarBinNode* l, VarBinNode* r)
	{								// Constructor: Internal
		mytype = internal;
		intl.opx = op;
		intl.left = l;
		intl.right = r;
	}

	bool isLeaf()				{return mytype == leaf;}
	VarBinNode* leftchild()		{return intl.left;}
	VarBinNode* rightchild()	{return intl.right;}
	void traverse(VarBinNode* subroot)
	{								// Preorder traversal
		if (subroot == NULL)	return;
		if (subroot -> isLeaf())
			{cout << "Leaf: " << subroot -> var << "
";}
		else
			{
			cout << "Internal: " << subroot -> intl.opx << "
";
			traverse(subroot -> leftchild());
			traverse(subroot -> rightchild());
			}
	}
};


///////////////////////////////////////////////////////////////////////

// 2.   C++                         
//   ，             。

class VarBinNode					// Node abstract base class
{
public:
	virtual bool isLeaf() = 0;
};

class LeafNode: public VarBinNode	// Leaf node
{
private:
	operand var;					// Operand value
public:
	// Constructor
	LeafNode(const Operand& val)		{var = val;}
	// Version for LeafNode
	bool isLeaf()						{return true;}
	// Return node value
	Operand value()						{return var;}
};

class IntlNode: public VarBinNode	// Internal node
{
private:
	VarBinNode* left;				// left child
	VarBinNode* right;				// right child
	operator opx;					// Operator value
public:
	// Constructor
	IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r)
	{
		opx = op;
		left = l;
		right = r;
	}
	// Version for IntlNode
	bool isLeaf()						{return false;}
	// left child
	VarBinNode* leftchild()				{return left;}
	// Right child
	VarBinNode* rightchild()			{return right;}
	// Value
	Operator value()					{return opx;}
};

// Preorder traversal	//   ，             。
void traverse(VarBinNode *subroot)
{
	if ( NULL == subroot) return;		// nothing to visit
	if (subroot -> isLeaf())			// Do leaf node
	{
		cout << "Leaf: " 
			<< ((LeafNode*)subroot) -> value()) 
			<< endl;
	}
	else
	{
		cout << "Internal: "
			<< ((IntlNode *)subroot) -> value() << endl;
		traverse(((IntlNode *)subroot -> leftchild());
		traverse(((IntlNode *)subroot -> rightchild());
	}
}


///////////////////////////////////////////////////////////////////////

// 3.   C++                         
//   ，           。

class VarBinNode						// Node abstract base class
{
public:
	virtual bool isLeaf() = 0;
	virtual void trav() = 0;
};

class Leafode:	public VarBinNode		// Leaf node
{
private:
	Operand var;						// Operand Value
public:
	// Constructor
	LeafNode(const Operand& val)	{var = val;}
	// Version for leafnode
	bool isLeaf()					{return true;}
	// Return node value
	Operand value()					{return var;}
	// traverse
	void trav()	{cout << "Leaf: " << value() << endl;}
};

class IntlNode: public VarBinNode		// Internal node
{
private:
	VarBinNode* lc;						// Left child
	VarBinNode* rc;						// Right child
	Operator opx;						// Operator Value
public:
	// constructor
	IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r)
		{opx = op; lc = l; rc = r;}
	// Version for IntlNode
	bool isLeaf()				{return false;}
	// Left child
	VarBinNode* left()			{return lc;}
	// Right child
	VarBinNode* right()			{return rc;}
	// Value
	Operator value()			{return opx;}
	// traverse
	void trav()
	{
		cout << "Internal: " << value() << endl;
		if(left() != NULL) left() -> trav();
		if(right() != NULL) right() -> trav();
	}
};

// Preorder traversal
void traverse(VarBinNode* root)
{
	if (root != NULL) root -> trav();
}

***/