二叉树的一些基本操作

#ifndef BITREE_H_INCLUDED
#define BITREE_H_INCLUDED

/************************************************
 *文件名: BiTree.h
 *创建人: 水龙头
 *日  期: 2019.7.22
 *描  述: 二叉树的基本操作
 ***********************************************/
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define INFEASIBLE -1
typedef char TElemType;
typedef int Status;
//二叉树节点类型
typedef struct BiTNode
{
    TElemType data;
    int flag;       //标志域，为了方便后序遍历的进行
    struct BiTNode *lchild, *rchild;

}BiTNode, *BiTree;
//构造空二叉树
Status InitBiTree(BiTree&);
//创建一棵二叉树
Status CreateBiTree(BiTree&);
//先序遍历
Status PreOrderTraverse(const BiTree&, Status (*visit)(const BiTree&));
//中序遍历
Status InOrderTraverse(const BiTree&, Status (*visit)(const BiTree&));
//后序遍历
Status PostOrderTraverse(const BiTree&, Status (*visit)(const BiTree&));
//层次遍历
Status LevelOrderTraverse(const BiTree&, Status (*visit)(const BiTree&));
//销毁一颗二叉树
Status DestroyBiTree(BiTree&);
//清空一棵二叉树
Status ClearBiTree(BiTree&);
//判断一颗二叉树是否为空
Status BiTreeEmpty(const BiTree&);
//求二叉树的深度
Status BiTreeDepth(const BiTree&);
//插入一个节点
Status InsertChild(BiTree&);
//删除一个节点
Status DeleteChild(BiTree&);
//查找节点所在处
BiTree Location(const BiTree&, TElemType, Status (*compare)(BiTree, TElemType));
//访问节点
Status Visit(const BiTree&);
//比较两关键字是否相等
Status Compare(BiTree, TElemType);

#endif // BITREE_H_INCLUDED




/************************************************
 *文件名: BiTree.cpp
 *创建人: 水龙头
 *日  期: 2019.7.22
 *描  述: 二叉树的基本操作
 ***********************************************/
