二叉树的基本应用（PTA题型为例）

2023-12-02 12:00:58

我们根据PTA上面的题对于二叉树有一个更深的认识

7-1 二叉树的创建和递归遍历 (20 分)

从键盘接受输入扩展先序序列，以二叉链表作为存储结构，建立二叉树。并输出这棵二叉树的先序、中序和后序遍历序列。二叉树结点的data是字符类型数据, 其中#表示空格字符。

输入格式:

输入扩展先序序列。二叉树结点的data是字符类型数据, 其中#表示空格字符。

输出格式:

第一行输出先序遍历序列；第二行输出中序遍历序列；第三行输出后序遍历序列。

输入样例:

ABC##DE#G##F###

输出样例:

ABCDEGF
CBEGDFA
CGEFDBA

//解析：简单的递归实现遍历 //主要是使用扩展先序序列创建二叉树，本题不过多分析

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
    char data;
    struct node *Lchild;
    struct node *Rchild;
}BiNode, *BiTree;

//扩展先序创建二叉树
BiTree Creat_Pre_Bitree(BiTree root)
{
    char c;
    c = getchar();
    if(c=='#')
        return NULL;
    else{
        root = (BiTree)malloc(sizeof(BiNode));
        root->data = c;
        root->Lchild = Creat_Pre_Bitree(root->Lchild);
        root->Rchild = Creat_Pre_Bitree(root->Rchild);
    }
    return root;
}
//先序遍历
void PreOrder(BiTree root)
{
    if(root)
    {
        printf("%c", root->data);
        PreOrder(root->Lchild);
        PreOrder(root->Rchild);
    }
}
//中序遍历
void InOrder(BiTree root)
{
    if(root){
        InOrder(root->Lchild);
        printf("%c", root->data);
        InOrder(root->Rchild);
    }
}
//后序遍历
void PostOrder(BiTree root)
{
    if(root){
        PostOrder(root->Lchild);
        PostOrder(root->Rchild);
        printf("%c", root->data);
    }
}

int main()
{
    BiTree root = Creat_Pre_Bitree(&root);
    PreOrder(root);
    printf("\n");
    InOrder(root);
    printf("\n");
    PostOrder(root);
    printf("\n");

    return 0;
}

7-2 非递归先序和中序遍历 (20 分)

从键盘接收扩展先序序列，以二叉链表作为存储结构，建立二叉树。采取非递归方法输出这棵二叉树的先序、中序遍历序列。

输入格式:

输入扩展先序序列。二叉树结点的data是字符类型数据, 其中#表示空格字符。

输出格式:

第一行输出先序遍历序列，第二行输出中序遍历序列。

输入样例:

ABC##DE#G##F###

输出样例:

ABCDEGF
CBEGDFA

//本题主要考察非递归的先序和中序遍历，算法实现：大多数的递归问题的非递归算法中都需要用栈来消除递归先序遍历的实现： 1)访问root，root入栈并进入其左子树，进而访问左子树的root并入栈，在进入下一层左子树，...直到为空 2)栈非空则从栈顶退出上一层的结点，并进入该节点的右子树 //栈的基本操作见：

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 100
typedef struct node{
    char data;
    struct node *Lchild;
    struct node *Rchild;
}BiNode, *BiTree;

//扩展先序创建二叉树
void Creat_Pre_Bitree(BiTree *root)
{
    char c;
    c = getchar();
    if(c=='#')
        *root = NULL;
    else
    {
        *root = (BiTree)malloc(sizeof(BiNode));
        (*root)->data = c;
        Creat_Pre_Bitree(&((*root)->Lchild));
        Creat_Pre_Bitree(&((*root)->Rchild));
    }
}

/*非递归*/
//栈相关
typedef struct {
    BiTree stdata[MaxSize];
    int top;
} sqstack;
//创建栈
sqstack* Init_Stack()
{
    sqstack *s;
    s = (sqstack *)malloc(sizeof(sqstack));
    s->top = -1;
    return s;
}

//判空
int IsEmpty(sqstack *s)
{
    if(s->top==-1)
        return 1;
    else
        return 0;
}

//入栈
void Push(sqstack*s,BiTree root){

    if(s->top<MaxSize){
        s->top++;
        s->stdata[s->top] = root;
        
    }
    return;
}

