返回
基础
分类

二叉查找树节点,综上所述我们得到AST节点的代码

日期: 2019-11-14 15:57 浏览次数 : 125

1.AST的每个节点由2个域组成,这2个域分别表示当前节点的类型和附加信息。
2.AST的每个节点包含一个指向其子节点的顺序表。
3.AST的每个节点包含指向下一个节点的指针。
综上所述我们得到AST节点的代码:  1     class CSyntaxTreeNode
 2     {
 3     public:
 4         CSyntaxTreeNode(int _type,int _value) : type(_type),value(_value){}
 5
 6         inline List<NAutoPtr<CSyntaxTreeNode>>& Child()
 7         {
 8             return child;
 9         }
10
11         inline NAutoPtr<CSyntaxTreeNode> Next()
12         {
13             return next;
14         }
15
16         inline int& Type()
17         {
18             return type;
19         }
20
21         inline int& Value()
22         {
23             return value;
24         }
25     protected:
26         int type;
27         int value;
28         List<NAutoPtr<CSyntaxTreeNode>> child;
29         NAutoPtr<CSyntaxTreeNode> next;
30     };然后我们给出了部分枚举来标识节点的类型:
 1         // for type
 2         enum TYPE
 3         {
 4             stNull,
 5             stDeclare,
 6             stFunction,
 7             stParamterList,
 8             stIf,
 9             stDo,
10             stExp,
11         };最后是一棵AST的整体结构:
 1 class CParserAnalyze
 2 {
 3 public:
 4     inline void Push(NAutoPtr<CSyntaxTreeNode>& Node)
 5     {
 6         SyntaxTreeStack.Push(Node);
 7     }
 8
 9     inline NAutoPtr<CSyntaxTreeNode> Pop()
10     {
11         return SyntaxTreeStack.Pop();
12     }
13
14     inline NAutoPtr<CSyntaxTreeNode> Top()
15     {
16         return SyntaxTreeStack.Top();
17     }
18
19     inline NAutoPtr<CSyntaxTreeNode> Root()
20     {
21         return SyntaxTreeRoot;
22     }
23 protected:
24     NAutoPtr<CSyntaxTreeNode> SyntaxTreeRoot;            // 语法树根节点
25     Stack<NAutoPtr<CSyntaxTreeNode>> SyntaxTreeStack;    // 语法树栈
26 };
这里我们简单的分析一下分析过程:
以if语句为例,其组合子代码为:
1     if_desc = (str_if + exp_desc)[if_desc_first] +
2             (str_then + stmt_list)[if_desc_second] +
3             Parser_Combinator_Node::opt((str_else + stmt_必赢手机登录网址 ,list)[if_desc_third]) +
4             (str_end + str_if)[if_desc_fourth];我们输入代码:
1     if a then
2         declare b as integer
3     end if在做语法分析:
1.读入if a,a被归约为一条exp生成一个类型为exp的节点并压入AST的语法树栈。
2.if a被归约生成一个类型为stIf的节点并弹出栈顶的exp节点填充到新生成的stIf节点的第一个子节点。
3.读入then declare b as integer,integer被归约生成一个生类型为stDeclare的节点并压入语法树栈。
4.declare b as integer被归约为栈顶的stDeclare节点填充一个b标识符的子节点。
5.then declare b as integer被归约,首先弹出栈顶的stmt_list因为这里是stDeclare说明stmt_list有内容应此将栈顶的stIf的值域的最低位置为1。
6.else子句不存在。
7.整体被归约。
此时栈顶为stIf节点,其不包含next节点,有两个子节点分别为stExp和stDeclare。

  写这个编译器的目的,是为了完成编译原理课上老师布置的大作业,实际上该大作业并不是真的实现一个编译器,而我选择硬刚,是为了完成我的小愿望--手写内核,编译器和CPU。我花了整个上半学期,写完了WeiOS,为了让它支持更多的用户态程序,甚至是基本的程序开发,必须给它量身打造一个编译器。于是这个编译器被提上日程。

二叉查找树

分析过程如下图:
1.必赢手机登录网址 1
2.必赢手机登录网址 2
3.必赢手机登录网址 3
4.必赢手机登录网址 4
5.必赢手机登录网址 5
6.必赢手机登录网址 6

  因为我要复习考研和专业课过多,我打消了手写词法分析和语法分析的念头,转而使用FLEX和YACC,等到有时间再完成手工的版本--我认为也不是很难,如果用递归下降的话。

