美文网首页
二叉树

二叉树

作者: 又是一只小白鼠 | 来源:发表于2020-04-27 10:38 被阅读0次

    结构体

    #include "bitree.h"
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100

typedef struct Node
{
    int data;
    struct Node *pleft;
    struct Node *pright;
}Node, *pNode;

int top =-1;//栈顶
int front = 0, rear = 0;//初始化队头和队尾指针开始时都为0

    创建二叉树

    pNode CreateBiNode(int data) {
    pNode p = (Node *) malloc(sizeof(Node));
    p->data = data;
    p->pleft = p->pright = NULL;
    return p;
}

pNode AddNode(int data, pNode pnode) {
    if (pnode == NULL) {
        return CreateBiNode(data);
    }
    if (data == pnode->data) {
        return pnode;
    }
    
    
    if (data < pnode->data) {
        if (pnode->pleft == NULL) {
            pnode->pleft = CreateBiNode(data);
            return pnode->pleft;
        }
        else {
            return AddNode(data, pnode->pleft);
        }
    }
    else {
        if (pnode->pright == NULL) {
            pnode->pright = CreateBiNode(data);
            return pnode->pright;
        }
        else {
            return AddNode(data, pnode->pright);
        }
    }
}

    递归遍历

    void PreOrderTraverse(struct Node *pnode)//先序
{
    if(pnode != NULL)
    {
        printf("%d\n", pnode->data);
        PreOrderTraverse(pnode->pleft);
        PreOrderTraverse(pnode->pright);
    }
}
//中序
void INOrderTraverse(pNode pnode) {
    if (pnode != NULL) {
        INOrderTraverse(pnode->pleft);
        printf("%d\n", pnode->data);
        INOrderTraverse(pnode->pright);
    }
}
//后序
void PostOrderTraverse(pNode pnode) {
    if (pnode) {
        PostOrderTraverse(pnode->pleft);
        PostOrderTraverse(pnode->pright);
        printf("%d\n", pnode->data);
    }
}

    栈操作

    //入栈
void pushbitree(pNode *stack, pNode pnode) {
    stack[++top] = pnode;
}

//出栈
void popbitree(pNode *stack) {
    if (top == -1) {
        return;
    }
    top --;
}

//获取栈顶元素
pNode getstacktop(pNode *stack) {
    return stack[top];
}

    非递归遍历

    //非递归实现先序
void StackPreOrderTraverse(pNode pnode) {
    pNode stack[MAXSIZE];//顺序栈
    pNode p;//临时指针
    pushbitree(stack, pnode);
    while (top != -1) {
        p = getstacktop(stack);
        popbitree(stack);
        while (p) {
            printf("%d ", p->data);
            if (p->pright) {
                pushbitree(stack, p->pright);//右子树入栈
            }
            p = p->pleft;//处理左子树直到叶子结点
        }
    }
    printf("\n");
}
//非递归中序
void StackINOrderTraverse(pNode pnode) {
    pNode stack[MAXSIZE];
    pNode p;//临时指针
    pushbitree(stack, pnode);
    while (top != -1) {
        while ((p=getstacktop(stack)) && p) {
            pushbitree(stack, p->pleft);//将该结点的左孩子进栈，如果没有左孩子，NULL进栈
        }
        popbitree(stack);//跳出循环，栈顶元素肯定为NULL，将NULL弹栈
        if (top != -1) {
            p = getstacktop(stack);
            popbitree(stack);
            printf("%d ", p->data);
            pushbitree(stack, p->pright);
        }
    }
    printf("\n");
}
//非递归中序
void StackINOrderTraverse2(pNode pnode) {
    pNode stack[MAXSIZE];
    pNode p;
    p = pnode;
    //当p为NULL或者栈为空时，表明树遍历完成
    while (p || top != -1) {
        //如果p不为NULL，将其压栈并遍历其左子树
        if (p) {
            pushbitree(stack, p);
            p = p->pleft;
        }
        //如果p==NULL，表明左子树遍历完成，需要遍历上一层结点的右子树
        else {
            p = getstacktop(stack);
            popbitree(stack);
            printf("%d ", p->data);
            p = p->pright;
        }
    }
    printf("\n");
}
//非递归后序
void StackPostOrderTraverse(pNode pnode) {
    pNode stack[MAXSIZE], stack2[MAXSIZE];
    pNode p;
    int top2 = -1;
    p = pnode;
    pushbitree(stack, p);
    while (top != -1) {
        p = getstacktop(stack);
        popbitree(stack);
        stack2[++top2] = p;
        if (p->pleft != NULL) {
            pushbitree(stack, p->pleft);
        }
        if (p->pright != NULL) {
            pushbitree(stack, p->pright);
        }
    }
    while (top2 != -1) {
        p = stack2[top2--];
        printf("%d ", p->data);
    }
    printf("\n");
}

    层次遍历

    void EnQueuebitree(pNode *a, pNode pnode) {
    a[++rear] = pnode;
}