#include <iostream>
#include "BiTree.h"
#include "Stack.h"
#include "Queue.h"
//注意将各个头文件保持一致
using namespace std;
//构造空二叉树
Status InitBiTree(BiTree& T)
{
    T = NULL;
    return OK;
}
//创建一棵二叉树(先序递归创建)
Status CreateBiTree(BiTree& T)
{
    //节点数据
    TElemType ch;
    cin >> ch;
    if(ch == '@')
    {
        T = NULL;
        return OK;
    }
    else
    {
        T = new BiTNode;
        if(T)
        {
            T->data = ch;
            CreateBiTree(T->lchild);
            CreateBiTree(T->rchild);
            return OK;
        }
        else
        {
            //节点创建失败，导致直接退出程序
            exit(-1);
        }
    }
}
//先序遍历
Status PreOrderTraverse(const BiTree& T, Status (*visit)(const BiTree&))
{
    //先序遍历的总体思路:
    //如果左儿子存在，则将其压入栈中；如果左儿子不存在，则将栈顶元素弹出，并令指针指向其右儿子。
    //在节点压入栈中之前就要将其访问掉。
    BiTree ptr = T, p = NULL;
    if(ptr)
    {
        //格式需要
        cout << "先序遍历的结果为: ";
        if(visit(ptr))
        {
            //因为需要将指针压入栈中，所以需要使栈中的元素类型与指针类型保持一致
            LinkList top = NULL;
            Init_Stack(top);
            Push(top, ptr);
            ptr = ptr->lchild;
            while(ptr || !StackEmpty(top))
            {
                //如果左儿子存在
                if(ptr)
                {
                    if(visit(ptr))
                    {
                        Push(top, ptr);
                        ptr = ptr->lchild;
                    }
                    //访问失败
                    else
                        return ERROR;
                }
                else if(!ptr)
                {
                    Pop(top, p);
                    ptr = p->rchild;
                }

            }
        }
        else
            return ERROR;
    }
    //格式需要
    cout << endl;
    return OK;
}
//中序遍历
Status InOrderTraverse(const BiTree& T, Status (*visit)(const BiTree&))
{
    //中序遍历的总体思路:
    //仔细观察会发现，其实先序遍历与中序遍历走的路线是完全一样的，唯一的区别在于节点的访问时机。
    //在节点弹出时再对其进行访问。
    BiTree ptr = T, p = NULL;
    if(ptr)
    {
        //格式需要
        cout << "先序遍历的结果为: ";
        LinkList top = NULL;
        Init_Stack(top);
        Push(top, ptr);
        ptr = ptr->lchild;
        while(ptr || !StackEmpty(top))
        {
            if(ptr)
            {
                Push(top, ptr);
                ptr = ptr->lchild;
            }
            else if(!ptr)
            {
                Pop(top, p);
                if(visit(p))
                {
                    ptr = p->rchild;
                }
                //访问失败
                else
                {
                    return ERROR;
                }
            }
        }
    }
    //格式需要
    cout << endl;
    return OK;
}
//后序遍历
Status PostOrderTraverse(const BiTree& T, Status (*visit)(const BiTree&))
{
    //后序遍历的思路:
    //先对于先序与中序来说，后序的路线更为复杂。
    //多了一个标志域；只有当该节点已经进入过栈中两次后才可以对其进行访问。
    BiTree ptr = T, p = NULL;
    if(ptr)
    {
        //格式需要
        cout << "先序遍历的结果为: ";
        LinkList top = NULL;
        Init_Stack(top);
        //表示该节点第一次被压入栈中
        ptr->flag = 1;
        Push(top, ptr);
        ptr = ptr->lchild;
        while(ptr || !StackEmpty(top))
        {
            if(ptr)
            {
                ptr->flag = 1;
                Push(top, ptr);
                ptr = ptr->lchild;
            }
            else if(!ptr)
            {
                Pop(top, p);
                if(p->flag == 1)
                {
                    //表示该节点第二次入栈
                    p->flag = 2;
                    Push(top, p);
                    ptr = p->rchild;
                }
                //该节点已经进入过栈中两次
                else
                {
                    if(visit(p))
                    {
                        //为了让下一次进入循环就直接出栈
                        ptr = NULL;
                    }
                    else
                        return ERROR;
                }
            }
        }

    }
    //格式需要
    cout << endl;
    return OK;
}
//层次遍历
Status LevelOrderTraverse(const BiTree& T, Status (*visit)(const BiTree&))
{
    //层次遍历的思路:
    //从上到下、从左到右.
    //一个节点要在其左右儿子（如果存在的话）都进入队列后,再出队列并立即对其进行访问.
    BiTree ptr = T;
    QueuePtr q = NULL;
    if(ptr)
    {
        //格式需要
        cout << "层次遍历的结果为: ";
        LinkQueue Q;
        InitQueue(Q);
        EnQueue(Q, ptr);
        while(!QueueEmpty(Q))
        {
            //得到队首元素
            //因为所使用的队列头文件GetHead函数参数类型有点冲突，所以此处需要拆一下包装。
            //注意q的类型
            GetHead(Q, q);
            //如果队首的左儿子存在则入队列
            if(q->Qdata->lchild)
            {
                EnQueue(Q, q->Qdata->lchild);
            }
            //如果ptr的右儿子存在则入队列
            if(q->Qdata->rchild)
            {
                EnQueue(Q, q->Qdata->rchild);
            }
            //然后再删除队首元素并对其进行访问
            DeQueue(Q, q->Qdata);
            if(!visit(q->Qdata))
            {
                //访问失败
                return ERROR;
            }
        }
    }
    //格式需要
    cout << endl;
    return OK;
}
//销毁(清空)一颗(链式)二叉树
Status DestroyBiTree(BiTree& T)
{
    if(T)
    {
        DestroyBiTree(T->lchild);
        DestroyBiTree(T->rchild);
        T = NULL;
    }
    return OK;
}
//判断一颗二叉树是否为空
Status BiTreeEmpty(const BiTree& T)
{
    if(T)
    {
        return ERROR;
    }
    else
        return TRUE;
}
//求二叉树的深度
Status BiTreeDepth(const BiTree& T)
{
    int Depth = 0, LeftDepth = 0, RigthDepth = 0;
    if(T)
    {
        LeftDepth = BiTreeDepth(T->lchild);
        RigthDepth = BiTreeDepth(T->rchild);
        Depth = 1 + (LeftDepth > RigthDepth ? LeftDepth : RigthDepth);
        return Depth;
    }
    return 0;
}
//访问节点
Status Visit(const BiTree& p)
{
    if(p)
    {
        cout << p->data << '	';
        return OK;
    }
    else
        return ERROR;
}
//比较两关键字是否相等
Status Compare(BiTree ptr1, TElemType ptr2)
{
    if(ptr1->data == ptr2)
        return TRUE;
    else
        return 0;
}
//查找节点所在处
BiTree Location(const BiTree& T, TElemType e, Status (*compare)(BiTree, TElemType))
{
    //模仿了一下层次遍历
    BiTree ptr = T;
    QueuePtr q = NULL;
    if(ptr)
    {
        LinkQueue Q;
        InitQueue(Q);
        EnQueue(Q, ptr);
        while(!QueueEmpty(Q))
        {
            //得到队首元素
            //因为所使用的队列头文件GetHead函数参数类型有点冲突，所以此处需要拆一下包装。
            //注意q的类型
            GetHead(Q, q);
            //如果队首的左儿子存在则入队列
            if(q->Qdata->lchild)
            {
                EnQueue(Q, q->Qdata->lchild);
            }
            //如果ptr的右儿子存在则入队列
            if(q->Qdata->rchild)
            {
                EnQueue(Q, q->Qdata->rchild);
            }
            //然后再删除队首元素并对其进行访问
            DeQueue(Q, q->Qdata);
            if(compare(q->Qdata, e))
            {
                return (q->Qdata);
            }
        }
    }
    return NULL;
}



 /************************************************
 *文件名: Stack.h
 *创建人: 水龙头
 *日  期: 2019.7.20
 *描  述: 链式栈（带表头）
 ***********************************************/
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED



