欧美性猛交XXXX免费看蜜桃,成人网18免费韩国,亚洲国产成人精品区综合,欧美日韩一区二区三区高清不卡,亚洲综合一区二区精品久久

今天把二叉樹(shù)的非遞歸遍歷實(shí)現了 后序的有點(diǎn)難度 呵呵

#include <stdio.h>
#include <stdlib.h>

typedef struct BitNode
{
char data;
BitNode *lchild,*rchild;
int ltag,rtag;
}BitNode,*BitTree,ElemType;         //樹(shù)的結構體定義

typedef struct node
{
ElemType stack;
struct node *next;
}linkstack;             //棧的結構體定義

int initstack(linkstack **s)//初始化一個(gè)帶頭結點(diǎn)的空棧
{
*s=(linkstack *)malloc(sizeof(linkstack));
if(*s==NULL)exit(-1);
(*s)->next=NULL;
return 1;
}

int push(linkstack *s,ElemType *x)//入棧操作，將x的數據元素插入棧s中，使x成為新的棧頂元素
{
linkstack *p,*q;
q=s;
p=(linkstack *)malloc(sizeof(linkstack));
if(!p)exit(-1);
p->stack=*x;
p->next=NULL;
while(q->next)
   q=q->next;
q->next=p;
return 1;
} 
/////////////////////////////////////////////////
//因為非遞歸遍歷算法 調用的棧不需要 全部出棧
//進(jìn)棧的鏈表實(shí)現的 真正算法為
// q->stack=*x;
// q->next=S->next;
// S->next=q;
////////////////////////////////////////////////

int pop(linkstack *s,ElemType *e)//出棧操作,先將棧s的棧頂結點(diǎn)的值送到e所指向的內存單元，然后刪除棧頂結點(diǎn)
{
linkstack *p,*q;
p=s;
if(s->next==NULL)return 0;
while(p->next)
{
   q=p;
   p=p->next;
}
q->next=NULL;
*e=p->stack;
free(p);
return 1;
}

int emptystack(linkstack *s)//判斷棧是否為空
{
if(s->next==NULL)return 1;
else return 0;
}

int gettop(linkstack *s,ElemType *e)
{
linkstack *p,*q; 
p=s;
if(s->next==NULL)return 0;
while(p->next)
{
   q=p;
   p=p->next;
}
*e=p->stack;
return 1;
}

BitTree CreateBiTree()
{
BitTree bt;
char x;
x=getchar();
if(x=='#') bt=NULL;
else
{
   bt=(BitTree)malloc(sizeof(BitNode));
   bt->data=x;
   bt->lchild=NULL;
   bt->rchild=NULL;
   bt->lchild=CreateBiTree();
   bt->rchild=CreateBiTree();
}
return bt;
}
//////////////////////////////////////////////////////////////////////////
//Comment:非遞歸先序遍歷 二叉樹(shù)
//Algorithm:沿著(zhù)左指針訪(fǎng)問(wèn)沿途經(jīng)過(guò)的根節點(diǎn)，同時(shí)將右指針進(jìn)棧，以便在遞歸訪(fǎng)
//問(wèn)左子樹(shù)完成后能得到右子樹(shù)的根節點(diǎn)的地址，如此重復進(jìn)行，直到?？?。
//////////////////////////////////////////////////////////////////////////
void PreOrderBiTree(BitTree T)
{
linkstack *S;
BitTree p,q;
q=(BitTree)malloc(sizeof(BitNode));
initstack(&S);
p=T;
while(p||!emptystack(S))
{
   while (p)
   {
    printf("%c ",p->data);
    push(S,p);
    p=p->lchild;
   }
   if(pop(S,q))
    p=q->rchild;
}
}
//////////////////////////////////////////////////////////////////////////
//Comment:非遞歸中序遍歷 二叉樹(shù)
//Algorithm:先沿著(zhù)左指針走到二叉樹(shù)中最左下的結點(diǎn)，即左指針為空的結點(diǎn)，將沿
//途經(jīng)過(guò)的根節點(diǎn)，指針進(jìn)棧。當左指針為空時(shí)，從棧中取出根節點(diǎn)訪(fǎng)問(wèn)，然后再跳
//到右子樹(shù)上。
//////////////////////////////////////////////////////////////////////////
void InOrderBiTree(BitTree T)
{
linkstack *S;
BitTree p,q;
q=(BitTree)malloc(sizeof(BitNode));
initstack(&S);
p=T;
while (p||!emptystack(S))
{
   while (p)
   {
    push(S,p);
    p=p->lchild;
   }
   pop(S,q);
   printf("%c",q->data);
   p=q->rchild;
}
}
//////////////////////////////////////////////////////////////////////////
//Comment:非遞歸后續遍歷 二叉樹(shù)
//Algorithm:先沿著(zhù)左指針走到二叉樹(shù)中最左下的結點(diǎn)，將沿途經(jīng)過(guò)的根節點(diǎn)指針進(jìn)
//棧，若右子樹(shù)為空，則彈棧并訪(fǎng)問(wèn)根節點(diǎn)，否則，跳到右子樹(shù)上。
//////////////////////////////////////////////////////////////////////////
void PostOrderBiTree(BitTree T)
{
    linkstack *S;
    BitTree p,q;
    char flag;//標記訪(fǎng)問(wèn)過(guò)的節點(diǎn)
    initstack(&S);
    q=(BitTree)malloc(sizeof(BitNode));
    p=T;
    while (p||!emptystack(S))
    {
        if(p!=q)
        {
            while(p)                                                  //當子樹(shù)p不為空時(shí) 進(jìn)棧
            {
                push(S,p);                                              
                if(p->lchild)p=p->lchild;                       //不為空 后移指向左子樹(shù)
                else p=p->rchild;                                //為空指向 右子樹(shù)
            }
        }
        if (emptystack(S))break;                       
        gettop(S,q);
        if(q->rchild==p)                                        //判斷是 遍歷過(guò) 右子樹(shù) 如遍歷過(guò)右子樹(shù) 說(shuō)明該遍歷根子樹(shù)
        {
            p=(BitTree)malloc(sizeof(BitNode));
            pop(S,p);
            printf("%c",p->data);
            p=q;
            flag = p->data;                                   //記錄 遍歷過(guò)的子樹(shù)
        }
        else
        {
            p=q->rchild;
            if (flag == p->data)//如果根節點(diǎn)的右子樹(shù)剛剛訪(fǎng)問(wèn)完成，那么打印根節點(diǎn)。
            {
                p=(BitTree)malloc(sizeof(BitNode));
                pop(S,p);
                printf("%c",p->data);
                p=q;
                flag = p->data;
            }
        }
  
    }
}

