数据结构 - 二叉树

递归实现前中后序遍历

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

#define TElemType int

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




void visit(TElemType& e){
    printf("%d",e);
}

void Preorder(BiTree T,void(*visit)(TElemType& e)){
    if(T==NULL)return;
    else{
        visit(T->data);
        Preorder(T->lchild, visit);
        Preorder(T->rchild, visit);
    }
}

void Inorder(BiTree T,void(*visit)(TElemType& e)){
    if(T==NULL)return;
    else{
        Preorder(T->lchild, visit);
        visit(T->data);
        Preorder(T->rchild, visit);
    }
}

void Postorder(BiTree T,void(*visit)(TElemType& e)){
    if(T==NULL)return;
    else{
        Preorder(T->lchild, visit);
        Preorder(T->rchild, visit);
        visit(T->data);
    }
}


int main( ){
    
    
    return 0;
}

非递归实现中序遍历

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

#define TElemType int

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




void visit(TElemType& e){
    printf("%d",e);
}

#define DataType BiTree

typedef struct{
    DataType *s;
    int t;
    int MAXNUM;
}SeqStack,*PSeqStack;
void push_seq(PSeqStack pastack,DataType x){
    if(pastack->t==pastack->MAXNUM-1)printf("\n Stack is full!");
    else pastack->s[++pastack->t]=x;
}

PSeqStack createEmptyStack_seq(int m){
    PSeqStack stack = (PSeqStack)malloc(sizeof(SeqStack));

    if(stack){
        stack->s=(DataType*)malloc(sizeof(DataType)*m);
        if(!stack->s){
            free(stack);
            return 0;
        }
        stack->t=-1;
        stack->MAXNUM=m;
        return stack;
    }
    return 0;
}

int isEmptyStack_seq(PSeqStack pastack){
    return (pastack->t==-1)?1:0;
}

int pop_seq(PSeqStack pastack){
    if(isEmptyStack_seq(pastack)){
        printf("\n Stack is free!");
        return 0;
    }
    pastack->t--;
    return 1;
}

DataType top_seq(PSeqStack pastack){
    if(isEmptyStack_seq(pastack)){
        printf("\n Stack is free!");
        exit(0);
    }else{
        return (pastack->s[pastack->t]);
    }
}
BiTNode *GoFarLeft(BiTree T,SeqStack *S){
    if(!T)return NULL;
    while (T->lchild) {
        push_seq(S, T);
        T=T->lchild;
    }
    return T;
}

void Inorder_I(BiTree T,void(*visit)(TElemType& e)){
    SeqStack *S = createEmptyStack_seq(10);
    BiTree t = GoFarLeft(T, S);
    while (t) {
        visit(t->data);
        if(t->rchild)t=GoFarLeft(t->rchild, S);
        else{
            if (!isEmptyStack_seq(S)) {
                t=top_seq(S);
                pop_seq(S);
            }else t = NULL;
        }
    }
}


int main( ){
    
    
    return 0;
}

广度优先遍历

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

#define TElemType int

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

void visit(TElemType& e){
    printf("%d",e);
}

typedef  BiTree  DataType;
typedef struct Qnode QNode;

typedef struct Qnode{
    DataType info;
    QNode *link;
}*QueuePtr;

typedef  struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue,*PLinkQueue;

LinkQueue q;

LinkQueue initQueue(){
    LinkQueue Q;
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front)exit(0);
    Q.front->link=NULL;
    return Q;
}

int enQueue(PLinkQueue q,DataType x){
    QueuePtr qnode = (QueuePtr)malloc(sizeof(QNode));
    if(!qnode)return 0;
    qnode->info=x;
    qnode->link=NULL;
    q->rear->link = qnode;
    q->rear=qnode;
    return 1;
}

DataType deQueue(PLinkQueue q){
    if(q->front==q->rear)return 0;
    QueuePtr p=q->front->link;
    DataType e = p->info;
    q->front->link=p->link;
    if(q->rear==p)q->rear=q->front;
    free(p);
    return e;
}
int queempty(LinkQueue q){
    if(q.front->link)return 1;
    else return 0;
}

void LevelOrder(BiTree root){
    BiTree tnode = root;
    if(root==NULL)exit(0);
    LinkQueue q = initQueue();
    enQueue(&q,tnode);
    while (!queempty(q)) {
        tnode = deQueue(&q);
        printf("%d",tnode->data);
        if(tnode->lchild)enQueue(&q, tnode->lchild);
        if(tnode->rchild)enQueue(&q, tnode->rchild);
    }
}

int main( ){
    
    
    return 0;
}