C # is indeed a good object-oriented language, I see "Data Structure (Second Edition)" The book should be a version described with C #. Here is a tree I wrote with C #. First use the interface to make an abstract definition, so that only the interface is operated while implementing traversal, insertion, etc. In the program, I try to use the characteristics of C #, such as interface, attribute, and rising, although it looks more often, when the code is getting more and more, you will see the advantages, because reasonable structure Let you think clearly. I can only count a beginning, because if you want to write all the types of trees and the algorithms above them, I see that there is no 1 ~ 2k line program is absolutely not, but as long as there is time. I will definitely write, and I hope everyone will write, and improve this code base. Using system; using system.collections; ///// / ////x@263.net) /// Namespace Tree {/// /// Left left subtree, Right Right Tree /// Enum position {left, right}; /// /// LINK pointing to children, Thread pointing back /// Enum tag {link, thread}; /// /// binary node Abstract definition /// interface ibinnode {bool islef (); object element {get; set;} ibinnode left {get; set; set;} }
/// /// traversal, clues, etc. Operations /// interface itravelbintree {void preordertravel (); void inordertravel (); void revORDERTRAVEL (); void print (IbinNode T);} interface IInsertBinTree {void Insert (IBinNode node, Position pos);} /// /// Normal actualize of bintree /// class BinNodePtr: IBinNode {protected object element; protected IBinNode lchild; protected IBinNode rchild ; public BinNodePtr (object e, IBinNode left, IBinNode right) {element = e; lchild = left; rchild = right;} public BinNodePtr (object e) {element = e; lchild = rchild = null;} public BinNodePtr () { element = null; lchild = rchild = null;} public bool isLeaf () {if (lchild == null && rchild == null) return true; return false;} public object Element {get {return element;} set {element = Value;}} public}}}} set {lchild = value;}} public ibinnode right}} set {rchild = value;}}} class BinNodeLine: BinNodePtr, IBinNode {private Tag ltag, rtag; public BinNodeLine (object e, IBinNode left, IBinNode right): base (e, left, right) {ltag = rtag = Tag. Link;} public binnodeline (Object E): base (e) {ltag =} public tag ltag {get {return ltag;} set {ltag = value;}} public tag = value;}} public tag = value;}} public tag = value;}} public tag = value; ;} set {rtag = value;}}} class TravelBinTree: ITravelBinTree, IInsertBinTree {const int INIT_TREE_SIZE = 20; private IBinNode tree; private BinNodeLine head; head pointer // private IBinNode prenode threaded post;
// Point to the recently visited pre-drive node public travelbintree () {tree = new binnodePtr ();} public travelbintree (ibinnode inode;} /// /// sequence traversal Recursive algorithm implementation /// /// Non-recursive implementation public void preordertravel () {ibinnode temptree; stack stk = new stack; if (Tree == null) THROW New INVALIDOPERATIONEXCEPTION ("Access tree is empty")); Temptree = Tree; Stk.push (Tree); While (stk.count! = 0) {while (Temptree! = null) {print (TempTree); STK.PUSH (Temptree.Left); Temptree = Temptree.Left;} STK.POP (); // Empty pointer returns (STK.COUNT! = 0) {TempTree = (ibinnode) stk.pop (); STK.PUSH ( temptree.Right); temptree = temptree.Right;}}} public void InOrderTravel () {InOrderTravel (tree);} private void InOrderTravel (IBinNode t) {if (t == null) return; InOrderTravel (t.Left); Print (t); inordertravel (T.right);} public void revORDertravel () {RevorderTravel (Tree);} private void RevorderTravel (IbinNode T) {IF (t == null) return; Revordertravel (T.L.L.right); Print (T);} public void print (Ibinnode T) {Console.write (T.Element ", ");} Public void insert (Ibinnode Node, Position POS) {if (Node == Null) Throw (" No Empty Node Insert Tree ")); Switch (POS) {CASE Position.Left: Tree. LEFT = Node; Break; Case Position.right: Tree.right = Node; Break;}} /// //> Follow the sequence of the tree /// public void treebuilder () { Stack STK = New Stack (init_tree_size); STK.PUSH (Tree); Position Pos; String Para; POS =
Position.Left; IbinNode Baby, Temp; While (True) {Para = Console.readLine (); if (PARA == ") {if (POS == Position.right) {stk.pop (); while (STK .Count! = 0 && ((ibinnode) STK.PEEK ()). Right! = NULL) STK.POP (); if (stk.count == 0) Break;} else pos = position.right;} else { IF (Tree.gettype (). Equals () == true) Baby = new binnodeptr (para); temp = (ibinnode) stk.peek (); if (pOS == position.left) Temp.Left = BABY; Else Temp.right = Baby; POS = position.Left; STK.PUSH (BABY);}}} /// /// 线 线 线 /// public void inorderthreading () {hEAD = New binnodeline (""); head.rtag = tag.thread; head.right = head; if (Tree == null) Head.Left = head; else {head.left = Tree; PRENODE = HEAD;
}}}} /// ///} 线 线 线 实 实 实 实 实 (i) = "t"> private void intenting (ibinnode t) {IF T == null) Return; Else {INTHREADING (T.LEFT); // IF (left}}} /// /// summary description for class1. /// class class1 {// / /// Test Console /// /// static void main (string [] args) {string para = null; para = console .Readline (); binnodeptr root = new binnodeptr (para); TravelBintree T = new travelbintree (root); t.treebuilder (); t.preorderTravel (); console.writeline ("); t.inorderTravel (); console .Writeline (""); t.revordertravel ();}}} Very hoping with everyone (HE_X@263.net)