//出栈
int Pop(sqstack*s,BiTree *x){
    if(IsEmpty(s))
    {
        return 0;
    }
    else
    {
        *x = s->stdata[s->top];
        s->top--;
        return 1;
    }

}
//非递归先序
void LPreOrder(BiTree root)
{
    sqstack* s;
    s = Init_Stack();
    BiTree p;
    p = root;
    while(p!=NULL||!IsEmpty(s)){
        while(p!=NULL){
            printf("%c", p->data);
            Push(s, p);
            p = p->Lchild;
        }
        if(!IsEmpty(s)){
            Pop(s,&p);
            p = p->Rchild;
        }
    }

}
//非递归中序
void LInOrder(BiTree root)
{
    sqstack* s;
    s = Init_Stack();
    BiTree p = root;
    while(p!=NULL||!IsEmpty(s)){
        while(p!=NULL){
            Push(s, p);
            p = p->Lchild;
        }
        if(!IsEmpty(s)){
            Pop(s,&p);
            printf("%c", p->data);
            p = p->Rchild;
        }
    }

}


int main()
{
    BiTree root;
    Creat_Pre_Bitree(&root);
    LPreOrder(root);
    printf("\n");
    LInOrder(root);
    printf("\n");

    return 0;
}

7-3 非递归后序遍历 (15 分)

从键盘接收扩展先序序列，以二叉链表作为存储结构，建立二叉树。采取非递归方法输出这棵二叉树的后序遍历序列。

输入格式:

输入扩展先序序列。二叉树结点的data是字符类型数据, 其中#表示空格字符。

输出格式:

输出后序遍历序列。

输入样例:

ABC##DE#G##F###

输出样例:

CGEFDBA

//后序非递归不能使用如上先、中序的遍历方法是因为，当访问完左右子树在访问结点后子树返回时无法有效的判断它到底是左子树返回的还是右子树返回的，此时我们就需要再加一个判断 /*算法实现*/ 1.当前结点进栈，并进入其左子树，重复至当前结点为空； 2.若栈非空，判断栈顶结点P的右子树是否为空，右子树是否访问过，是则退栈，访问p结点，p赋给q，p置空；不是，则进入p的右子树。

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 100
typedef struct node{
    char data;
    struct node *Lchild;
    struct node *Rchild;
}BiNode, *BiTree;

//扩展先序创建二叉树
void Creat_Pre_Bitree(BiTree *root)
{
    char c;
    c = getchar();
    if(c=='#')
        *root = NULL;
    else
    {
        *root = (BiTree)malloc(sizeof(BiNode));
        (*root)->data = c;
        Creat_Pre_Bitree(&((*root)->Lchild));
        Creat_Pre_Bitree(&((*root)->Rchild));
    }
}
/*
//递归
void PreOrder(BiTree root)
{
    if(root)
    {
        printf("%c", root->data);
        PreOrder(root->Lchild);
        PreOrder(root->Rchild);
    }
}

void InOrder(BiTree root)
{
    if(root){
        InOrder(root->Lchild);
        printf("%c", root->data);
        InOrder(root->Rchild);
    }
}

void PostOrder(BiTree root)
{
    if(root){
        PostOrder(root->Lchild);
        PostOrder(root->Rchild);
        printf("%c", root->data);
    }
}
*/

/*非递归*/
//栈相关
typedef struct {
    BiTree stdata[MaxSize];
    int top;
} sqstack;
//创建栈
sqstack* Init_Stack()
{
    sqstack *s;
    s = (sqstack *)malloc(sizeof(sqstack));
    s->top = -1;
    return s;
}

//判空
int IsEmpty(sqstack *s)
{
    if(s->top==-1)
        return 1;
    else
        return 0;
}

//入栈
void Push(sqstack*s,BiTree root){

    if(s->top<MaxSize){
        s->top++;
        s->stdata[s->top] = root;
        
    }
    return;
}

//出栈
int Pop(sqstack*s,BiTree *x){
    if(IsEmpty(s))
    {
        return 0;
    }
    else
    {
        *x = s->stdata[s->top];
        s->top--;
        return 1;
    }

}
//取栈顶元素
void Top(sqstack*s,BiTree*p)
{
    if(IsEmpty(s))
        return;
    else
        *p = s->stdata[s->top];
}
//非递归先序
void LPreOrder(BiTree root)
{
    sqstack* s;
    s = Init_Stack();
    BiTree p;
    p = root;
    while(p!=NULL||!IsEmpty(s)){
        while(p!=NULL){
            printf("%c", p->data);
            Push(s, p);
            p = p->Lchild;
        }
        if(!IsEmpty(s)){
            Pop(s,&p);
            p = p->Rchild;
        }
    }

}
//非递归中序
void LInOrder(BiTree root)
{
    sqstack* s;
    s = Init_Stack();
    BiTree p = root;
    while(p!=NULL||!IsEmpty(s)){
        while(p!=NULL){
            Push(s, p);
            p = p->Lchild;
        }
        if(!IsEmpty(s)){
            Pop(s,&p);
            printf("%c", p->data);
            p = p->Rchild;
        }
    }

}
//非递归后续遍历
void LPostOrder(BiTree root)
{
    sqstack *s;
    BiTree p, q;
    s=Init_Stack();
    p = root;
    q = NULL;
    while(p!=NULL||!IsEmpty(s))
    {
        while(p!=NULL)
        {
            Push(s, p);
            p = p->Lchild;
        }
        if(!IsEmpty(s))
        {
            Top(s, &p);
            if((p->Rchild==NULL)||(p->Rchild==q))
            {
                Pop(s, &p);
                printf("%c", p->data);
                q = p;
                p = NULL;
            }
            else
                p = p->Rchild;
        }
    }
}

