二叉树具体实现-C语言

知识回顾：

树

树是n（n>=0）个结点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足：

1、有且仅有一个特定的称为根的结点。

2、当n>1时，其余结点可分为m（m>0）个互不相交的有限集T~1~，T~2~，...，T~n~。其中每个集合本身又是一棵树，并且称为根的子树。

树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

1、树的根结点没有前驱，除根结点外的所有结点具有且只有一个前驱。

2、树中所有结点可以有零个或多个后继。

二叉树

二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

与树相似，二叉树也以递归的形式定义，二叉树是n（n>=0）个结点的有限集合：

1、或者为空二叉树，即n=0。

2、或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成，左子树和右子树又分别是一棵二叉树。

二叉树可用顺序存储和链式存储实现。

树结点数据结构

树中的任何一个结点都是一个结构体，需要使用malloc（）函数申请空间

typedef char BiElemType;
typedef struct BiTNode{
    BiElemType c; //对应树中存储的char型数据
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

二叉树的层次建树

为了提高代码的编写效率，将结构体类型的声明放入function.h头文件，该头文件在main.cpp文件内进行声明，在代码验证的步骤中，使用单步调试和断点进行验证。

function.h

//
// Created by caiju on 2024/6/10.
//

#ifndef UNTITLED2_FUNCTION_H
#define UNTITLED2_FUNCTION_H
#include <stdio.h>
#include <stdlib.h>

#endif //UNTITLED2_FUNCTION_H

typedef char BiElemType;
typedef struct BiTNode{
    BiElemType c;
    struct BiTNode *lchild;
    struct BiNode *rchild;
}BiTNode,*BiTree;

//tag结构体为辅助队列使用
typedef struct tag{
    BiTree p; //树中某个结点的地址值
    struct tag *next;
}tag_t,*ptag_t;

main.cpp

#include "function.h"

int main(){
    BiTree pnew; //用于指向新申请的树结点
    char c;
    BiTree tree=NULL; //树根
    //phead为队列头，ptail为队列尾，listpnew为每次入队的新结点，pcur为当前的父结点
    ptag_t phead=NULL,ptail=NULL,listpnew=NULL,pcur=NULL;
    //输入内容为abcdefghij
    while(scanf("%c",&c))
    {
        if(c=='\n')
        {
            break;
        }
        //calloc()函数申请结点空间，并对空间进行初始化，赋值为0
        pnew= (BiTree)calloc(1,sizeof(BiTNode));
        //将输出的数据进行存储
        pnew->c=c;
        //队列结点申请空间
        listpnew=(ptag_t)calloc(1,sizeof(tag_t));
        listpnew->p=pnew;
        if(NULL==tree)
        {
            tree=pnew;
            phead=listpnew; //队列头
            ptail=listpnew; //队列尾
            pcur=listpnew;
            continue;
        } else
        {
            ptail->pnext=listpnew; //新结点尾插法插入链表
            ptail=listpnew; //ptail（队尾指针）指向队列最后一个元素
        }//pcur指针始终指向要插入的结点的位置
        if(NULL==pcur->p->lchild) //如何把新结点放入树
        {
            pcur->p->lchild=pnew; //将新结点放入插入结点的左孩子结点
        }else if(NULL==pcur->p->rchild)
        {
            pcur->p->rchild=pnew;//将新结点放入插入结点的右孩子结点
            pcur=pcur->pnext;
        }
    }
    return 0;
};

在上面的代码里，读者需要注意一个问题，比如在continue处打上断点，输入ab，在内存视图观察pcur->next指针的变化情况，数据a进入队列成为树根后，代码处理数据b，在执行ptail->next=listpnew代码后，会观察到ptail->next指针和pcur->next指针指向同一个内存地址，但是在代码中，并没有对pcur->next指针进行赋值，通过gpt询问后，得出两个指针共享同一个结点时，修改某个指针的指向会导致另一个指针的指向也发生变化（存疑）

再次执行代码，在终端界面输入abcdefghij，在return 0处添加断点，进行调试，如果观察到左右子树跟下图的情况一直，则代表层次建树成功，否则读者需要注意自己的代码逻辑和语法问题。

二叉树的前序中序后序遍历

前序遍历：打印自身，随后打印左子树，最后打印右子树

中序遍历：打印左子树，随后打印自身，最后打印右子树

后序遍历：打印左子树，随后打印右子树，最后打印自身

function.h

//
// Created by caiju on 2024/6/10.
//

#ifndef UNTITLED2_FUNCTION_H
#define UNTITLED2_FUNCTION_H
#include <stdio.h>
#include <stdlib.h>

#endif //UNTITLED2_FUNCTION_H

typedef char BiElemType;
typedef struct BiTNode{
    BiElemType c;
    struct BiTNode *lchild;
    struct BiNode *rchild;
}BiTNode,*BiTree;

//tag结构体为辅助队列使用
typedef struct tag{
    BiTree p; //树中某个结点的地址值
    struct tag *next;
}tag_t,*ptag_t;

main.cpp

#include "function.h"

//递归实现
//前序遍历（深度优先遍历）,输入为abcdefghij，理想输出结果为abdhiejcfg
void PreOrder(BiTree p){
    if(NULL != p)
    {
        putchar(p->c); //等价于printf("%c",c)或visit函数
        PreOrder(p->lchild);
        PreOrder(p->rchild);
    }
}

//中序遍历，理想输出为hdibjeafcg
void InOrder(BiTree p){
    if(NULL != p)
    {
        InOrder(p->lchild);
        putchar(p->c);
        InOrder(p->rchild);
    }
}

//后序遍历，理想输出为hidjebfgca
void PostOrder(BiTree p) {
    if (NULL != p) {
        PostOrder(p->lchild);
        PostOrder(p->rchild);
        putchar(p->c);
    }
}
int main(){
    BiTree pnew; //用于指向新申请的树结点
    char c;
    BiTree tree=NULL; //树根
    //phead为队列头，ptail为队列尾，listpnew为每次入队的新结点，pcur为当前的父结点
    ptag_t phead=NULL,ptail=NULL,listpnew=NULL,pcur=NULL;
    //输入内容为abcdefghij
    while(scanf("%c",&c))
    {
        if(c=='\n')
        {
            break;
        }
        //calloc()函数申请结点空间，并对空间进行初始化，赋值为0
        pnew= (BiTree)calloc(1,sizeof(BiTNode));
        //将输出的数据进行存储
        pnew->c=c;
        //队列结点申请空间
        listpnew=(ptag_t)calloc(1,sizeof(tag_t));
        listpnew->p=pnew;
        if(NULL==tree)
        {
            tree=pnew;
            phead=listpnew; //队列头
            ptail=listpnew; //队列尾
            pcur=listpnew;
            continue;
        } else
        {
            ptail->pnext=listpnew; //新结点尾插法插入链表
            ptail=listpnew; //ptail（队尾指针）指向队列最后一个元素
        }//pcur指针始终指向要插入的结点的位置
        if(NULL==pcur->p->lchild) //如何把新结点放入树
        {
            pcur->p->lchild=pnew; //将新结点放入插入结点的左孩子结点
        }else if(NULL==pcur->p->rchild)
        {
            pcur->p->rchild=pnew;//将新结点放入插入结点的右孩子结点
            pcur=pcur->pnext;
        }
    }
    printf("--------PreOrder----------\n");
    PreOrder(tree);
    printf("\n--------InOrder------------\n");
    InOrder(tree);
    printf("\n--------PostOrder------------\n");
    PostOrder(tree);
    return 0;
};

二叉树层序遍历

二叉树的层序遍历（也称为广度优先遍历）是一种逐层访问树中结点的遍历方法，从根结点开始，依次访问每一层的结点。常用的方法是使用队列（queue）来辅助实现

function.h

//
// Created by caiju on 2024/6/10.
//

#ifndef UNTITLED2_FUNCTION_H
#define UNTITLED2_FUNCTION_H
#include <stdio.h>
#include <stdlib.h>

#endif //UNTITLED2_FUNCTION_H

typedef char BiElemType;
typedef struct BiTNode{
    BiElemType c;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

//tag结构体为辅助队列使用
typedef struct tag{
    BiTree p; //树中某个结点的地址值
    struct tag *pnext;
}tag_t,*ptag_t;

//队列相关的数据结构
typedef BiTree ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct {
    LinkNode *front,*rear;
}LinkQueue;

void InitQueue(LinkQueue &Q);
bool IsEmpty(LinkQueue Q);
void EnQueue(LinkQueue &Q,ElemType x);
bool DeQueue(LinkQueue &Q,ElemType &x);

queue.cpp

//
// Created by caiju on 2024/6/12.
//
#include "function.h"

void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); //头和尾指向同一个结点
    Q.front->next=NULL; //头结点的next指针指向NULL
}

