树

存储结构

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

树的遍历

先序遍历

void PreOrder(BiTree T){
    if(T != NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

先序遍历（非递归）

void PreOrder2(BiTree T){
    SqStack S;  //创建一个栈
    InitStack(S);
    BiTNode *p=T;
    while(p || !IsEmpty(S))
        if(p!=NULL){
            visit(p);
            Push(S,p);
            p=p->lchild;
        }
        else{
            Pop(S,p);
            p=p->rchild;
        }
}

中序遍历

void InOrder(BiTree T){
    if(T != NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

中序遍历（非递归）

void InOrder2(BiTree T){
    SqStack S;
    InitStack(S);
    BiTNode *p=T;
    while(p || !IsEmpty(S)){
        if(p!=NULL){
            Push(S,p);
            p=p->lchild;
        }
        else{
            Pop(S,p);
            visit(p);
            p=p->rchild;
        }
    }
}

后序遍历

void PostOrder(BiTree T){
    if(T != NULL){
        InOrder(T->lchild);
        InOrder(T->rchild);
        visit(T);
    }
}

后序遍历（非递归）

void PostOrder(BiTree T){
    SqStack S;
    InitStack(S);
    BiTNode *p = T,*r = NULL;
    while(p || !IsEmpty(S)){
        if(p){
            Push(S,p);
            p = p->lchild;
        }
        else{
            GetTop(S,p);
            if(p->rchild && p->rchild != r)
                p = p->rchild;
            else{
                Pop(S,p);
                visit(p->data);
                r = p;
                p = NULL;
            }
        }//else
    }//while
}

层序遍历

void LevelOrder(BiTree T){
    InitQueue(Q);
    BiTNode *p = T;
    EnQueue(Q,T);
    while(!QueueEmpty(Q)){
        DeQueue(Q,p);
        visit(p);
        if(p->lchild != NULL)
            EnQueue(Q,p->lchild);
        if(p->rchild != NULL)
            EnQueue(Q,p->rchild);
    }
}

线索二叉树

存储结构

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;      //tag值为0代表指向孩子，1代表前驱后继
}ThreadNode,*ThreadTree;

中序线索化

void InThread(ThreadNode *&p,ThreadNode *&pre){
    if(p){
        InThread(p->lchild,pre);
        if(p->lchild != NULL){
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre != NULL && pre->rchlid == NULL){
            pre->rchlid = p;
            pre->rtag = 1;
        }
        pre = p;
        InThread(p->rchlid,pre);
    }
}
/**********↓建立中序线索二叉树↓****************/
void CreateInThread(ThreadTree T){
    ThreadNode *pre = NULL;
    if(T != NULL){
        InThread(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 FirstNode(p->rchild);
    else
        return p->rchild;
}
void InOrder(ThreadTree T){
    for(ThreadNode *p = FirstNode(T); p != NULL;p = NextNode(p))
        visit(p);
}