// 二叉查找树节点 Binary search tree node

2.AST的每个节点包含一个指向其子节点的顺序表。 3.AST的每个节...

  全部代码都在该处

    public class BinarySearchTreeNode

词法分析

    { public int key;// 二叉查找树节点的值

  因为是精简的C语言,所以只支持基本的符号,像”++”, “--”和位操作都不予考虑。另外,只支持int和void类型。于是便构成了以下符号集:

       public BinarySearchTreeNode left;// 二叉查找树节点的左子节点

  number [1-9][0-9]*

       public BinarySearchTreeNode right;// 二叉查找树节点的右子节点

  letter [a-zA-Z]

       /// 二叉查找树节点构造函数

  Identifier {letter}({letter}|{number})*

       public BinarySearchTreeNode(int nodeValue)

  Newline n

       {   key = nodeValue;//nodeValue 节点的值

  whitespace [ tr]+

           left = null; right = null;

保留字:

       }

  If else while int void return

       /// 插入节点

运算和界限符号:

       public void InsertNode(BinarySearchTreeNode node)

  <= >= != == + - * / < > ; , { } [ ]

       {   if(node.key > this.key)

主体函数是getToken(),这个函数封装了FLEX原生的yylex函数。而yyparser也将直接调用该函数。它的主要工作是在开始第一次词的检索前,初始化相关变量。然后在每次被调用的时候,返回符号的类型给yyparser,并且把构成符号的字符串临时保存在tokenString字符数组中。所以这函数相当于什么事情都没有干。

           {  if(this.right == null)

另外注意的是注释的两个符号,我直接在词法分析处理注释了。行注释是”//”,利用FLEX自带的input()函数(如果有的话,没有就写一个)一直读到’n’出现。然后就是段注释符”/*”和”*/”,相似的做法。

              {   this.right = node;//node插入的节点

语法分析

                  return;

  以下是BNF格式的语法规则:

              }

  Program-> declaration_list

              else

  declaration_list-> declaration_listdeclaration | declaration

                  this.right.InsertNode(node);

  declaration-> var_declaration | func_declaration

           }

  type_specifier-> INT| VOID

           else

  var_declaration-> type_specifier VARIABLE ;| type_specifier VARIABLE [ NUM ] ;

           {   if(this.left == null)

  func_declaration-> type_specifier VARIABLE compound_stmt

              {   this.left = node; return; }

  Params-> params_list| VOID

              else

  params_list-> params_list , param| param

                  this.left.InsertNode(node);

  Param-> type_specifier VARIABLE| type_specifier VARIABLE [ ]

           }

  compound_stmt-> { local_declarations stmt_list }

       }

  local_declarations->local_declarations var_declaration| /* empty */

       /// 二叉查找树查询

  stmt_list->stmt_list stmt| stmt

       public bool SearchKey(int searchValue)

  Stmt-> expr_stmt | if_stmt| return_stmt | compound_stmt | iteration_stmt

       { if(this.key == searchValue)//searchValue需要查询的值

  expr_stmt-> expr ; | ;

              return true;// 是否找到查询的值

  if_stmt ->IF stmt| IF stmt ELSE stmt

           if(searchValue > this.key)

  iteration_stmt->WHILE stmt

           {   if(this.right == null) return false;

  return_stmt->RET ; | RET expr ;

              else

  Expr-> var = expr | simple_expr

                  return this.right.SearchKey(searchValue);

  Var-> VARIABLE| VARIABLE [ NUM ]

           }

  Call-> VARIABLE

           else

  Args-> arg_list |/* empty */

           {   if(this.left == null)   return false;

  arg_list-> arg_list , expr| expr

              else

  simple_expr -> NUM | var| call | | - simple_expr

                  return this.left.SearchKey(searchValue);

        | simple_expr + simple_expr

           }

        | simple_expr - simple_expr

       }

        | simple_expr * simple_expr

       // 中序遍历

        | simple_expr / simple_expr

       public void MiddleDisplay()

        | simple_expr < simple_expr

       { if(this.left != null)

        | simple_expr > simple_expr

              this.left.MiddleDisplay();

        | simple_expr >=simple_expr

           Console.WriteLine(this.key);

        | simple_expr <=simple_expr

           if(this.right != null)

        | simple_expr !=simple_expr

              this.right.MiddleDisplay();

        | simple_expr ==simple_expr

       }

  我用globl.h中的TreeNode结构来保存语法树中的每一个节点。而一些为空的转换,我打算还是用一个该结构来表示,但是类型标记为None.

       // 前序遍历

  我实现的C-还算是个比较完整的程序语言,所以很有必要生成AST,那么语法树中共有几种类型的节点呢?按理说应每种语法规则对应一种类型,例如参数列表,声明语句,普通语句和表达式等都对应一个节点类型,详细可以参见NodeType枚举类型。Parser.c文件是处理与语法树相关的函数,目前来说当中几个函数还没写清楚,TreeNode需要大改一下我估计,过几天也许就明了了。--2018/05/29

       public void FrontDisplay()

  2018/05/30

       { Console.WriteLine(this.key);

  没想到只过了一天不到,就完成了语法分析部分,总体上来说还是很简单的。

           if(this.left != null)

  有些语法规则导出两种相似的子规则,用专业术语来讲就是就是要做左因子消除,但好像yacc已经代替我们做了这个工作--我猜测它在底下优化了我们混乱的语法规则,包括左递归也解决了。据来说就是if_stmt导出的两种情况,我并不打算在StmtType枚举中添加新的枚举类型来处理,而是利用原有的结构,用nkids来辨别是哪种情况。而在处理var_declaration第二种导出的规则时,原有的结构不够用了,因为我要存储VARIABLE和NUM,很显然一个attr联合体不够用,所以我引入了第二个联合体分别来存储两个值。分别叫attrAattrB。有些时候这样做也无法解决结构上的问题,才不得不用两个枚举类型来解决。现在我也不确定这样做是否多余,毕竟我也是第一次写编译器,但它确实解决了当下的问题。

              this.left.FrontDisplay();

  我删除了封装yylex()getToken()函数,并解决了注释代码的问题,现在可以支持/**/的段注释和//行注释了。另外,我不想让我代码变得冗余,所以我把构建符号表(Symbol table)的任务放在了语义分析,直接放在语法分析中虽然节约了时间,但实在是难以维护。

           if(this.right != null)

  最后根目录下source*.c都成功地进行了语法分析,可能也只是表面上...

              this.right.FrontDisplay();

  语义分析还没学,翻书去了...

       }

  2018/06/02

       // 后序遍历

  经过两天的学习,我知道了符号表基本的构建方式和运行时环境的搭建。但是还来不及完全转换成代码。今天我抽了一点时间写了符号表的管理函数。我的编译器有多级符号表:一个全局符号表以及每个函数一个局部符号表。在全局符号表中,每个属于函数的变量名,都有一个指针指向其局部符号表。而局部符号表通过Parent字段与父符号表相连,在当前符号表无法检索到符号信息的时候,就会去搜寻父符号表,层层递增。由于C语言本身的规定,和我的懒惰,我不支持动态作用域,也就是说对一切外部的符号引用而言,其偏移和效果都是固定的;也不支持函数声明嵌套,也就是说对于任何局部符号表,其父符号表都指向全局符号表。因此我觉得这样简单的实现方式是可行的。

       public void BehindDisplay()

  符号表的基本数据结构是哈希表。具体实现不做阐述,我只写了插入和寻找的函数,因为这个烂编译器暂时不支持类型声明和类型别名,所以我没有写删除。

       {   if(this.left != null)

  这里留下一个问题,除了全局声明函数,代码块--也就是被{}包围起来的部分,也需要局部符号表,而且是支持嵌套的。那么我该如何解决这种相当于“匿名”函数的符号表问题,我还没有思路。或许可以给它们各自赋予决不会引起冲突的名字?又或者是留到代码生成阶段再处理,这样就不必缓存“匿名”符号表了,直接生成代码就完事了。

              this.left.BehindDisplay();

  主要代码都在symbol.csymbol.h里面。

           if(this.right != null)

  2018/06/07

              this.right.BehindDisplay();

  经过几天的咸鱼和跟进,我完成了类型检查和符号表生成,中间代码生成。

           Console.WriteLine(this.key);

  关于类型检查,是完全仿造gcc的,检查顺序是后序遍历,例如表达式:

       }

    a = test() + b;

    }

  我们必须先检查test()是否有返回值,然后b是什么类型的数据,如果test()返回值是void,那么这个语句就可以直接判断为错误了。若两个加数通过检查,而a是数组类型的话,也会报错。

    /// 二叉查找树

  由上所述,类型检查必须是后序遍历,而我生成符号表的时候采取先序遍历,这里就产生了矛盾。解决的方法是,我对语法树中的表达式类型的节点,通通执行后续遍历,而其他如If语句,while语句等采取常规做法。原因是我在表达式的语句中,不可能出现声明新函数或者变量的语句,反而是要检查所用的变量和函数在之前是否声明,如果没有就报错,因此后序遍历是可行的。

    public class BinarySearchTree

  也就是说我的buildSymtab()函数不是安装树状递归展开的,而且名不副实,因为它除开生成符号表,还同时完成了类型检查工作。其实我是想把这两个步骤分开的,用2-pass来完成,代码也比较精简,想砍掉哪部分也很方便。但由于当时写的太爽了,不想再写类似于buildSymtab()这样结构的函数了,所以直接做完了。

    {   private BinarySearchTreeNode root;

  上一篇遗留的问题,匿名代码块怎么办?我的处理方法是为它们生成单独的符号表,并且在语法分析阶段,调用randomFuncName()函数为每一个匿名代码块生成一个名字,类似真正的函数那样管理,这个名字不是真正随机的,因为它是AAAnonymous*的形式,但无所谓了,反正这编译器也烂。

       /// 生成一个二叉查找树

  具体的代码在analyzer.c里,相关结构的定义在analyzer.h中。

        public BinarySearchTree()

  接下来是一张类型检查的贴图: 左边是我的fcc,右边是gcc,错误和警告都检测出来了,但是他们比我提示信息更加多...

       {   root = nul; }

  必赢手机登录网址 7

       /// 生成一个二叉查找树

  运行时环境:

       /// <param name="nodeValue">二叉查找树根节点的值</param>

  当然是选择和C语言一样啊,没有什么好说的。

       public BinarySearchTree(int nodeValue)

  要提的一点还是匿名代码块的问题,对于这种代码块中声明和定义的“局部变量”,我观察了gcc的做法,他们把这些“局部变量”当作了其所属的函数的局部变量,举个例子:

       { root = new BinarySearchTreeNode(nodeValue); }

  void test()

       /// 在二叉查找树上插入一个节点

  {

       /// <param name="nodeValue">插入节点的值</param>

    int j;

       public void InsertBinarySearchTreeNode(int nodeValue)

    {

       {   BinarySearchTreeNode insertNode = new BinarySearchTreeNode(nodeValue);

      int i;

                     if(root == null)

    }

           { root = insertNode;

  }

              return;

  那么在函数test()为局部变量分配空间的时候,不是分配4个字节,而是8个字节。所以我也这么干。因为语法的原因,函数体本身声明局部变量肯定在匿名代码块之前,故当我们处理到匿名代码块的时候,必须要返回去更改所属函数的局部变量信息(用于代码生辰的时候分配具体空间)。之前我的FuncProperty结构并没有维护参数个数和局部变量大小的信息,所以我做了一些更改,添加了nparamsnlocalv域。

           }

  中间代码

           else

  本来我都不打算写中间代码,直接生成x86的汇编代码,但老师说不给我分,我就写了。然后我看了一下vsl的中间代码,我很郁闷遂决定自己创造一套新的三地址码,我觉得还挺有意思的,我甚至都考虑用这套三地址码写一个虚拟机,直接在虚拟机上面跑。。。

              root.InsertNode(insertNode);

  折中了一下,我的这套三地址码已经非常像x86的汇编代码了,除了一些没用的临时寄存器。其对于我来说,最大的作用就是把树形的信息,转换成了链状的,接下来顺着三地址码构成的链表翻译就好了。相关代码见irgen.c而数据结构等在irgen.h.下面是一个源代码文件(source2.c)以及其生成的三地址码(midcode.f)的部分。

           return;

source2.c:

       }

int jb;int x[10];/*void test{}*/int minloc(int a[], int low, int high){    int i; int x; int k;            k = low;    x = a[low];    i = low + i;/*    k = a;    ok = 10;    i = a[test()];*/    while (i < high) {        if (a[i] < x) {            x = a[i];            k = i;        }        i = i + 1;    }    return k;}   void sort(int a[], int low, int high){    int i;    int k;

       /// 在二叉查找树上查询一个数

midcode.f:

       /// <param name="searchValue">需要查询的值</param>

 1 program: 2     glob_var jb 4 3     glob_var x 40 4  5 _minloc: 6     loc_var 16 7     k = low  8     mull t0 low 4  9     addl t1 &a t0 10     x = t1 11     addl t2 low i 12     i = t2 13 L0:14     lt t3 i high 15     if_false t3 goto L116     mull t4 i 4 17     addl t5 &a t4 18     lt t6 t5 x 19     if_false t6 goto L220     mull t7 i 4 21     addl t8 &a t7 22     x = t8 23     k = i 24 L2:25     addl t9 i 1 26     i = t9 27     goto L028 L1:29     ret k 30 31 _sort:32     loc_var 1633     i = low 34 L3:35     subl t10 high 1 36     lt t11 i t10 37     if_false t11 goto L438     loc_var 1639     begin_args

       /// <returns>是否找到查询的值</returns>

  可以看到真的是一一对应的,虽然还有个小Bug,但是我懒得管了。

       public bool SearchKey(int searchValue)

  2018/06/11

       { if(root.key == searchValue)   return true;

  我的寄存器分配函数写得有点混乱,当然如果我不想做那些奇奇怪怪的优化,就不会存在这个问题。我写得很难受,但也比较享受。我现在是考虑把对中间变量的处理也统一起来,但是还没有思路...

           else

  isReside():判断一个地址是否驻留在寄存器中,如果该地址类型为TempPtr或TempReg,

              return root.SearchKey(searchValue);

  regWriteBack(RegPtr Rp, RegPtr Rbp,FILE *fp): 把Rp寄存器的内容写会所属变量的内存地址。一定要先判断Hp是否为空,若为空就表示当前存了一个中间变量!!!! 如果不为空,但是没被修改过--就是dirty为0,也没必要写回去!!!

       }

  regReadIn(RegPtr Address *addr, FILE *fp): 把地址addr所属的变量的值读到到Rp指向的寄存器中,并更新相关内容.如果该变量/中间变量已存在寄存器中,则调用regMoveReg()直接从原寄存器移动.如果不在,则根据addr的类型采取不同的操作.我暂时处理了一般变量和常数的读取。

       /// 二叉查找树中序遍历

  regBindVar(RegPtr Rp, Address *addr, HashList Hp, int dirty):如函数名,把addr,Hp,dirty赋给寄存器Rp.函数体内检测是否有其他寄存器已保存了该变量,调用FreeReg()把其addr和Hp域清空.

       public void MiddleDisplay()

  RegPtr regSearchOne(HashList Hp, FILE *fp):为第一个操作数搜寻合适的寄存器.我判断的是addr这个域,但感觉好像不够圆满...

       { root.MiddeleDisplay(); return; }

  

       /// 二叉查找树前序遍历

  2018/06/14

       public void FrontDisplay()

  懒得写了,终于完成了代码生成,我自己写的那套寄存器分配,也很好用,甚至超过了vsl作者们写的算法=

  但是遗留了一个问题,就是我在代码生成的时候,忘记考虑到代码重入性的问题了,在生成循环代码块的时候,根据前文的数据流生成了代码,本意是尽量减少内存存取的次数,但是我没有考虑到,在真正运行的过程中,每次循环开始的时候,寄存器中存储的信息不一定是“第一次"进入循环块时的信息,因此我生成的代码有语义错误,只有偶尔情况下才是正确的。我不打算改这个bug了,老师说这个涉及到龙书上讲解的数据流分析,但我还要考研,所以推迟了吧,等真正需要的时候再搞这个。

  下面是测试代码,就是一个简单的选择排序 source2.c

/* A program to perform selection sort on a 10   element array. *//*void test{}*/int minloc(int a[], int low, int high){    int i; int x; int k;            k = low;    x = a[low];    i = low + i;    while (i < high) {        if (a[i] < x) {            x = a[i];            k = i;        }        i = i + 1;    }    return k;}   void sort(int a[], int low, int high){    int i;    int k;    i = low;    while (i < high - 1) {        int t;        k = minloc(a, i, high);        t = a[k];        a[k] = a[i];        a[i] = t;        i = i + 1;    }}

  我生成的汇编代码 source2.s:

  

.file"testfile/source2.c".text.globlminloc.typeminloc, @functionminloc:pushl %ebpmovl %esp, %ebpsubl $16, %espmovl 12, %eaxmovl %eax, -12movl 12, %edxleal 0, %ebxmovl 8, %ecxaddl %ecx, %ebxmovl , %ebxmovl %ebx, -8movl -4, %eaxaddl %eax, %edxmovl %edx, -4.L0:cmpl 16, %edxjge .L1leal 0, %eaxaddl %ecx, %eaxmovl , %eaxcmpl -8, %eaxjge .L2leal 0, %ebxaddl %ecx, %ebxmovl , %ebxmovl %ebx, -8movl %edx, -12.L2:movl -4, %edxaddl $1, %edxmovl %edx, -4jmp .L0.L1:movl -12, %eaxleaveret.globlsort.typesort, @functionsort:pushl %ebpmovl %esp, %ebpsubl $16, %espmovl 12, %eaxmovl %eax, -4.L3:movl 16, %edxsubl $1, %edxcmpl %edx, %eaxjge .L4movl 16, %ebxpushl %ebxpushl %eaxmovl 8, %ecxpushl %ecxcall minlocaddl $12, %espmovl %eax, -8leal 0, %edxaddl %ecx, %edxmovl , %edxmovl %edx, -12movl -4, %eaxleal 0, %edxaddl %ecx, %edxmovl -8, %eaxleal 0, %ebxaddl %ecx, %ebxmovl , %edxmovl %edx, movl -4, %eaxleal 0, %ecxmovl 8, %eaxaddl %eax, %ecxmovl -12, %eaxmovl %eax, movl -4, %eaxaddl $1, %eaxmovl %eax, -4jmp .L3.L4:leaveret

  

最后上测试结果,难得的正确了一次:

必赢手机登录网址 8

  2018/06/24

  本来不打算写了,但是在满分的激励下我做了以下修改,并最终解决了上面的Bug

    1.被调用函数保存可能改变的所有寄存器。

    2.实现循环代码的语义正确(其实就是保证了可重入性)。

  当然还有一个问题就是,栈内容初始化。因为物理页面分配的不确定性,因此会留下上一个进程的数据,所以必须在程序一开始对可能用到的栈空间进行初始化。严格来说,这并不是我的问题。

  最后附上一张成功运行的图:

  必赢手机登录网址 9

       { root.FrontDisplay(); return; }

       /// 二叉查找树后序遍历

       public void BehindDisplay()

       {   root.BehindDisplay(); return; }

       /// 二叉查找树排序

       /// <param name="a">需要排序的数组</param>

       public static void BinarySearchTreeSort(int [] a)

       { BinarySearchTree t = new BinarySearchTree();

           for(int i = 0; i < a.Length; i ++)

              t.InsertBinarySearchTreeNode(a[i]);

           t.MiddleDisplay();return;

       }/// 二叉查找树查找

       /// <param name="a">进行查找的数组</param>

       /// <param name="searchKey">需要查找的树</param>

       public static bool BinarySearchTreeSearch(int [] a, int searchKey)

       {   BinarySearchTree t = new BinarySearchTree();

           for(int i = 0; i < a.Length; i ++)

              t.InsertBinarySearchTreeNode(a[i]);

           return t.SearchKey(searchKey);

       }

    }

namespace 二叉树

{   class Node

    {   int n;

        public Node(int x)

        {   n=x; }

        public Node Left;

        public Node Right;

        public void Insert(Node node)

        {   if(node.n > this.n)

            {   if(this.Right == null)

                    this.Right = node;

                else

                    this.Right.Insert(node);   }

            else

            {   if(this.Left == null)

                { this.Left = node; }

                else

                { this.Left.Insert(node); }  }   }    //递归

        public void Show()

        {   Console.WriteLine(n); } }

    class BinaryTree

    {   Node root; 

        public void GenerateTree(Node node) //高内聚,低耦合

        {   if(root == null)

            {   root = node; return; }//如果树是空,第一次加节点

            root.Insert(node); 

    }

        public void ShowInOrder(Node node) //中序遍历(in order):左中右。先(前)序遍历(pre order):中左右。后序遍历(post order):左右中。

        {  if(node == null) return;//递归必须有个终止条件,递归方法中一定要接受参数

            ShowInOrder(node.Left);

            node.Show();

            ShowInOrder(node.Right);

        }

        public void Show()

        {   ShowInOrder(root); }

 }

    class A

    {   static void Main()

        {   BinaryTree b = new BinaryTree();

            Node node = new Node(5);

            b.GenerateTree(node);

            node = new Node(13);

            b.GenerateTree(node);

            node = new Node(6);

            b.GenerateTree(node);

            node = new Node(26);

            b.GenerateTree(node);

            node = new Node(7);

            b.GenerateTree(node);

            b.Show();   }   }   }    结果:5,6,7,13,26

单链表

    class Node

    { int a;

       public Node(int a) 

       {   this.a=a; }

       public int A      

       {get{return a;}  set{a=value;} }

       public Node next;

    }

    class LinkedList

    { Node header;

       public void Generate(int x)

       {   if(header==null)

              header=new Node(x);

           else

           {   Node n = new Node(x);

              if(n.A < header.A)

              {   n.next = header;

                  header=n;

                  return;

              }

              Node tmp=header;

              Node t=header;

              while(tmp.A < n.A)

              {   t=tmp; //为了下一次循环

                  tmp=tmp.next;

                  if(tmp==null)

                     break;

              }

              t.next=n;

              n.next=tmp;

           }

       }

       public void Out()

       {   Node tmp=header;

           while(tmp!=null)

           {   Console.WriteLine(tmp.A);

              tmp = tmp.next;

           } } }

    class Test

    {   static void Main()

       {   LinkedList ll = new LinkedList();

           ll.Generate(6);

           ll.Generate(36);

           ll.Generate(26);

           ll.Generate(16);

           ll.Out();

       }   }   }