#include<iostream>
#include "BiTree.h"
using namespace std;
#define TRUE 1
#define FALSE 0
#define ERROR -1
#define OK 1
#define OVERFLOW -2
#define INFEASIBLE -1
typedef BiTree SElemType;
typedef int Status;
typedef struct SNode
{
    SElemType data;
    struct SNode *next;
}SNode, *LinkList;
Status Init_Stack(LinkList &top);
Status Push(LinkList &top, SElemType ch);
Status Pop(LinkList &top, SElemType &e);
Status GetTop(const LinkList &top, SElemType &e);
Status DestroyStack(LinkList&);
Status ClearStack(LinkList&);
Status StackEmpty(const LinkList&);
Status StackLength(const LinkList&);
Status StackTraverse(const LinkList& , Status (*visit)(const LinkList&));
Status Visit(const LinkList&);

#endif // STACK_H_INCLUDED




/************************************************
 *文件名: Stack.cpp
 *创建人: 水龙头
 *日  期: 2019.7.20
 *描  述: 链式栈（带表头）
 ***********************************************/
#include "Stack.h"
Status GetTop(const LinkList &top, SElemType &e)      //得到栈顶元素
{
    if(top)
    {
        LinkList p = top;
        if(!p->next)
        {
            return ERROR;
        }
        else
        {
            e = top->data;
            return OK;
        }
    }
    else
    {
        return INFEASIBLE;
    }
}
Status DestroyStack(LinkList& top)
{
    LinkList ptr = NULL;
    while(top)
    {
        ptr = top;
        top = top->next;
        free(ptr);
    }
    return OK;
}
Status ClearStack(LinkList& top)
{
    if(top)
    {
        LinkList ptr = NULL;
        while(top->next)
        {
            ptr = top;
            top = top->next;
            free(ptr);
        }
        return OK;
    }
    else
        return INFEASIBLE;
}
Status StackEmpty(const LinkList& top)
{
    if(top)
    {
        if(top->next)
        {
            return FALSE;
        }
        else
            return TRUE;
    }
    else
        return INFEASIBLE;
}
Status StackLength(const LinkList& top)
{
    if(top)
    {
        int count = 0;
        LinkList ptr = top;
        while(ptr->next)
        {
            ptr = ptr->next;
            count++;
        }
        return count;
    }
    else
        return INFEASIBLE;
}
Status StackTraverse(const LinkList& top, Status (*visit)(const LinkList&))
{
    if(top)
    {
        LinkList ptr = top;
        while(ptr->next)
        {
            visit(ptr);
            ptr = ptr->next;
        }
        return OK;
    }
    else
        return INFEASIBLE;
}
Status Visit(const LinkList& ptr)
{
    cout << ptr->data << '	';
    return OK;
}
Status Init_Stack(LinkList &top)           //初始化栈
{
    LinkList p = (SNode *)malloc(sizeof(SNode));
    if(!p)
    {
        return OVERFLOW;
    }
    else
    {
        p->next = NULL;
        top = p;
        return OK;
    }
}
Status Push(LinkList &top, SElemType ch)
{
    if(top)
    {
        LinkList q = (SNode *)malloc(sizeof(SNode));
        if(!q)
        {
            return OVERFLOW;
        }
        else
        {
            q->next = top;        //注意这一步是将头指针赋给新节点的后继
            q->data = ch;
            top = q;
            return OK;
        }
    }
    else
        return INFEASIBLE;
}
Status Pop(LinkList &top,SElemType&e)           //不能对字面值进行引用
{
    if(top)
    {
        LinkList p = top;
        if(!p->next)
        {
            return ERROR;
        }
        else
        {
            e = top->data;
            top = top->next;
            free(p);
            return OK;
        }
    }
    else
        return INFEASIBLE;
}