前序、中序、后序的非遞歸遍歷中，要數后序最為麻煩，如果只在棧中保留指向結點(diǎn)的指針，那是不夠的，必須有一些額外的信息存放在棧中。
方法有很多，這里只舉一種，先定義棧結點(diǎn)的數據結構
typedef struct{Node * p; int rvisited;}SNode //Node 是二叉樹(shù)的結點(diǎn)結構，rvisited==1代表p所指向的結點(diǎn)的右結點(diǎn)已被訪(fǎng)問(wèn)過(guò)。

lastOrderTraverse(BiTree bt){
　　//首先，從根節點(diǎn)開(kāi)始，往左下方走，一直走到頭，將路徑上的每一個(gè)結點(diǎn)入棧。
　　p = bt;
　　while(bt){
　　　　push(bt, 0); //push到棧中兩個(gè)信息，一是結點(diǎn)指針，一是其右結點(diǎn)是否被訪(fǎng)問(wèn)過(guò)
　　　　bt = bt.lchild;
　　}

　　//然后進(jìn)入循環(huán)體
　　while(!Stack.empty()){ //只要棧非空
　　　　sn = Stack.getTop(); // sn是棧頂結點(diǎn)

　　　　//注意，任意一個(gè)結點(diǎn)N，只要他有左孩子，則在N入棧之后，N的左孩子必然也跟著(zhù)入棧了(這個(gè)體現在算法的后半部分)，所以當我們拿到棧頂元素的時(shí)候，可以確信這個(gè)元素要么沒(méi)有左孩子，要么其左孩子已經(jīng)被訪(fǎng)問(wèn)過(guò)，所以此時(shí)我們就不關(guān)心它的左孩子了，我們只關(guān)心其右孩子。

　　　　//若其右孩子已經(jīng)被訪(fǎng)問(wèn)過(guò)，或是該元素沒(méi)有右孩子，則由后序遍歷的定義，此時(shí)可以visit這個(gè)結點(diǎn)了。
　　　　if(!sn.p.rchild || sn.rvisited){
　　　　　　p = pop();
　　　　　　visit(p);
　　　　}
　　　　else //若它的右孩子存在且rvisited為0，說(shuō)明以前還沒(méi)有動(dòng)過(guò)它的右孩子，于是就去處理一下其右孩子。
　　　　{ 
　　　　　　//此時(shí)我們要從其右孩子結點(diǎn)開(kāi)始一直往左下方走，直至走到盡頭，將這條路徑上的所有結點(diǎn)都入棧。

　　　　　　//當然，入棧之前要先將該結點(diǎn)的rvisited設成1，因為其右孩子的入棧意味著(zhù)它的右孩子必將先于它被訪(fǎng)問(wèn)(這很好理解，因為我們總是從棧頂取出元素來(lái)進(jìn)行visit)。由此可知，下一次該元素再處于棧頂時(shí)，其右孩子必然已被visit過(guò)了，所以此處可以將rvisited設置為1。
　　　　　　sn.rvisited = 1;

　　　　　　//往左下方走到盡頭，將路徑上所有元素入棧
　　　　　　p = sn.p.rchild;
　　　　　　while(p != 0){
　　　　　　　　push(p, 0);
　　　　　　　　p = p.lchild;
　　　　　　}
　　　　}//這一輪循環(huán)已結束，剛剛入棧的那些結點(diǎn)我們不必管它了，下一輪循環(huán)會(huì )將這些結點(diǎn)照顧的很好。
　　}
}