Data Structure and Algorithm (C # Implementation) Series --- Tree (1)
HEAVENKILLER (original)
First we define the tree next:
The tree is a limited, non-empty node set,
T = {r} or t1 or t2 or ... or TN
It has the following properties:
1. Collection specified node R is called the root node of the tree
2. The remaining nodes can be divided into n subsets, T1, T2, ... TN (n> = 0), where each subset is a tree.
Other definitions of trees, such as leaves, and high, please check out other things, everywhere.
The main nature of the tree is traversal, divided into depth traversal and breadth traversal.
Here, it is implemented as DEPTHFIRSTTRAVESAL () and widthfirsttravesal ()
The depth traversal is divided into pre-sequence traversal, order traversal, and back sequence traversal.
This is achieved by adapter technology.
Using system;
Using system.collections;
Namespace Datastructure
{
///
/// Tree's summary description.
/// gen traverse, traversaltype can't be change, or throw a exception
/// support enumeration, comparison, depth replication
///
Public Abstract Class Tree: ienumerable, iComparable
{
Public tree ()
{
//
// TODO: Add constructor logic here
//
}
Protected Queue KeyQueue = new queue (); // Store data only when enumerating, does not participate in the comparison of Equals implementation
Protected TraversalType TraversalType = TraversalType.breadth; // Choose a Traversal Type, And Depthfirst Is Default
// protected uint deterree = 0; // degree of the tree, init it as 0
// protected uint height = 0; // HEIGHT of the Tree, Init IT AS 0
// Enumerate different traversal types
Public Enum TraversalType PUBLIC ENUMTYPE
{
Breadth = 1, // Scene Traverse
Predepth = 2, // pre-sequence traversal
Indepth = 3, // 中序 Traverse
PostDepth = 4 // Back sequence traversal
}
// public virtual abstract object key {}
Public Abstract Tree this [uint _index] {get; set;} // if i only use get, can I change it lat
Public Abstract Object Key {Get;
Public Abstract uint deterree {get;}
// public abstract uint height {get;}
Public void settraversaltype (traversaltype _type) {traversaltype = _Type;} // set a traversal a type, if it's not set manually, Depthfirst Will Be Chosen in Default
Public Abstract Bool ISempty (); // Property Takes The Place of iSempty ()
Public abstract bool isleaf ();
// Only Visit, Needn't Queuepublic Virtual Void DepthfirstTraversal (iPrePostvisitor_VIS) // Middle Depthfirst Traversal
{
// Different visits using different visits through _vis to perform pre-sequence, sequencing, and order
IF (! iSempty ())
{
_vis.previsit (this.key);
IF (this.degree> = 1)
{
IF (this.degree> = 2)
{
For (uint i = 0; i <(twis.degree-1); i ) //
{
This [i] .depthfirsttraversal (_VIS); // Recursive Call
//_vis.visit(thiskey);
}
}
THIS [this.degree-1] .depthfirsttraversal (_VIS);
}
_vis.postvisit (this.key);
}
}
Public Virtual Void BreadthfirstTraversal (Ivisitor_Vis) // Breadth First Traversal
{
Queue Tmpqueue = new queue (); // used to help breakthfirsttraversal
//thiskeyqueue=new queue (); // store keys
IF (! this.isempty ())
Tmpqueue.enqueue (this); // enqueue the root node at first
While (tmpqueue.count! = 0) // untric the number of the queue is Zero
{
Tree headtree = (Tree) tmpqueue.dequeue ();
//this.keyqueue.enqueue (HEADTREE.KEY);
_Vis.visit (Headtree.Key);
For (uint i = 0; i { Tree ChildTree = Headtree [i]; IF (! CHildTree.Isempty ()) Tmpqueue.enqueue (Childtree); } } } / / -------------------------------------------------------------------------------------------- End ------------------------------------ // Interior member class for accessers for different traversal types Public Class Preorder: iprepostvisitor { Private Ivisitor Visitor; Public preorder (ivisitor _vis) {visitor = _vis;} #Region iprepostvisitor member Public void previsit (Object _obj) { // Todo: Add preorder.previsit implementation THIS.Visitor.visit (_OBJ); } Public void visit (Object _obj) { // Todo: Add preorder.visit implementation } Public void Postvisit (Object_Obj) { // Todo: Add preorder.postvisitor implementation } #ndregion }
