ADT树——C语言实现

数据结构——树

PS:新人博客，如有错误欢迎在评论区指正

前置知识：递归，结构体

基础概念

根节点只存在一个
节点拥有子树的个数为节点的度
除了根节点一外的，都是子树
- 子树个数没有限制，子树之间互不相交
结点间的亲缘关系：如图示
从根节点开始向下数，树的层数即是树的深度
森林：互补相交的树

树的存储结构

存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理，取决于基于该存储结构的运算是否合适、方便，时间复杂度好不好等——《大话数据结构》

双亲表示法

采用数组来存储：顺序存储各个节点，给各节点附加记录其 parent 节点位置
每个节点中，包含该节点的数据和该节点的 parent 节点的位置
除了知道自己是谁，自己存放什么内容，还知道自己的 parent 在哪

#define MAX_TREE_SIZE 100 //树的最大尺寸
typedef int TElemType;    //树节点的数据类型
typedef struct PTNode{	  //节点结构
	TElemType data;		  //节点数据
	int parent;			  //parent 位置
}PTNode;
typedef struct{
	PTNode nodes[MAX_TREE_SIZE];//节点数组
	int r,n;			  //根的位置和节点数
}PTree;

易于找到 parent 节点，但在寻找节点的 child 时，需要遍历整个树

孩子表示法

每个节点指向一颗子树的根节点——多重链式表示法

实现方法一

为给一个节点设置最大值

实现方法二

对比于方法一无法确定节点的度，我们可以设置一个变量来记录节点的度，进而设计适当的个数，减少空指针浪费空间

克服空间浪费，但节点的链表结构不同，还要维护节点度的数值，会产生时间消耗（空间换时间，时间换空间）

二叉树

二叉树基础概念

在没有指定规则的情况下，其他形式树的创建比较困难，所以一般创建二叉树来学习树的数据类型
每个根节点最多只有两个子树
左子树和右子树是有区别的

二叉树与非常经典的二分查找算法有一些关联，我们在将一组数据输入时，可以依照二分查找（大小关系）输入树中，并且在查找的时候也比较快捷（\(log_2N\))
- 但很明显可以发现，如果所选取的根节点不好，就会导致树长得比较奇葩，甚至长成斜树
斜树：左斜树 and 右斜树，每层都只有一个节点，所有节点都全是左子树（右子树）
满二叉树：全部节点都存在的二叉树
完全二叉树：其序号按照满二叉树来标注，看图可知
- 满二叉树一定是完全二叉树，但反过来不一定

二叉树存储结构

可以类比前基本树的存储结构

二叉树的遍历

从根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个节点被访问且仅被访问一次

前序遍历：先访问根节点，然后遍历左节点，再遍历右节点：ABDGHCEIF

1. 先从根节点进入，访问A
2. 再进一步访问A的左子树B
3. 依次向左下访问：D->G，由于G没有子树，所以返回节点D，访问右子树H
PS：这里我们是使用递归来实现的二叉树，所以会有返回操作，看到完整代码即可理解
4. D节点的树已经访问完，返回到B节点，B节点没有右子树，返回A节点
5. 右边的访问类比左边即可，规则一样

代码实现

void PreOrdeTraverse(BiTree T)
{
    if (T)		//树不空则继续访问
    {
        printf(T->data);
        PreOrdeTraverse(T->lchild);//使用递归形式实现遍历，所以需要下层左树访问完全，才能返回到节点，访问右树
        PreOrdeTraverse(T->rchild);
    }
}

中序遍历：从根节点开始（并不访问根节点），先遍历节点左树，再访问根节点，后访问右树：GDHBAEICF

先看代码，更好的理解中序遍历

void InOrdeTraverse(BiTree T)
{
    if (T)
    {
        InOrdeTraverse(T->lchild);
        printf(T->data);
        InOrdeTraverse(T->rchild);
    }
}

1. 依旧是从A节点进入，但看程序，我们会优先进行`InOrdeTraverse(T->lchild)`，访问左子树
2. B->D->G
3. 当到达G节点时，没有左子树了，我们便输出G的内容printf(T->date)；G节点无右子树，所以本节点递归结束，回到D节点printf(T->data)，接着访问H节点，同样H节点无左右子树，便printf(T->data)
4. 其他同样如此理解

后序遍历：从根节点进入，先访问左子树，再访问右子树，最后放过根节点

类比前两种遍历方式，不多赘述

void PosOrdeTraverse(BiTree T)
{
    if (T)
    {
        PosOrdeTraverse(T->lchild);
        PosOrdeTraverse(T->rchild);
        visit(T->data);
    }
}

层序遍历：按照层级关系对树进行遍历；使用队列实现：ABCDEFGHI

