C++ 二叉树的基本操作

发布时间: 更新时间: 总字数:2328 阅读时间:5m 作者: 分享 复制网址

C++ 二叉树的基本操作

实验五:二叉树的基本操作

  • (1)输入字符序列,建立二叉链表。
  • (2)先序、中序、后序遍历二叉树:递归算法。
  • (3)中序遍历二叉树:非递归算法。(最好也能实现先序、后序非递归算法)
  • (4)求二叉树的高度 。
  • (5)求二叉树的叶子个数。
  • (6)借助队列实现二叉树的层次遍历。
  • (7)在主函数中设计一个简单的菜单,分别调试上述算法。

源码

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define LIST_INT_SIZE 100
#define LISTINCREMENT 10
int dep, count = 0;
typedef int Status;
typedef char TElemType;
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
//建立二叉树
Status CreateBiTree(BiTree &T)
{
    char ch;
    getchar();
    scanf("%c", &ch);
    if (ch == ' ' || ch == '\n')
    {
        T = NULL;
        return ERROR;
    }
    else
    {
        T = (BiTree)malloc(sizeof(BiTNode));
        T->data = ch;
        printf("请输入%c的左孩子:", T->data);
        CreateBiTree(T->lchild);
        printf("请输入%c的右孩子:", T->data);
        CreateBiTree(T->rchild);
        return OK;
    }
}
//主菜单
void print()
{
    printf("\n菜单如下:\n");
    printf("1 . 输入字符序列,建立二叉链表\n");
    printf("2 . 先序、中序、后序遍历二叉树:递归算法\n");
    printf("3 . 先序、中序、后序遍历二叉树:非递归算法\n");
    printf("4 . 求二叉树的高度 \n");
    printf("5 . 求二叉树的叶子个数\n");
    printf("6 . 借助队列实现二叉树的层次遍历\n");
    printf("0 . EXIT\n请选择操作序号:");
}
//先序、中序、后序遍历二叉树:递归算法
void print2()
{
    printf("\n递归算法遍历二叉树,菜单如下:\n");
    printf("1.先根遍历\n");
    printf("2.中序遍历\n");
    printf("3.后续遍历\n");
    printf("0.退出\n");
    printf("请输入二级菜单选择:");
}
Status Visit(BiTree T)
{
    if (T)
    {
        printf("%c ", T->data);
        return OK;
    }
}
Status PrintElement(TElemType e)
{
    printf(" %c ", e);
    return OK;
}
//先序
Status PreOrderTraverse(BiTree T, Status (*Visit)(TElemType e))
{
    if (T)
    {
        if (Visit(T->data))
            if (PreOrderTraverse(T->lchild, Visit))
                if (PreOrderTraverse(T->rchild, Visit))
                    return OK;
        return ERROR;
    }
    else
        return OK;
}
//中序
Status MidOrderTraverse(BiTree T, Status (*Visit)(TElemType e))
{
    if (T)
    {
        if (MidOrderTraverse(T->lchild, Visit))
            if (Visit(T->data))
                if (MidOrderTraverse(T->rchild, Visit))
                    return OK;
        return ERROR;
    }
    else
        return OK;
}
//后序
Status LastOrderTraverse(BiTree T, Status (*Visit)(TElemType e))
{
    if (T)
    {
        if (LastOrderTraverse(T->lchild, Visit))
            if (LastOrderTraverse(T->rchild, Visit))
                if (Visit(T->data))
                    return OK;
        return ERROR;
    }
    else
        return OK;
}
//求树的叶子的个数,和打印出叶子
Status LeafNumTree(BiTree T)
{
    int lnum, rnum;
    if (T != NULL)
    {
        if (T->lchild == NULL && T->rchild == NULL)
            return 1;
        else
        {
            lnum = LeafNumTree(T->lchild);
            rnum = LeafNumTree(T->rchild);
            return lnum + rnum;
        }
    }
    return 0;
}
//求二叉树的高度
Status BiTreeDepth(BiTree T)
{
    int l, r;
    if (T)
    {
        l = BiTreeDepth(T->lchild);
        r = BiTreeDepth(T->rchild);
        if (l >= r)
            dep += l;
        else dep += r;
    }
    else
        return 1;
}
//先序、中序、后序遍历二叉树:非递归算法
void print3()
{
    printf("\n非递归算法遍历二叉树,菜单如下:\n");
    printf("1.先根遍历\n");
    printf("0.退出\n");
    printf("请输入二级菜单选择:");
}
typedef struct QueueNode
{
    BiTree e;
    struct QueueNode *next;
} QueueNode, *QueuePtr;                 //定义队列结点结构
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
} LinkQueue;
//栈的顺序存储表示
typedef struct
{
    BiTNode *base;   //栈底指针
    BiTNode *top;    //栈顶指针
    int   stacksize; //当前已分配的存储空间
} SqStack;
//初始化一个带头结点的队列
void InitQueue(LinkQueue &q)
{
    q.front = q.rear = (QueuePtr)malloc(sizeof(QueueNode));
    q.front->next = NULL;
}
//入队列
void enqueue(LinkQueue &q, BiTree p)
{
    QueuePtr s;
    int first = 1;
    s = (QueuePtr)malloc(sizeof(QueueNode));
    s->e = p;
    s->next = NULL;
    q.rear->next = s;
    q.rear = s;
}
//出队列
void dequeue(LinkQueue &q, BiTree &p)
{
    char data;
    QueuePtr s;
    s = q.front->next;
    p = s->e ;
    data = p->data;
    q.front->next = s->next;
    if (q.rear == s)
        q.rear = q.front;
    free(s);
    printf("%c\t", data);
}
//判断队列是否为空
Status queueempty(LinkQueue q)
{
    if (q.front->next == NULL)
        return 1;
    return 0;
}
//按层次遍历树中结点
void Traverse(BiTree T)
{
    LinkQueue q;
    BiTree p;
    InitQueue(q);
    p = T;
    enqueue(q, p);
    while (queueempty(q) != 1)
    {
        dequeue(q, p);
        if (p->lchild != NULL)
            enqueue(q, p->lchild);
        if (p->rchild != NULL)
            enqueue(q, p->rchild);
    }
    printf("\n");
}
//建立一个空栈
void InitStack(SqStack &S)
{
    S.base = (BiTree)malloc(LIST_INT_SIZE * sizeof(BiTNode));
    if (!S.base)
        exit(OVERFLOW );//存储分配失败
    S.top = S.base;
    S.stacksize = LIST_INT_SIZE;
}
//压入栈
void Push(SqStack & S, BiTree p)
{
    if (S.top - S.base >= S.stacksize) //满栈,追加存储结构
    {
        S.base = (BiTree)realloc(S.base, (S.stacksize + LISTINCREMENT) * sizeof(BiTNode));
        if (!S.base)  exit(OVERFLOW ); //存储分配失败
        S.top = S.base + S.stacksize;
        S.stacksize += LISTINCREMENT;
    }
    *(++S.top) = *p;
}
//退出栈
bool Pop(SqStack &S, BiTree &p)
{
    if ( S.top == S.base)
    {
        printf("空栈\n");
        return false;
    }
    p = (BiTree)malloc( sizeof(BiTNode));
    *p = *S.top;
    --S.top;
    return true;
}
//判断是否是空栈
bool StackEmpty(SqStack &S)
{
    if ( S.top == S.base)
        return true;
    else
        return  false ;
}
Status InOrderTraverAndCountLeaf(BiTree &T, Status(* Vist)(TElemType e))
{
    int j = 0, count = 0;
    BiTree p;
    p = (BiTNode *)malloc( sizeof(BiTNode)); //关键一步
    p = T;
    SqStack s;
    InitStack(s);
    while (p || !StackEmpty(s))
    {
        if (p)
        {
            Push(s, p); //如果p为非空,将p压入栈
            if (!(p->lchild) && !(p->rchild))
                ++count;//记录叶子节点数
            p = p->lchild;
        }//if
        else
        {
            Pop(s, p); //如果p为空,则p退栈
            Vist(p->data);
            p = p->rchild;
        }//else
    }//while
    return  count;
}
int main()
{
    int n, ncase;
    int count;
    bool f, f1, f2, f3;
    BiTree T;
    TElemType e;
    print();
    while (scanf("%d", &n) != EOF)
    {
        f = true;
        switch (n)
        {
        case 1:
            printf("输入空格或回车表示此结点为空结束\n请输入头结点:");
            if (CreateBiTree(T))
                printf("二叉树建立成功!\n");
            else
                printf("二叉树建立失败!\n");
            break;
        case 2:
            print2();
            while (scanf("%d", &ncase) != EOF)
            {
                f1 = true;
                switch (ncase)
                {
                case 1:
                    printf("先序遍历顺序为:");
                    if (PreOrderTraverse(T, PrintElement))
                        printf("先序遍历成功!\n");
                    else
                        printf("先序遍历失败!\n");
                    break;
                case 2:
                    printf("中序遍历顺序为:");
                    if (MidOrderTraverse(T, PrintElement))
                        printf("中序遍历成功!\n");
                    else
                        printf("中序遍历失败!\n");
                    break;
                case 3:
                    printf("后序遍历顺序为:");
                    if (LastOrderTraverse(T, PrintElement))
                        printf("后序遍历成功!\n");
                    else
                        printf("后序遍历失败!\n");
                    break;
                case 0:
                    f1 = false;
                    break;
                default :
                    printf("输入错误,请重新输入!\n");
                }
                if (!f1)
                    break;
                print2();
            }
            break;
        case 3:
            print3();
            while (scanf("%d", &ncase) != EOF)
            {
                f2 = true;
                switch (ncase)
                {
                case 1:
                    InOrderTraverAndCountLeaf(T, PrintElement);
                    break;
                case 0:
                    f2 = false;
                    break;
                default :
                    printf("输入错误,请重新输入!\n");
                }
                if (!f2)
                    break;
                print3();
            }
            break;
        case 4:
            dep = 0;
            BiTreeDepth(T);
            printf("二叉树的高度为:%d\n", dep - 1);
            break;
        case 5:
            count = LeafNumTree(T);
            printf("二叉树的叶子个数为:%d\n", count);
            break;
        case 6:
            printf("按层次遍历的顺序为:\n");
            Traverse(T);
            printf("\n");
            break;
        case 0:
            f = false;
            break;
        default:
            printf("输入错误,请重新输入!\n");
            break;
        }
        if (!f)
        {
            printf("退出程序...\n");
            break;
        }
        print();
    }
    return 0;
}
最新评论
加载中...
Home Archives Categories Tags Statistics