int main()
{
    BiTree root;
    Creat_Pre_Bitree(&root);
    LPostOrder(root);

    return 0;
}

7-4 层次遍历 (10 分)

从键盘接收扩展先序序列，以二叉链表作为存储结构，建立二叉树。输出这棵二叉树的层次遍历序列。

输入格式:

输入扩展先序序列。二叉树结点的data是字符类型数据, 其中#表示空格字符。

输出格式:

输出层次遍历序列。

输入样例:

ABC##DE#G##F###

输出样例:

ABCDEFG

//二叉树的层次遍历　　所谓二叉树的层次遍历就是指从二叉树的第一层（root结点）开始，自上而下逐层遍历，同层从左到右逐个访问。由此我们可知这一访问过程的特点是：先访问的结点其孩子也将先访问，后访问的结点其孩子也后访问，这与队列的·操作吻合，因此我们用队列进行节点访问次序的控制 //算法实现 1.队头结点出队，并访问出队节点 2.出队结点的非空左、右孩子依次入队

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 100
typedef struct node{
    char data;
    struct node *Lchild;
    struct node *Rchild;
}BiNode, *BiTree;

//扩展先序创建二叉树
void Creat_Pre_Bitree(BiTree *root)
{
    char c;
    c = getchar();
    if(c=='#')
        *root = NULL;
    else
    {
        *root = (BiTree)malloc(sizeof(BiNode));
        (*root)->data = c;
        Creat_Pre_Bitree(&((*root)->Lchild));
        Creat_Pre_Bitree(&((*root)->Rchild));
    }
}

/*queue*/
//循环队列
typedef struct 
{
    BiTree data[MaxSize];
    int front, rear;
}Csqueue;

//置空队 初始化
Csqueue* Init_Queue()
{
    Csqueue *q;
    q = (Csqueue *)malloc(sizeof(Csqueue));
    q->front = q->rear = MaxSize - 1;
    return q;
}

//入队
int EnterQueue(Csqueue*q,BiTree x)
{
    if((q->rear+1)%MaxSize==q->front)
    {
        //printf("FULL");
        return 0;
    }
    else
    {
        q->rear = (q->rear + 1) % MaxSize;
        q->data[q->rear] = x;
        return 1; 
    }
}
//出队
int DelectQueue(Csqueue*q,BiTree*x)
{
    if(q->rear==q->front)
    {
        //printf("NUll");
        return 0;
    }
    else
    {
        q->front = (q->front + 1) % MaxSize;
        *x = q->data[q->front];
        return 1;
    }
}
//判空
int isempty(Csqueue*q)
{
    if(q->front==q->rear)
        return 1;
    return 0;
}

void levelorder(BiTree root)
{
    Csqueue *q;
    BiTree p;
    q = Init_Queue();
    EnterQueue(q, root);
    while(!isempty(q))
    {
        DelectQueue(q, &p);
        printf("%c", root->data);
        if (p->Lchild != NULL)
            EnterQueue(q, p->Lchild);
        if(p->Rchild!=NULL)
            EnterQueue(q, p->Rchild);
    }
}

int main()
{
    BiTree root;
    Creat_Pre_Bitree(&root);
    levelorder(root);
    return 0;
}

7-5 结点个数 (20 分)

从键盘接收扩展先序序列，以二叉链表作为存储结构，建立二叉树。分别统计二叉树中叶子结点、度为1的结点、度为2的结点的个数，并输出。

输入格式:

输入扩展先序序列。二叉树结点的data是字符类型数据, 其中#表示空格字符。

输出格式:

第一行依次输出叶子结点个数、度为1的结点个数、度为2的结点个数，以空格隔开。第二行连续输出叶子结点，中间不间隔。

输入样例:

ABC##DE#G##F###

输出样例:

3 2 2
CGF

//结点计算非常简单，所有node的计算我们只需全部遍历一遍即可，度数为1的只要判断左右子树中有一个存在，另一个为空即可，其他度数的结点算法一样 //这里代码我写的比较多主要是为了能够将方法尽可能的都复习到，读者可根据注释，自行修改！

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 100
typedef struct node{
    char data;
    struct node *Lchild;
    struct node *Rchild;
}BiNode, *BiTree;