反向链表

    class Link            //this class reverse the LinkedList

    { public int a;

       public Link next;

    }

    class createLink     //the class create the LinkedList

    {

       Link header=null;

       Link p = null;

       Link temp = null;

       Link l=null;       //Link k=null;

       Link g=null;

       public void create()

       { string str;

           int i;

           Console.WriteLine("Please enter number:");

           str=Console.ReadLine();

           while(str!="y")

           { i=Convert.ToInt32(str);

              temp=new Link();

              temp.a=i;

              temp.next=null;

                if(g==null)

                  g=temp;

              if(header==null)

                  header=temp;

              if(p==null)

                  p=temp;

              else

              { p.next=temp;

                  p=p.next;

              }

              Console.WriteLine("please enter number:");

              str=Console.ReadLine();

           }

       }

       public void display()

       {   while(header!=null)

           {   Console.WriteLine(header.a);

              header=header.next;

           }

       }

       public void reversed() // the mothod reversed the LinkedList

       { Link k=null;

           Link tmp=null;

           Link com =null;

           if(tmp==null)

              tmp=header.next;

           while(tmp!=null)

           {  //            if(com==null)

//             com=header;

              l=tmp;

              if(k==null)

              {   header.next=null;

                  k=header;

              }

              com=header;

              header=l;

              tmp=l.next;

              l.next=com;

           }

       }

       public void show()

       {   while(l!=null)

           {   Console.WriteLine(l.a);

              l=l.next;

           } } }

    class Tester

    {   static void Main()

       {  createLink cl=new createLink();

           cl.create();

           //cl.display();

           cl.reversed();

           cl.show();

       } } }

Stack 栈

    class Node

    { int a;

       public Node(int a)

       {   this.a=a; }

       public int A

       { get{return a;} set{a=value;} }

       public Node next;

    }

    class LinkedList

    { protected Node header;

       public void Generate(int x)

       {   if(header==null)

              header=new Node(x);

           else

           {   Node n = new Node(x);

              n.next=header;

              header=n;

           }

       }

       public void Out()

       {   Node tmp=header;

           while(tmp!=null)

           {   Console.WriteLine(tmp.A);

              tmp = tmp.next;

           } } }

    class Stack : LinkedList

    {   public void Push(int x)

       {   this.Generate(x); }

       public int Pop()

       { if(this.header == null)

              return -1; // empty stack

           int n = header.A;

           header = header.next;

           return n;

       }

    }

    class Test

    {   static void Main()

       {   Stack ss = new Stack();

           ss.Push(7);

           ss.Push(78);

           ss.Push(9);

           ss.Push(2);

           int i = ss.Pop();

           while(i != -1)

           {   Console.WriteLine(i);

              i = ss.Pop();

           } } } }