/************************************************
 *文件名: Queue.h
 *创建人: 水龙头
 *日  期: 2019.7.14
 *描  述: 链式队列
 ***********************************************/
#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED


#include <iostream>
#include "BiTree.h"
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR -1
#define OVERFLOW -2

typedef BiTree QElemType;
typedef int Status;
typedef struct QNode
{
    QElemType Qdata;
    struct QNode* next;
}QNode, *QueuePtr;
typedef struct
{
    QueuePtr front;         //队首指针
    QueuePtr rear;          //队尾指针
}LinkQueue;
Status InitQueue(LinkQueue&);               //初始化队列
Status DestroyQueue(LinkQueue&);            //销毁队列
Status ClearQueue(LinkQueue&);              //清空队列
Status QueueEmpty(const LinkQueue&);              //判断队列是否为空
int QueueLength(const LinkQueue&);                //返回队列长度
Status GetHead(const LinkQueue&, QueuePtr&);      //返回队首元素
Status EnQueue(LinkQueue&, QElemType);          //插入一个元素
Status DeQueue(LinkQueue&, QElemType&);          //删除一个元素
Status QueueTraverse(const LinkQueue&, Status (*visit)(const QueuePtr ));  //遍历整个队列
Status Visit(const QueuePtr);



#endif // QUEUE_H_INCLUDED




 /************************************************
 *文件名:Queue.cpp
 *创建人:水龙头
 *日  期: 2019.7.14
 *描  述: 链式队列
 ***********************************************/
#include "Queue.h"

Status InitQueue(LinkQueue& Q)
{
    Q.front = Q.rear = new QNode;       //带头节点的链式队列
    if(Q.front)
    {
        Q.front->next = NULL;
        return OK;
    }
    else
        return OVERFLOW;
}
Status DestroyQueue(LinkQueue& Q)
{
    while(Q.front)
    {
        Q.rear = Q.front->next;
        delete (Q.front);       //空间虽已销毁，但原本指向该空间的指针还在，只不过变为野指针了而已。
        Q.front = Q.rear;
    }
    return OK;
}
Status ClearQueue(LinkQueue& Q)
{
    QueuePtr ptr = Q.front->next;
    Q.rear = Q.front;
    while(ptr)
    {
        QueuePtr p = ptr;
        ptr = ptr->next;
        delete p;
    }
    return OK;
}
Status QueueEmpty(const LinkQueue& Q)
{
    if(Q.front == Q.rear)
        return TRUE;
    else
        return FALSE;
}
int QueueLength(const LinkQueue& Q)
{
    if(Q.front == Q.rear)
        return 0;
    else
    {
        int count = 0;
        QueuePtr ptr = Q.front->next;
        while(ptr)
        {
            count++;
            ptr = ptr->next;
        }
        return count;
    }
}
Status GetHead(const LinkQueue& Q, QueuePtr& ptr)
{
    QueuePtr p = Q.front->next;
    if(p)
    {
        ptr = p;
        return OK;
    }
    else
    {
        ptr = NULL;
        return ERROR;
    }
}
Status EnQueue(LinkQueue& Q, QElemType e)
{
    QueuePtr ptr = new QNode;
    if(ptr)
    {
        ptr->next = NULL;
        ptr->Qdata = e;
        Q.rear->next = ptr;
        Q.rear = ptr;
        return OK;
    }
    else
        return OVERFLOW;
}
Status DeQueue(LinkQueue& Q, QElemType& e)
{
    if(Q.front == Q.rear)
        return ERROR;
    else                                //注意这是队列，只能从队首删除元素，从队尾插入元素
    {
        QueuePtr ptr = Q.front->next;
        Q.front->next = ptr->next;
        e = ptr->Qdata;
        if(ptr == Q.rear)       //如果原本队列里只有一个元素
        {
            Q.rear = Q.front;
        }
        delete ptr;
        return OK;
    }
}
Status Visit(const QueuePtr ptr)
{
    if(!ptr)
    {
        return ERROR;
    }
    else
    {
        cout << ptr->Qdata << '	';
        return OK;
    }
}
Status QueueTraverse(const LinkQueue& Q, Status (*visit)(const QueuePtr ))
{
    QueuePtr ptr = NULL;
    if(Q.front == Q.rear)
        return ERROR;
    else
    {
        ptr = Q.front->next;        //从第一个节点开始遍历（带头节点的链表）
        while(ptr)
        {
            (*visit)(ptr);
            ptr = ptr->next;
        }
        cout << endl;
        return OK;
    }
}