//扩展先序创建二叉树
void Creat_Pre_Bitree(BiTree *root)
{
    char c;
    c = getchar();
    if(c=='#')
        *root = NULL;
    else
    {
        *root = (BiTree)malloc(sizeof(BiNode));
        (*root)->data = c;
        Creat_Pre_Bitree(&((*root)->Lchild));
        Creat_Pre_Bitree(&((*root)->Rchild));
    }
}
int count = 0;//node
int onecount = 0;//node = 1
int leafcount = 0;//node = 0

//统计二叉树中结点数目
/*  
无顺序要求，任意遍历方法均可
*/
void preOrder(BiTree root)
{
    if(root)
    {
        count++;
        preOrder(root->Lchild);
        preOrder(root->Rchild);
    }
}

//统计度数为1的结点
/*
先序（中序、后序均可）如果该节点有左（右）结点，而无右（左）结点，onecount++;
*/
void LfOrder(BiTree root)
{
    if(root)
    {
        if(((root->Lchild==NULL)&&(root->Rchild!=NULL))||((root->Rchild==NULL)&&(root->Lchild!=NULL)))
            onecount++;
        LfOrder(root->Lchild);
        LfOrder(root->Rchild);
    }
}

//统计叶子的结点数目
/*
方法一、使用全局变量
*/
void LeafOrder(BiTree root)
{
    if(root)
    {
        if((root->Lchild==NULL)&&(root->Rchild==NULL))
        {
            printf("%c", root->data);
        }
        LeafOrder(root->Lchild);
        LeafOrder(root->Rchild);
    }
}
/*
方法二、
采用递归思想，如果是空树，返回0，如果是叶子返回1，狗则，返回左右子树的叶子结点之和。
重难点：此方法必须在左右子树的叶子结点求出之后才可求出树的叶子结点数。所以，我们要选择后序遍历
*/
int leaf(BiTree root)
{
    int nl, nr;
    if(root == NULL)
        return 0;
    if((root->Lchild==NULL)&&(root->Rchild==NULL))
         return 1;
    nl = leaf(root->Lchild);
    nr = leaf(root->Rchild);
    return (nl + nr);
}



int main()
{
    BiTree root;
    Creat_Pre_Bitree(&root);
    int n = leaf(root);
    preOrder(root);
    LfOrder(root);
    printf("%d %d %d\n", n, onecount, count - onecount - n);
    LeafOrder(root);
    return 0;
}

7-6 二叉树的高度 (15 分)

从键盘接收扩展先序序列，以二叉链表作为存储结构，建立二叉树。计算二叉树的高度，并输出。

输入格式:

输入扩展先序序列。二叉树结点的data是字符类型数据, 其中#表示空格字符。

输出格式:

输出一个整数。

输入样例:

ABC##DE#G##F###

输出样例:

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 100
typedef struct node{
    char data;
    struct node *Lchild;
    struct node *Rchild;
}BiNode, *BiTree;
int count=0;
//扩展先序创建二叉树
void Creat_Pre_Bitree(BiTree *root)
{
    char c;
    c = getchar();
    if(c=='#')
        *root = NULL;
    else
    {
        *root = (BiTree)malloc(sizeof(BiNode));
        (*root)->data = c;
        Creat_Pre_Bitree(&((*root)->Lchild));
        Creat_Pre_Bitree(&((*root)->Rchild));
    }
}

/*求二叉树的高度*/
/**
 * 方法一、使用全局变量的方法，二叉树的根节点为第一层的结点，第h曾结点的孩子是h+1
 * 
*/

void Treedepth(BiTree root,int h)
{
    if(root)
    {
        if(h>count)
            count = h;
        Treedepth(root->Lchild, h + 1);
        Treedepth(root->Rchild, h + 1);

    }
}
/*方法二*/
/*
函数值返回：如果是空树，则高度为0，否则它的高度应为左、右子树高度的最大值+1，采用后序遍历

*/
int PostTreedepth(BiTree root)
{
    int hl, hr, h;
    if(root==NULL)
        return 0;
    else
    {
        hl = PostTreedepth(root->Lchild);
        hr = PostTreedepth(root->Rchild);
        h = (hl > hr ? hl : hr) + 1;
        return h;
    }
}

int main()
{
    BiTree root;
    Creat_Pre_Bitree(&root);
    Treedepth(root, 1);
    printf("%d", count);
    return 0;
}

二叉树的基本应用先到这些，其余操作以后会慢慢发布，内容有错误，希望大佬指正！！

码农公寓

输入格式:

输出格式:

输入样例:

输出样例:

输入格式:

输出格式:

输入样例:

输出样例:

输入格式:

输出格式:

输入样例:

输出样例:

输入格式:

输出格式:

输入样例:

输出样例:

输入格式:

输出格式:

输入样例:

输出样例:

输入格式:

输出格式:

输入样例:

输出样例:

相关文章