pNode DeQueuebitree(pNode *a) {
    return a[++front];
}

void QueueLevelTraverse(pNode pnode) {
    pNode a[MAXSIZE];//顺序队
    pNode p;//临时指针p
    EnQueuebitree(a, pnode);
    while (front != rear) {
        p = DeQueuebitree(a);
        printf("%d ", p->data);
        if (p->pleft != NULL) {
            EnQueuebitree(a, p->pleft);
        }
        if (p->pright != NULL) {
            EnQueuebitree(a, p->pright);
        }
    }
    printf("\n");
}

    完整代码

    //
//  bitree.c
//  Ccode
//
//  Created by on 2020/4/22.
//  Copyright © 2020. All rights reserved.
//

#include "bitree.h"
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100

typedef struct Node
{
    int data;
    struct Node *pleft;
    struct Node *pright;
}Node, *pNode;

int top =-1;//栈顶
int front = 0, rear = 0;//初始化队头和队尾指针开始时都为0

pNode CreateBiNode(int data) {
    pNode p = (Node *) malloc(sizeof(Node));
    p->data = data;
    p->pleft = p->pright = NULL;
    return p;
}

pNode AddNode(int data, pNode pnode) {
    if (pnode == NULL) {
        return CreateBiNode(data);
    }
    if (data == pnode->data) {
        return pnode;
    }
    
    if (data < pnode->data) {
        if (pnode->pleft == NULL) {
            pnode->pleft = CreateBiNode(data);
            return pnode->pleft;
        }
        else {
            return AddNode(data, pnode->pleft);
        }
    }
    else {
        if (pnode->pright == NULL) {
            pnode->pright = CreateBiNode(data);
            return pnode->pright;
        }
        else {
            return AddNode(data, pnode->pright);
        }
    }
}

void PreOrderTraverse(struct Node *pnode)//先序
{
    if(pnode != NULL)
    {
        printf("%d\n", pnode->data);
        PreOrderTraverse(pnode->pleft);
        PreOrderTraverse(pnode->pright);
    }
}

//入栈
void pushbitree(pNode *stack, pNode pnode) {
    stack[++top] = pnode;
}

//出栈
void popbitree(pNode *stack) {
    if (top == -1) {
        return;
    }
    top --;
}

//获取栈顶元素
pNode getstacktop(pNode *stack) {
    return stack[top];
}


//非递归实现先序
void StackPreOrderTraverse(pNode pnode) {
    pNode stack[MAXSIZE];//顺序栈
    pNode p;//临时指针
    pushbitree(stack, pnode);
    while (top != -1) {
        p = getstacktop(stack);
        popbitree(stack);
        while (p) {
            printf("%d ", p->data);
            if (p->pright) {
                pushbitree(stack, p->pright);//右子树入栈
            }
            p = p->pleft;//处理左子树直到叶子结点
        }
    }
    printf("\n");
}


//中序
void INOrderTraverse(pNode pnode) {
    if (pnode != NULL) {
        INOrderTraverse(pnode->pleft);
        printf("%d\n", pnode->data);
        INOrderTraverse(pnode->pright);
    }
}