#define maxsize 30 //队列最大长度
//访问二叉树结点操作
void visit(char c)
{
    printf("%c", c);
}
//层序遍历队列结构
typedef struct
{
    BiTree data[maxsize];
    int front, rear; //前后
} SqQueue;
//初始化队列
void InitQueue(SqQueue *Q)
{
    Q->front = Q->rear = 0;
}
//入队
void EnQueue(SqQueue *Q, BiTree P)
{
    if ((Q->rear + 1) % maxsize == Q->front)
    {
        printf("this Queue is full");
    }
    else
    {
        Q->data[Q->rear] = P;
        Q->rear = (Q->rear + 1) % maxsize;
    }
}
//出队
void DeQueue(SqQueue *Q, BiTree *P)
{
    if (Q->front == Q->rear)
    {
        printf("this queue is full");
    }
    else
    {
        *P = Q->data[Q->front];
        Q->front = (Q->front + 1) % maxsize;
    }
}
int emptyQueue(SqQueue Q)
{
    if (Q.front == Q.rear)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
//层序遍历二叉树
void LevelOrder(BiTree T)
{
    SqQueue Q;
    InitQueue(&Q);
    BiTree P;
    EnQueue(&Q, T);
    while (!emptyQueue(Q))
    {
        DeQueue(&Q, &P);
        visit(P->data);
        if (P->lchild != NULL)
        {
            EnQueue(&Q, P->lchild);
        }
        if (P->rchild != NULL)
        {
            EnQueue(&Q, P->rchild);
        }
    }
}

总的代码汇集

#include 
#include 
//使用递归实现树
#define maxsize 30
typedef struct BiTNode
{
    char data;                       //结点的数据域
    struct BiTNode *lchild, *rchild; //指向左孩子和右孩子
} BiTNode, *BiTree;
//访问二叉树结点操作
void visit(char c)
{
    printf("%c", c);
}
//层序遍历队列结构
typedef struct
{
    BiTree data[maxsize];
    int front, rear; //前后
} SqQueue;
//初始化队列
void InitQueue(SqQueue *Q)
{
    Q->front = Q->rear = 0;
}
//入队
void EnQueue(SqQueue *Q, BiTree P)
{
    if ((Q->rear + 1) % maxsize == Q->front)
    {
        printf("this Queue is full");
    }
    else
    {
        Q->data[Q->rear] = P;
        Q->rear = (Q->rear + 1) % maxsize;
    }
}
//出队
void DeQueue(SqQueue *Q, BiTree *P)
{
    if (Q->front == Q->rear)
    {
        printf("this queue is full");
    }
    else
    {
        *P = Q->data[Q->front];
        Q->front = (Q->front + 1) % maxsize;
    }
}
int emptyQueue(SqQueue Q)
{
    if (Q.front == Q.rear)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
//层序遍历二叉树
void LevelOrder(BiTree T)
{
    SqQueue Q;
    InitQueue(&Q);
    BiTree P;
    EnQueue(&Q, T);
    while (!emptyQueue(Q))
    {
        DeQueue(&Q, &P);
        visit(P->data);
        if (P->lchild != NULL)
        {
            EnQueue(&Q, P->lchild);
        }
        if (P->rchild != NULL)
        {
            EnQueue(&Q, P->rchild);
        }
    }
}

//先序序列创建一颗二叉树
void CreatBiTree(BiTree *T)
{
    char c;
    scanf("%c", &c);
    if (c == '#')
        *T = NULL;
    else
    {
        *T = (BiTNode *)malloc(sizeof(BiTNode)); //给结点申请一个空间
        (*T)->data = c;
        CreatBiTree(&((*T)->lchild)); //创建左子树
        CreatBiTree(&((*T)->rchild)); //创建右子树
    }
}

//先序遍历二叉树
void PreOrdeTraverse(BiTree T)
{
    if (T)
    {
        visit(T->data);
        PreOrdeTraverse(T->lchild);
        PreOrdeTraverse(T->rchild);
    }
}
//中序遍历二叉树
void InOrdeTraverse(BiTree T)
{
    if (T)
    {
        InOrdeTraverse(T->lchild);
        visit(T->data);
        InOrdeTraverse(T->rchild);
    }
}
//后序遍历二叉树
void PosOrdeTraverse(BiTree T)
{
    if (T)
    {
        PosOrdeTraverse(T->lchild);
        PosOrdeTraverse(T->rchild);
        visit(T->data);
    }
}
//查找字母D在第几层
void Search(BiTree T, int leavel)
{
    if (T)
    {
        if (T->data == 'D')
        {
            printf("D在第%d层！\n", leavel);
        }
        Search(T->lchild, leavel + 1);
        Search(T->rchild, leavel + 1);
    }
}
//计算节点个数
int sumNode(BiTree T, int *count)
{
    if (T)
    {
        *count += 1;
        sumNode(T->lchild, count);
        sumNode(T->rchild, count);
    }
    return *count;
}
int main()
{
    BiTree T;
    int level = 1;
    int count = 0;
    printf("请输入先序创建的二叉树，以#结束：");
    CreatBiTree(&T);
    printf("正在先序打印二叉树：");
    PreOrdeTraverse(T);
    putchar('\n');
    printf("正在中序打印二叉树：");
    InOrdeTraverse(T);
    putchar('\n');
    printf("正在后序打印二叉树：");
    PosOrdeTraverse(T);
    printf("正在层序打印二叉树：");
    LevelOrder(T);
    putchar('\n');
    printf("Nodes = %d\n", sumNode(T, &count));
    Search(T, level);
    return 0;
}

运行结果

谢谢观看

end；

数据结构学习

ADT树——C语言实现

数据结构——树

基础概念

树的存储结构

双亲表示法

孩子表示法

实现方法一

实现方法二

二叉树

二叉树基础概念

二叉树存储结构

二叉树的遍历

前序遍历：先访问根节点，然后遍历左节点，再遍历右节点：ABDGHCEIF

中序遍历：从根节点开始（并不访问根节点），先遍历节点左树，再访问根节点，后访问右树：GDHBAEICF

后序遍历：从根节点进入，先访问左子树，再访问右子树，最后放过根节点

层序遍历：按照层级关系对树进行遍历；使用队列实现：ABCDEFGHI

总的代码汇集

谢谢观看

相关

进阶数据结构学习笔记

一些杂七杂八的数据结构学习笔记

标签