二叉链表结点结构定义 ：

typedef struct Node

     { DataType data;

        strct Node * LChild;

        struct Node * RChild;

     }BiTNode, *BiTree;

1、 先序遍历

void  PreOrder(BiTree root)

        { if (root!=NULL)

{Visit(root->data);                      PreOrder(root ->LChild);    

 PreOrder(root ->RChild);

      }

 }

2、中序遍历

void  InOrder(BiTree root) 

         {if (root!=NULL)

   { InOrder(root ->LChild);    

  Visit(root->data);                      InOrder(root ->RChild);             }

   }

3、 后序遍历

void  PostOrder(BiTree root) 

    {if(root!=NULL)

   { PostOrder(root ->LChild);

      PostOrder(root ->RChild);

      Visit(root ->data);                   

        }

二、 输出二叉树中的叶子结点

void  PreOrder(BiTree root)

   /{  if (root!=NULL)

     {if (root ->LChild==NULL && root ->RChild==NULL)

              printf(root->data);                 

         PreOrder(root->LChild);                  PreOrder(root->RChild);                   }

     }

三、 统计叶子结点数目

void leaf(BiTree root)

{  if(root!=NULL)

      {leaf(root->LChild);

    leaf(root->RChild);

         if (root ->LChild==NULL && root ->RChild==NULL)

            LeafCount++;

   }

}

用“扩展先序遍历序列”创建二叉链表的算法

void CreateBiTree(BiTree *bt)

{ char ch;

  ch=getchar();

  if(ch==' ^ ') *bt=NULL;

  else

     {*bt=(BiTree)malloc(sizeof(BiTNode));

        (*bt)->data=ch;

        CreateBiTree(&((*bt)->LChild)); 

        CreateBiTree(&((*bt)->RChild));

      }

 }

后序遍历求二叉树的高度递归算法

int PostTreeDepth(BiTree bt)

{  int hl,hr,max;

 if(bt!=NULL)

  {

hl=PostTreeDepth(bt->LChild);       hr=PostTreeDepth(bt->RChild);        max=hl>hr?hl:hr;              

  return(max+1);              

   }

  else return(0);                    }

中序线索化算法

void  Inthread(BiTree root)

 {  if (root!=NULL)

  {Inthread(root->LChild);                

    if (root->LChild==NULL)

       {root->Ltag=1; root->LChile=pre;} / *置前驱线索 */}

    if (pre!=NULL&& pre->RChild==NULL)  

        {pre->rtag=1 ;pre-> RChild=root; }

    pre=root；

    Inthread(root->RChild);                   

     }

   }

遍历线索树可分为两步：

1、求出被访问的第1个结点(以中序为例)

BiTNode * Infirst(BiTNode * bt)

{  BiTNode *p=bt;

    if(p=null)  return(null);

    while (p->ltag==0)     p= p->Lchild;

    return(p);   }

2、连续访问后继结点

void yinorder(BiTNode bt)

{  BiTNode *p;

    p= Infirst(bt);

    while (p!=null)   {visit(p);p=innext(p);}  

 }

1、插入结点运算

void InsNode(BiTNode * p ,  BiTNode * r)

   {if(p->Rtag==1)   

       {   r->RChild=p->RChild;          r->Rtag=1;

         p->RChild=r;    r->LChild=p;     r->Ltag=1;   }

       else 

       {   s=p->RChild;

         while(s->Ltag==0)         s=s->LChild;

          s->LChild=r;

         r->RChild=p->RChild;       r->Rtag=0;

         r->LChild=p;            r->Ltag=1;

         p->RChild=r; }

}