//非递归中序
void StackINOrderTraverse(pNode pnode) {
    pNode stack[MAXSIZE];
    pNode p;//临时指针
    pushbitree(stack, pnode);
    while (top != -1) {
        while ((p=getstacktop(stack)) && p) {
            pushbitree(stack, p->pleft);//将该结点的左孩子进栈，如果没有左孩子，NULL进栈
        }
        popbitree(stack);//跳出循环，栈顶元素肯定为NULL，将NULL弹栈
        if (top != -1) {
            p = getstacktop(stack);
            popbitree(stack);
            printf("%d ", p->data);
            pushbitree(stack, p->pright);
        }
    }
    printf("\n");
}

//非递归中序
void StackINOrderTraverse2(pNode pnode) {
    pNode stack[MAXSIZE];
    pNode p;
    p = pnode;
    //当p为NULL或者栈为空时，表明树遍历完成
    while (p || top != -1) {
        //如果p不为NULL，将其压栈并遍历其左子树
        if (p) {
            pushbitree(stack, p);
            p = p->pleft;
        }
        //如果p==NULL，表明左子树遍历完成，需要遍历上一层结点的右子树
        else {
            p = getstacktop(stack);
            popbitree(stack);
            printf("%d ", p->data);
            p = p->pright;
        }
    }
    printf("\n");
}


//后序
void PostOrderTraverse(pNode pnode) {
    if (pnode) {
        PostOrderTraverse(pnode->pleft);
        PostOrderTraverse(pnode->pright);
        printf("%d\n", pnode->data);
    }
}

//非递归后序
void StackPostOrderTraverse(pNode pnode) {
    pNode stack[MAXSIZE], stack2[MAXSIZE];
    pNode p;
    int top2 = -1;
    p = pnode;
    pushbitree(stack, p);
    while (top != -1) {
        p = getstacktop(stack);
        popbitree(stack);
        stack2[++top2] = p;
        if (p->pleft != NULL) {
            pushbitree(stack, p->pleft);
        }
        if (p->pright != NULL) {
            pushbitree(stack, p->pright);
        }
    }
    while (top2 != -1) {
        p = stack2[top2--];
        printf("%d ", p->data);
    }
    printf("\n");
}

void EnQueuebitree(pNode *a, pNode pnode) {
    a[++rear] = pnode;
}

pNode DeQueuebitree(pNode *a) {
    return a[++front];
}

void QueueLevelTraverse(pNode pnode) {
    pNode a[MAXSIZE];//顺序队
    pNode p;//临时指针p
    EnQueuebitree(a, pnode);
    while (front != rear) {
        p = DeQueuebitree(a);
        printf("%d ", p->data);
        if (p->pleft != NULL) {
            EnQueuebitree(a, p->pleft);
        }
        if (p->pright != NULL) {
            EnQueuebitree(a, p->pright);
        }
    }
    printf("\n");
}

int Treeheight(struct Node *pnode)
{
    int LD, RD;
    if(pnode == NULL)
    {
        return 0;
    }
    else
    {
        LD = Treeheight(pnode->pleft);
        RD = Treeheight(pnode->pright);
        return (LD >= RD? LD:RD) + 1;
    }
}

void testbitree() {
    int newvalue = 0;
    struct Node *proot = NULL;
    char answer = 'n';
    do
    {
        printf("Enter the node value:\n");
        scanf("%d", &newvalue);
        if(proot == NULL)
        {
            proot = CreateBiNode(newvalue);
        }
        else
        {
            AddNode(newvalue, proot);
        }
        printf("\nDo you want to enter another (y or n)? ");
        scanf(" %c", &answer);
    } while(tolower(answer) == 'y');

    PreOrderTraverse(proot);
    printf("\nThe height of tree is %d!\n", Treeheight(proot));
    StackPreOrderTraverse(proot);
    
    printf("=====================\n");
    INOrderTraverse(proot);
    StackINOrderTraverse(proot);
    StackINOrderTraverse2(proot);
    printf("-------PostOrderTraverse-------\n");
    PostOrderTraverse(proot);
    StackPostOrderTraverse(proot);
    
    printf("======QueueLevelTraverse======\n");
    QueueLevelTraverse(proot);
}

    相关文章

      网友评论

          本文标题：二叉树

          本文链接：https://www.haomeiwen.com/subject/aozewhtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|二叉树|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！