bool IsEmpty(LinkQueue Q){
    if(Q.front==Q.rear)
    {
        return true;
    } else
    {
        return false;
    }
}

//入队，尾插法
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s= (LinkNode*)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s; //rear指针始终指向尾部
    Q.rear=s;
}

//出队，头删法
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==Q.rear)
    {
        return false;
    }
    LinkNode *p=Q.front->next; //头结点为空，头结点next指针指向的结点才是第一个结点
    x=p->data;
    Q.front->next=p->next; //断链
    if(p==Q.rear) //若删除的是最后一个结点
    {
        Q.rear=Q.front; //队列重置为空
    }
    free(p);
    return true;
}

main.cpp（其余部分跟上面的相同，区别是增加了LevelOrder函数）

#include "function.h"

//递归实现
//前序遍历（深度优先遍历）,输入为abcdefghij，理想输出结果为abdhiejcfg
void PreOrder(BiTree p){
    if(NULL != p)
    {
        putchar(p->c); //等价于printf("%c",c)或visit函数
        PreOrder(p->lchild);
        PreOrder(p->rchild);
    }
}

//中序遍历，理想输出为hdibjeafcg
void InOrder(BiTree p){
    if(NULL != p)
    {
        InOrder(p->lchild);
        putchar(p->c);
        InOrder(p->rchild);
    }
}

