二叉树

baseFunc.h

#include <iostream>
using namespace std;
#define ElementType int
#define QElementType BiTree


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

typedef struct PtrStack{
    BiTree *top;
    BiTree *base;
    int length;
}*Stack;

typedef struct QueueNode{
    struct QueueNode *next;
    QElementType data;
}*LNode;
typedef struct circleQueue{
    QueueNode *front,*rear;
}LQueue;

//链栈操作
void initLinkStack(Stack &S);
void Push(Stack &S,BiTree x);
void Pop(Stack &S,BiTree &x);
void getTop(Stack S,BiTree &x);
bool isEmpty(Stack S);


//队列操作
void initQueue(LQueue &Q);
void EnQueue(LQueue &Q,BiTree T);
void DeQueue(LQueue &Q,BiTree &T);
bool isEmpty(LQueue Q);



//二叉树操作
bool CreateBiTree(BiTree &T);
void PreOrder(BiTree T);
void Inorder(BiTree T);
void Postorder(BiTree T);
void Preorder2(BiTree T);
void Inorder2(BiTree T);
void Postorder2(BiTree T);
void Levelorder(BiTree T);

baseFunc.cpp

//
// Created by Vsion on 2019/11/6.
//

#include "header/baseFunc.h"



bool  CreateBiTree(BiTree &T)
{
    int ch;
    cout<<"先序输入字符"<<endl;
    cin>>ch;
    if(ch == 0)  T = nullptr;
    else
    {
        if(! (T = (BiTNode*) malloc (sizeof(BiTNode))))   return false;
        T->data = ch;
        CreateBiTree(T->lchild) ;
        CreateBiTree(T->rchild) ;
    }
    return true;
}

void PreOrder(BiTree T){
    if (T){
        cout<<T->data<<endl;
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
void Inorder(BiTree T){
    if (T){
        Inorder(T->lchild);
        cout<<T->data<<endl;
        Inorder(T->rchild);
    }
}

void Postorder(BiTree T){
    if (T){
        Postorder(T->lchild);
        Postorder(T->rchild);
        cout<<T->data<<endl;
    }
}
void Preorder2(BiTree T){
    Stack S;
    S = new PtrStack;
    initLinkStack(S);
    BiTree p = T;
    while (p||!isEmpty(S)){
        if (p){
            cout<<p->data<<endl;
            Push(S,p);
            p = p->lchild;
        }else{
            Pop(S,p);
            p = p->rchild;
        }
    }
}
void Inorder2(BiTree T){
    Stack S;
    S = new PtrStack;
    initLinkStack(S);
    BiTree p = T;
    while (p||!isEmpty(S)){
        if (p){
            Push(S,p);
            p = p->lchild;
        }
        else{
            Pop(S,p);
            cout<<p->data;
            p = p->rchild;
        }
    }
}
void Postorder2(BiTree T){
    Stack S;
    BiTree r;
    S = new PtrStack;
    initLinkStack(S);
    BiTree p = T;
    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;
                Push(S,p);
                p = p->lchild;
            }else{
                Pop(S,p);
                cout<<p->data<<endl;
                r = p;
                p = nullptr;
            }
        }
    }
}
void Levelorder(BiTree T){

    LQueue Q;
    initQueue(Q);
    BiTree p;
    EnQueue(Q,T);
    while(!isEmpty(Q)){
        DeQueue(Q,p);
        cout<<p->data<<endl;
        if (p->lchild) EnQueue(Q,p->lchild);
        if (p->rchild) EnQueue(Q,p->rchild);

    }

}

void initLinkStack(Stack &S){
    S->base = new BiTree;
    S->top = S->base;
    S->length = 0;
}
void Push(Stack &S,BiTree x){
    *S->top++ = x;
    S->length++;
}
void Pop(Stack &S,BiTree &x){
    x = *--S->top;
    S->length--;
}
void getTop(Stack S,BiTree &x){
    x = *--S->top;
    S->top++;
}

bool isEmpty(Stack S){
    return S->length <= 0;
}




void initQueue(LQueue &Q){
    Q.front = Q.rear = new QueueNode;
    Q.front->next = nullptr;
}
void EnQueue(LQueue &Q,QElementType data){
    LNode p;
    p = new QueueNode;
    p->data = data;
    p->next = nullptr;
    Q.rear->next = p;
    Q.rear = p;
}
void DeQueue(LQueue &Q,QElementType &x){
    LNode p;
    p = new QueueNode;
    p = Q.front->next;
    x = p->data;

    Q.front->next = p->next;

    if (Q.rear == p) Q.rear = Q.front;
    delete p;
}
bool isEmpty(LQueue Q){
    return Q.front == Q.rear;
}