二叉树

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

数据结构与算法-二叉树02
二叉树
二叉树基础操作
树与二叉树
二叉树的宽度优先搜索（层次遍历，BFS）
剑指 offer：39、平衡二叉树
Algorithm小白入门 -- 二叉树
14-树&二叉树&真二叉树&满二叉树
二叉树的应用
12.树Tree（2）

结构体

#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);
}