树(2)

一:二叉树的遍历. 由于递归算法很简单，在这里就不例举了，主要看一下非递归算法(其实也就是用栈实现，因为递归本身就是一种栈) 1.先序遍历: 思想:(1)从根节点依次遍历当前节点的左子树，边遍历访问，并且压入栈 (2).再访问当前栈顶结点的右子树,然后再返回

一:二叉树的遍历.

由于递归算法很简单，在这里就不例举了，主要看一下非递归算法(其实也就是用栈实现，因为递归本身就是一种栈)

1.先序遍历:

思想:(1)从根节点依次遍历当前节点的左子树，边遍历访问，并且压入栈

(2).再访问当前栈顶结点的右子树,然后再返回到(1)执行,直至栈空

#define maxsize 100
typedef struct
{
    Bitree Elem[maxsize];
    int base,top;
}SqStack;

void PreOrderUnrec(Bitree t)
{
    SqStack s;
    StackInit(s);
    p=t;
    
    while (p!=null || !StackEmpty(s))
    {
        while (p!=null)             //遍历左子树
        {
            visite(p->data);
            push(s,p);
            p=p->lchild;       
        }//endwhile
        
        if (!StackEmpty(s))         //通过下一次循环中的内嵌while实现右子树遍历
        {
            p=pop(s);
            p=p->rchild;        
        }//endif                
    }//endwhile 
    
}//PreOrderUnrec

2.中序遍历:

思想:(1)从根节点遍历左子树，边遍历边入栈

(2)弹出栈顶元素，并访问，然后访问当前栈顶的右子树,回到(1)

#define maxsize 100
typedef struct
{
    Bitree Elem[maxsize];
    int base,top;
}SqStack;

void InOrderUnrec(Bitree t)
{
    SqStack s;
    StackInit(s);
    p=t;
    while (p!=null || !StackEmpty(s))
    {
        while (p!=null)             //遍历左子树
        {
            push(s,p);
            p=p->lchild;
        }//endwhile
        
        if (!StackEmpty(s))
        {
            p=pop(s);
            visite(p->data);        //访问根结点
            p=p->rchild;            //通过下一次循环实现右子树遍历
        }//endif   
    
    }//endwhile
}//InOrderUnrec

3.后序遍历(其实还不是特清楚，代码来自百度):(需要设置一个标志量表示当前节点的右子树是否被访问)

#define maxsize 100
typedef enum{L,R} tagtype;//标记的类型，为R时表示当前结点的
typedef struct 
{
    Bitree ptr;
    tagtype tag;
}stacknode;

typedef struct
{
    stacknode Elem[maxsize];
    int base,top;
}SqStack;

void PostOrderUnrec(Bitree t)
{ 
    SqStack s;
    stacknode x;
    StackInit(s);
    p=t;
    
    do 
    {
        while (p!=null)        //遍历左子树
        {
            x.ptr = p; 
            x.tag = L;         //标记为左子树
            push(s,x);
            p=p->lchild;
        }
    
        while (!StackEmpty(s) && s.Elem[s.top].tag==R)//如果
        {
            x = pop(s);
            p = x.ptr;
            visite(p->data);   //tag为R，表示右子树访问完毕，故访问根结点       
        }
        
        if (!StackEmpty(s))
        {
            s.Elem[s.top].tag =R;     //遍历右子树
            p=s.Elem[s.top].ptr->rchild;        
        }    
　　}while (!StackEmpty(s));
}//PostOrderUnrec

二.线索二叉树:

含有n个结点的二叉树,一共有2n个指针域,有n+1个处于Null状态，为了使空间不浪费，可以让这些空的指针域指向二叉树各种遍历的前驱或后继结点,这样又可以方便查找每一个元素，而不必采用遍历，节省了时间

1.存储结构:

typedef enum { Link, Thread } PointerThr; 
    // Link==0:指针，Thread==1:线索
typedef struct BiThrNode{
    TElemType data;
    Struct BiThrNode *lchild, *rchild;    // 左右孩子指针
    PointerThr LTag, RTag;   // 左右标志,当LTag=Thread时，表示线索,为Link时表示指向下一结点
} BiThrNode, *BiThrTree;

1）若结点有左子树，则lchild指向其左孩子；
否则， lchild指向其直接前驱(即线索)；

2).若结点有右子树，则rchild指向其右孩子；

否则，rchild指向其后继(即线索)；

例：

2.线索二叉树的中序遍历算法:

Status IOTraver_T( BiThrTree T,Status (*Visit)(TElemType e) )
{ //T指向头结点，头结点的左链lchild指向根结点，中序遍历 //二叉线索树T的非递归算法，对每个数据元素调用函数Visit。
 p = T->lchild;  //p指向根结点     
 while (p != T) {     //空树或遍历结束时，p = = T
    while (p->LTag==Link) p = p->lchild;  
    if (!Visit(p->data)) return ERROR;  //访问其左子树为空的结点
    while (p->RTag==Thread && p->rchild!=T) 
       { p = p->rchild; Visit(p->data);  } //访问后继结点
    p = p->rchild; 
    }
 return OK;  
} // IOTraver_T

3.线索二叉树的生成算法:

void InThreading (BiThrTree p)//中序并线索化
 {
    if (p)
    {  
       InThreading( p->lchild );  // 左子树线索化
        if ( !p->lchild ) 
         { p->LTag=Thread; p->lchild=pre; }  // 前驱线索

        if ( !pre->rchild )
         { pre->RTag=Thread; pre->rchild=p; }  //后继线索
        pre = p;                         // 保持pre指向p的前驱
      InThreading(p->rchild);      //右子树线索化
     }
  } // InThreading

Status InorderThreading(BiThrTree  & Thrt, BiThrTree  T)
{ //中序遍历二叉树T,并将其中序线索化, Thrt 指向头结点.
   if ( ! (Thrt = (BiThrTree) malloc ( sizeof (BiThrnode) ) )  exit  ( OVERFLOW ) ;
   Thrt ->LTag = Link;   Thrt ->RTag = Thead;   // 建头结点
   Thrt ->rchild = Thrt ;                                       //右指针回指
   if ( !T ) Thrt ->lchild = Thrt ;    // 若二叉树空,则左指针回指
   else {
             Thrt ->lchild = T;     pre = Thrt; //将头结点与树相连
             InThreading(T);          // 中序遍历进行中序线索化，调用上面的函数
             pre ->rchild = Thrt;   
             pre ->RTag = Thread;     //最后一个结点线索化
             Thrt ->rchild = pre;
            }
    return OK;
 } // InOrderThreading