//后序遍历，理想输出为hidjebfgca
void PostOrder(BiTree p) {
    if (NULL != p) {
        PostOrder(p->lchild);
        PostOrder(p->rchild);
        putchar(p->c);
    }
}

//层次遍历（层序遍历、广度优先遍历）
void LevelOrder(BiTree T){
    LinkQueue Q; //辅助队列
    InitQueue(Q); //初始化队列
    BiTree p;
    EnQueue(Q,T); //树根入队
    while(!IsEmpty(Q))
    {
        DeQueue(Q,p);
        putchar(p->c);
        if(p->lchild!=NULL) //入队左孩子
        {
            EnQueue(Q,p->lchild);
        }
        if(p->rchild!=NULL)
        {
            EnQueue(Q,p->rchild); //入队右孩子
        }
    }
}
int main(){
    BiTree pnew; //用于指向新申请的树结点
    char c;
    BiTree tree=NULL; //树根
    //phead为队列头，ptail为队列尾，listpnew为每次入队的新结点，pcur为当前的父结点
    ptag_t phead=NULL,ptail=NULL,listpnew=NULL,pcur=NULL;
    //输入内容为abcdefghij
    while(scanf("%c",&c))
    {
        if(c=='\n')
        {
            break;
        }
        //calloc()函数申请结点空间，并对空间进行初始化，赋值为0
        pnew= (BiTree)calloc(1,sizeof(BiTNode));
        //将输出的数据进行存储
        pnew->c=c;
        //队列结点申请空间
        listpnew=(ptag_t)calloc(1,sizeof(tag_t));
        listpnew->p=pnew;
        if(NULL==tree)
        {
            tree=pnew;
            phead=listpnew; //队列头
            ptail=listpnew; //队列尾
            pcur=listpnew;
            continue;
        } else
        {
            ptail->pnext=listpnew; //新结点尾插法插入链表
            ptail=listpnew; //ptail（队尾指针）指向队列最后一个元素
        }//pcur指针始终指向要插入的结点的位置
        if(NULL==pcur->p->lchild) //如何把新结点放入树
        {
            pcur->p->lchild=pnew; //将新结点放入插入结点的左孩子结点
        }else if(NULL==pcur->p->rchild)
        {
            pcur->p->rchild=pnew;//将新结点放入插入结点的右孩子结点
            pcur=pcur->pnext;
        }
    }
    printf("--------PreOrder----------\n");
    PreOrder(tree);
    printf("\n--------InOrder------------\n");
    InOrder(tree);
    printf("\n--------PostOrder------------\n");
    PostOrder(tree);
    printf("\n--------LevelOrder-----------\n");
    LevelOrder(tree);
    printf("\n");
    return 0;
};

