基础代码（指模板代码）

二叉树层次遍历

基于队列实现二叉树的层次遍历

  1. void LevelOrder(BiTree T)
  2. {
  3.     InitQueue(Q);
  4.     BiTNode *p;
  5.     if(!T)
  6.         EnQueue(Q,T);  // 根节点入队列
  7.     while(!IsEmpty(Q))
  8.     {
  9.         DeQueue(Q,p);
  10.         visit(p);     // 访问该节点
  11.         if(p->lchild)
  12.              EnQueue(Q,p->lchild) 
  13.         if(p->rchild)
  14.             EnQueue(Q,p->rchild)
  15.      } 
  17. }

线索二叉树

利用n-1个空链域将原有的二叉树线索化，线索二叉树的存储结构是一种崭新的物理结构

  1. typedef struct ThreadNode
  2. {
  3.     Elemtype data;
  4.     struct ThreadNode* lchild,rchild;
  5.     int latg,rtag; 
  6. }ThreadNode,*ThreadTree;

中序建立线索二叉树

记忆方法：对称性

void InOrderThread(ThreadTree *p,TreadTree *pre)
{
        if(*p){
            InOrderThread(*p->lchild,*pre)// 左子树递归
            if(!(*p->lchild)
            {  (*p)->lchild = *pre;// 左孩子线索化
                (*p)->ltag = 1;
            }
            else if (!(*pre)->rchild&&(*pre) )
            {
                (*pre)-> rchild = p;// 右孩子线索化
                (*pre)->rtag = 1；
            }
            *pre = p;// 更新pre指针
            InOrderThread((*p)->rchild,*pre)// 右子树递归
        }

}
void CreateInOrderThread(ThreadTree T)
{
        ThreadTree pre = NULL;// 全局变零
        if(!T)
        {
            InOrderThread(&T,&pre);// 中序遍历+线索化二叉树
            pre->rchild = NULL;    // 最后一个节点的线索化
            pre->rtag = 1;
        }
}

中序二叉树的遍历

注意：从根节点开始找第一个中序访问的第一个节点，简单理解就是最左下角的节点

ThreadNode * FirstNode(ThreadNode *p)
{
while(p->ltag == 0)// 最左下的节点，未必叶子节点
    p = p->lchild;
return p;
}

找中序后继，若有右孩子，找到以该右孩子为根节点的最左下节点，否则，为右线索

ThreadNode * NextNode(ThreadNode *p)
{
if(p->rtag == 0)
    return FisrstNode(p->rchild);
 else
     return p->rchild;
}

中序二叉树遍历节点

void InOder(ThreadTree T);
{ // 利用上述两个代码中序遍历线索树
    ThreadNode *p = NULL;
    for (p = FisrtNode(T);p!=NULL;p=NextNode(p))
        visit(p);
}