树(2)

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

一:二叉树的遍历.

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

1.先序遍历:

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

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

#define maxsize 100typedef struct{    Bitree Elem[maxsize];    int base,top;}SqStack;void PreOrderUnrec(Bitree t){    SqStack s;    StackInit(s);    p=t;        while (p!=null || !StackEmpty(s))    {        whil<span>本文来源gaodai#ma#com搞*代#码9网#</span>e (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 100typedef 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 100typedef 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; //将头结点与树相连             <strong>InThreading(T);  </strong>        // 中序遍历进行中序线索化，调用上面的函数             pre ->rchild = Thrt;                pre ->RTag = Thread;     //最后一个结点线索化             Thrt ->rchild = pre;            }    return OK; } // InOrderThreading

喜欢 (0)赏

[搞代码]

分享 (0)