共三道练习题，给出第一道题目答案，剩下两道题目都可在文章中找到答案，供读者练习

题目一

二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一颗二叉树T，采用二叉链表存储，结点结构如下：

其中叶节点的weight域保存该结点的非负权值，设root为指向T的根节点的指针，请设计求T的WPL算法，要求如下：

1）给出算法的基本设计思想

2）使用C或C++语言，给出二叉树结点的数据类型定义

3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释

答：

提示：带权路径长度是权值与从根节点到叶子节点路径长度（即深度）的乘积。可以使用先序遍历或层次遍历解决问题。

算法基本思想1：基于先序递归遍历的算法思想是用一个static变量记录wpl，把每个结点的深度作为递归函数的一个参数传递。

算法的步骤如下：

①若该结点是叶子结点，那么变量wpl加上该结点的深度与权值之积

②若该结点非叶子结点，那么若左子树不为空，对左子树调用递归算法，若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加一

③最后返回计算出来的变量wpl的值

算法的基本思想2：基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前层数，当遍历到叶子结点时，累计wpl；当遍历到非叶子结点时将该结点的子树加入队列；当某个结点为该层的最后一个结点时，层数加一；队列空时遍历结束，返回wpl

二叉树结点的数据类型定义如下：

typedef int BiElemType;
typedef struct BiTNode{
    BiElemType weight;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

代码实现如下：

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

typedef int BiElemType;

// 定义二叉树节点结构
typedef struct BiTNode {
    BiElemType weight; // 结点的权值
    struct BiTNode *lchild; // 左孩子指针
    struct BiTNode *rchild; // 右孩子指针
} BiTNode, *BiTree;

typedef struct tag {
    BiTree p; // 树的某一个结点的地址值
    struct tag *pnext; // 指向下一个 tag 结构
} tag_t, *ptag_t;

// 递归前序遍历计算带权路径长度的函数
int wp1_PreOrder(BiTree root, int deep) {
    // 静态局部变量 wp1，初始值为 0，只初始化一次
    static int wp1 = 0;

    // 如果当前节点是叶子节点，累加 wp1
    if (root->lchild == NULL && root->rchild == NULL)
        wp1 += deep * root->weight;

    // 递归遍历左子树
    if (root->lchild != NULL)
        wp1_PreOrder(root->lchild, deep + 1);

    // 递归遍历右子树
    if (root->rchild != NULL)
        wp1_PreOrder(root->rchild, deep + 1);

    return wp1;

}

// 计算带权路径长度的函数
int WPL(BiTree root) {
    return wp1_PreOrder(root, 0);
}

题目二

读取字符串abcdefghij，然后层次建树建立一棵二叉树，然后前序遍历输出abdhiejcfg

题目三

读取字符串abcdefghij，然后层次建树建立一棵二叉树，然后中序遍历输出 hdibjeafcg，后序遍历输出 hidjebfgca，层序遍历输出abcdefghij