AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【DS】树&二叉树链式结构及实现@二叉树 —— 前中后序遍历 | 求节点个数高度等 | 层序遍历&判断是否是完全二叉树

2022-07-29 476
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 前中后序遍历 | 求节点个数高度等 | 层序遍历&判断是否是完全二叉树

正文开始@小边同学还爱编程吗:star:

树&二叉树链式结构及实现

1. 树概念及结构

1.1 树的概念

树是一种非线性的数据结构，它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是根朝上，而叶朝下的。

树是递归定义的。任何树都会被分成根和子树（多个/空）
<img src=" title="">

1.2 树的相关概念

<img src=" title="">

:blue_heart:节点的度：一个节点含有的子树的个数称为该节点的度。
:blue_heart:叶节点或终端节点：度为0的节点称为叶节点。
:blue_heart:分支节点或非终端节点：度不为0的节点。
:yellow_heart:父节点或双亲节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
:yellow_heart:子节点或孩子节点：一个节点含有的子树的根节点称为该节点的子节点。
:yellow_heart:兄弟节点：具有相同父节点的节点（亲兄弟）互称为兄弟节点。如上图：B、C是兄弟节点，H、I不是
:yellow_heart:堂兄弟节点：双亲在同一层的节点互为堂兄弟。如上图：H、I互为堂兄弟节点
:yellow_heart:节点的祖先：从根到该节点所经分支上的所有节点。如上图：A、E、J都是Q的祖先
:yellow_heart:子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
:green_heart:树的度：一棵树中，最大的节点的度称为树的度。如上图：树的度为6
:green_heart:节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
:green_heart:树的高度或深度：树中节点的最大层次。如上图：树的高度为4，3
:green_heart:森林：由m（m>0）棵互不相交的树的集合称为森林。并查集就是多棵树构成的森林（以后详谈）

1.3 树的表示

树结构相对线性表比较复杂，既要保存值域，也要保存结点和结点之间的关系，怎么存储呢？

实际中树有很多种表示方式如：双亲表示法，孩子表示法及孩子双亲表示法等。它们各有优缺点，我们这里重点介绍表示树结构最优方法 —— 左孩子右兄弟表示法。

方式1：假设已知树的度为N

struct TreeNode
{
    int data;
    struct TreeNode* subs[N];
}

问题：可能存在不少的空间浪费；万一没有限定树的度是多少呢？

方式2：用链表代替数组来存储其孩子节点

typedef struct TreeNode* SLDataType;
struct TreeNode
{
    int data;
    SeqList s; // SLDataType* a; //c++ vector
}

问题：结构相对复杂

方式3：结构数组存储 —— 双亲表示法（只存父亲）

struct TreeNode
{
    int parent;
    int data;
}

<img src=" title="">

:yellow_heart: 左孩子右兄弟表示法

typedef int DataType;
struct Node
{
    //只存两个指针
    struct Node* _firstChild1;     // 第一个孩子结点
    struct Node* _pNextBrother; // 指向其下一个兄弟结点
    DataType _data;                // 结点中的数据域
};

没有空间浪费，且可完整表示，真的很妙！

<img src=" title="">

1.4 树在实际中的运用

表示文件系统的目录树结构

<img src=" title="">

2. 二叉树概念及结构

树本身并不常用，下面介绍二叉树。

2.1 二叉树的概念

:yellow_heart: 二叉树

  1. 度最大为2的树，最多只有两个孩子。
  2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

对于任意的二叉树都是由以下几种情况复合而成的：

<img src=" title="">

现实中的二叉树 ——

<img src=" title="">

2.2 特殊的二叉树

:yellow_heart: 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

  1. 所有的叶子节点都在最后一层
  2. 左右的分支节点都有两个孩子

:yellow_heart: 完全二叉树

  1. 前(n-1)层都是满的
  2. 最后一层不一定满，但是最后一层从左到右是连续的

<img src=" title="">

注：满二叉树是一种特殊的完全二叉树。

1.假设树的高度为$h$，总共有$2^h-1$个节点，由等比数列求和公式求得

$2^0+2^1+ ...2^(h-1) = 1(2^-1)/(2-1) = 2^h-1$

2.一棵满二叉树有$N$个节点，高度是多少，由N = 2^h-1^

满二叉树高度为 h = log~2~(N+1)

2.3 二叉树的性质

1.一个 $n$ 个结点的二叉树拥有 $(n-1)$ 条边
2.若规定根节点的层数为1，则一棵非空二叉树的第$i$层上最多有 2^i-1^ 个结点
3.度为0的度为2的永远多1个。对任何一棵二叉树，如果度为0其叶结点个数为n~0~ ，度为2的分支结点个数为n~2~ ，则有 n~0~＝ n~2~＋1（学图论的时候啊，证过一大堆这些破玩意儿，我都忘了）

其它在堆中的性质，下一篇文章见。

关于这些性质，有一系列题目，熟悉性质就很简单

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199

n0 = n2 + 1  n0 = 200
3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2

由n0 + n1 + n2 = 2n
n0 = n2 + 1
得2n0 + n1 - 1 = 2n

完全二叉树最多度为1的节点只能是0个或者1个，
n~1~ = 0时，n~0~不是整数；n~1~ = 1时，n~0~ = n

5.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386

n0 + n1 + n2 = 768
n0 = n2 + 1
n0 = 384 选笔。
4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12

高度为$h$的完全二叉树的节点范围是[ 2^h-1^-1+1，2^h^-1]，选笔

2.4 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

2.4.1 顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树。因为非完全二叉树会有空间的浪费，所以现实使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

关于堆，经典的堆排序和TopK问题马上单独出文章见~

2.4.2 链式存储

二叉树的链式存储结构是指，用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面高阶数据结构如红黑树等会用到三叉链。

<img src=" title="">

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
     struct BinTreeNode* _pLeft; // 指向当前节点左孩子
     struct BinTreeNode* _pRight; // 指向当前节点右孩子
     BTDataType _data; // 当前节点值域
}

// 三叉链
struct BinaryTreeNode
{
     struct BinTreeNode* _pParent; // 指向当前节点的双亲
     struct BinTreeNode* _pLeft; // 指向当前节点左孩子
     struct BinTreeNode* _pRight; // 指向当前节点右孩子
     BTDataType _data; // 当前节点值域
}；

今天我们要实现的是二叉树的链式结构。

3. 二叉树链式结构的实现

普通二叉树的增删查改没有什么价值，用它来存数据太复杂了。因此在这里我们不关注增删查改，关注递归遍历结构。

价值体现 ——

  • [ ] 为后面学习更有用的树（在它的基础上，增加一些性质）打下基础
  • [ ] 很多oj题结构是普通二叉树。对的，马上再来更新一波题解。

老规矩，头文件附在后面了，有需要自取。

3.0 前置说明

在对二叉树的做基本操作前，需先有一棵二叉树。由于现在对二叉树结构掌握还不够深入，此处暂时手动构建一棵简单的二叉树，快速上手，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

BTNode* BuyNode(BTDataType x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if (newnode == NULL)
    {
        printf("malloc failed\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->left = newnode->right = NULL;
    return newnode;
}

BTNode* CreateBinaryTree()
{
    BTNode* nodeA = BuyNode('A');
    BTNode* nodeB = BuyNode('B');
    BTNode* nodeC = BuyNode('C');
    BTNode* nodeD = BuyNode('D');
    BTNode* nodeE = BuyNode('E');
    BTNode* nodeF = BuyNode('F');

    nodeA->left = nodeB;
    nodeA->right = nodeC;
    nodeB->left = nodeD;
    nodeC->left = nodeE;
    nodeC->right = nodeF;

    return nodeA;
}

这篇文章我们就要与它为伴了:innocent: ——

<img src=" title="">

3.1 前中后序遍历

:yellow_heart: 首先了解什么是所谓的前序/中序/后序的递归结构遍历。按照规则，二叉树的遍历有——

  1. 前序遍历，亦称先序遍历(Preorder Traversal) —— 访问根左子树右子树。
  2. 中序遍历(Inorder Traversal) —— 访问左子树根右子树。
  3. 后序遍历(Postorder Traversal) —— 访问左子树右子树根。

<img src=" title="">

二叉树的递归遍历，是一种分治思想，即分而治之，大事化小，小事化了。（本文只写递归版本的深先，非递归版本的我们cpp见）

遍历一棵树，就可以拆分成，根，遍历左子树，遍历右子树；遍历该左子树再拆分为，左子树的根，遍历左子树的左子树，遍历左子树的右子树，以此类推。直至遍历到空节点，小事化了，再返回。前中后序递归过程类似，只不过访问/打印根节点时机不一样罢了。

上图中，访问顺序为 ——

前序    A B D NULL NULL NULL C E NULL NULL F NULL NULL
中序  NULL D NULL B NULL A NULL E NULL C NULL F NULL
后序  NULL NULL D NULL B NULL NULL E NULL NULL F C A

3.1.1 前序遍历

  • [ ] 两要素：不断向递归终止条件靠近&递归终止条件
  • [ ] 这里把NULL都打印，很多地方都是不打印的，但打印出来才看得到递归的本质。
void PreOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    printf("%c ", root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

你觉得这些递归难理解吗？三个月前我初学可能也有同样的感觉，现在看也还算是理所当然，不清晰那就去画递归展开图吧！

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Rl9TWmqD-1644589500703)(C:\Users\13136\AppData\Roaming\Typora\typora-user-images\image-20220210183654303.png)]

3.1.2 中序遍历

void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}

3.1.3 后序遍历

void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%c ", root->data);
}

<img src=" title="">

3.2 节点个数及高度等

下面都是对分而治之思想的应用，这些带返回值的递归如果觉得不清晰，就去画递归展开图理解吧。

3.2.1 二叉树的节点个数

分治：

  • [ ] 二叉树的节点个数 = 自己(1) + 左子树节点个数 + 右子树节点个数
  • [ ] 不可拆分的子问题：空节点
int BinaryTreeLeafSize(BTNode* root)
{
    return root == 0 ? 0 : 
                 1 + BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
    /*if (root == NULL)
        return 0;
    return 1 + BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);*/
}

求二叉树节点个数也可以采用遍历计数的方法，但要注意

// 如果不加static,递归调用建立函数栈桢，count是局部变量，不是对一个变量++
// 如果加了static,此时放在静态区，但依然有问题，求第二棵树的时候，节点数累加
// 1.遍历计数 -- 有问题
int BinaryTreeSize(BTNode* root)
{
    if (root == NULL)
        return 0;
    static int count = 0;
    count++;
    BinaryTreeSize(root->left);
    BinaryTreeSize(root->right);
    return count;
}

因此我们引入 2.输出型参数 或者 上文的返回值的分治的方法

// 2.输出型参数
void BinaryTreeSize(BTNode* root, int* pn)
{
    if (root == NULL)
        return 0;
    (*pn)++;
    BinaryTreeSize(root->left, pn);
    BinaryTreeSize(root->right, pn);
}

3.2.2 二叉树的的叶子结点个数

分治：

  • [ ] 二叉树的的叶子结点个数 = 左子树叶子节点个数 + 右子树叶子结点个数
  • [ ] 不可拆分的子问题：叶子节点，返回1
int BinaryTreeLeafSize(BTNode* root)
{
    if (root == NULL)
        return 0; //处理空树，包括子树当中为空的情况
    if (root->left == NULL && root->right == NULL)
        return 1;
    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

3.2.3 二叉树第k层节点个数

分治：这个确实不容易想呢

  • [ ] 提示：求A的第四层节点个数 = 求左子树的第三层节点个数 + 求右子树的第三层节点个数
  • [ ] 不可拆分的子问题：到第1层，即叶子节点。相对距离为0，不用再往下沉了。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ytuIeGBc-1644589500706)(C:\Users\13136\AppData\Roaming\Typora\typora-user-images\image-20220211152101792.png)]

int BinaryTreeLevelKSize(BTNode* root, int k)
{
    if (root == NULL)
        return 0;
    if (k == 1)
        return 1;
    return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

3.2.4 二叉树的深度

分治：

  • [ ] 二叉树的深度/高度 = 1 + 左子树、右子树的深度较大的（像后序）
  • [ ] 不可拆分的子问题：空节点
int BinaryTreeDepth(BTNode* root)
{
    if (root == NULL)
        return 0;
    int leftDepth = BinaryTreeDepth(root->left);
    int rigthDepth = BinaryTreeDepth(root->right);
    return 1 + (leftDepth > rigthDepth ? leftDepth : rigthDepth);
}

注意：

    // 这样会有大量的重复计算
    return BinaryTreeDepth(root->left) > BinaryTreeDepth(root->right) ? 
        BinaryTreeDepth(root->left) + 1 : BinaryTreeDepth(root->right) + 1;

3.2.5 二叉树查找值为x的节点

分治：

  • [ ] 二叉树查找值为x的节点 = 本身是不是 + 在左子树中查找值为x的节点 + 在右子树中查找值为x的节点 （相当于前序遍历顺序查找）
  • [ ] 不可拆分的子问题：值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    BTNode* leftRet;
    BTNode* rightRet;
    if (root == NULL)
        return NULL;
    if (root->data == x)
        return root;

    leftRet = BinaryTreeFind(root->left, x);
    if (leftRet)
        return leftRet;

    rightRet = BinaryTreeFind(root->right, x);
    if (rightRet)
        return rightRet;

    return NULL;
}

觉得不清晰，就在脑子里面走一遍递归过程，画递归展开图也可，画图太累了我不画了。

其实，我们把函数调用的第一层逻辑考虑清楚，整个递归问题就不大。

3.3 层序遍历

3.3.1 层序遍历

层序遍历：自上而下，自左至右逐层访问树的结点的过程。

这里要利用队列先进先出的性质。目前还是要把之前写好的文件包过来。

:yellow_heart: 1. 先入根

:yellow_heart: 2. 当前节点出来，把孩子带进去。就是这样上一层出的时候，带入下一层

:yellow_heart: 3. 队列为空，说明走后一层没有节点，遍历结束。

A B C D E F

<img src=" title="">

:heart: 注注注意：此时队列中的数据类型是树的节点。之前的Queue.h我们数据类型是int，因此现在要做一些改动。

Queue.h

//注意是树的节点--数据类型
//前置声明
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QDataType;

//队列
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;

//多个变量，那就用结构体封起来
typedef struct Queue
{
    QueueNode* head;
    QueueNode* tail;
}Queue;

​

层序遍历 ——

void LevelOrder(BTNode* root)
{
    if (root == NULL)
    {
        return ;
    }
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        printf("%c ", front->data);
        QueuePop(&q);

        if (front->left)
            QueuePush(&q, front->left);
        if (front->right)
            QueuePush(&q, front->right);
    }
    printf("\n");
    QueueDestroy(&q);
}

<img src=" title="">

3.3.2 判断是否为完全二叉树

判断是否为完全二叉树是层序遍历的变形

<img src=" title="">

遇到空了以后，出剩下的所有节点并检查

bool BinaryTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    // 1.层序遍历小变形
    QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front == NULL)
        {
            break;
        }
        // 带孩子进队列，空的也要带
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }
    // 2.遇到空后，出队检查
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front)
        {
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}

3.4 销毁

二叉树的销毁依旧是递归销毁的，相当于后序遍历

void BinaryTreeDestory(BTNode* root)
{
    if (root == NULL)
        return ;
    BinaryTreeDestory(root->left);
    BinaryTreeDestory(root->right);
    free(root);
}

为了保证接口一致，可以传一级指针，但要注意需要在外边置空，在里面置空没有作用（众所周知，形参改变不会影响实参）

    BinaryTreeDestory(root);
    root = NULL;

当然也可以传二级，那就可以在里边置空了。

附

BinaryTree.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef char BTDataType;

typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
    BTDataType data;
}BTNode;

// 二叉树前序遍历    
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);

//求二叉树节点的个数
void BinaryTreeSize(BTNode* root,int* pn);
//int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//二叉树的深度
int BinaryTreeDepth(BTNode* root);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

// 层序遍历
void LevelOrder(BTNode* root);
//判断一棵树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

// 二叉树手动构建
BTNode* CreateBinaryTree();
// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
//传一级二级都行：外面置空(里面置空没有用)
//这里为了保持传参的一致性传一级

BinaryTree.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"BinaryTree.h"
#include"Queue.h"

// 二叉树前序遍历
void PreOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    printf("%c ", root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

// 二叉树中序遍历
void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}

// 二叉树后序遍历
void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%c ", root->data);
}

// 1. 遍历计数的方法 
// 如果不加static,递归调用建立函数栈桢，count是局部变量，不是对一个变量++
// 如果加了static,此时放在静态区，但依然有问题，求第二棵树的时候，节点数累加
// 因此我们引入2.输出型参数或者3.返回值的方法
//int BinaryTreeSize(BTNode* root)
//{
//    if (root == NULL)
//        return 0;
//    static int count = 0;
//    count++;
//    BinaryTreeSize(root->left);
//    BinaryTreeSize(root->right);
//    return count;
//}

// 2.输出型参数
void BinaryTreeSize(BTNode* root, int* pn)
{
    if (root == NULL)
        return 0;
    (*pn)++;
    BinaryTreeSize(root->left, pn);
    BinaryTreeSize(root->right, pn);
}

//// 3. 分治
//int BinaryTreeSize(BTNode* root)
//{
//    return root == 0 ? 0 : 1 + BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
//    /*if (root == NULL)
//        return 0;
//    return 1 + BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);*/
//}

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
    if (root == NULL)
        return 0; //不仅仅是空树的情况,走到某个子树为空
    if (root->left == NULL && root->right == NULL)
        return 1;
    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
    if (root == NULL)
        return 0;
    if (k == 1)
        return 1;
    return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

//二叉树的深度
int BinaryTreeDepth(BTNode* root)
{
    if (root == NULL)
        return 0;
    int leftDepth = BinaryTreeDepth(root->left);
    int rigthDepth = BinaryTreeDepth(root->right);
    return 1 + (leftDepth > rigthDepth ? leftDepth : rigthDepth);
}

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    BTNode* leftRet;
    BTNode* rightRet;
    if (root == NULL)
        return NULL;
    if (root->data == x)
        return root;

    leftRet = BinaryTreeFind(root->left, x);
    if (leftRet)
        return leftRet;

    rightRet = BinaryTreeFind(root->right, x);
    if (rightRet)
        return rightRet;

    return NULL;
}


void LevelOrder(BTNode* root)
{
    if (root == NULL)
    {
        return ;
    }
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        printf("%c ", front->data);
        QueuePop(&q);

        if (front->left)
            QueuePush(&q, front->left);
        if (front->right)
            QueuePush(&q, front->right);
    }
    printf("\n");
    QueueDestroy(&q);
}

bool BinaryTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front == NULL)
        {
            break;
        }
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front)
        {
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}

BTNode* BuyNode(BTDataType x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if (newnode == NULL)
    {
        printf("malloc failed\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->left = newnode->right = NULL;
    return newnode;
    printf("\n");
}


BTNode* CreateBinaryTree()
{
    BTNode* nodeA = BuyNode('A');
    BTNode* nodeB = BuyNode('B');
    BTNode* nodeC = BuyNode('C');
    BTNode* nodeD = BuyNode('D');
    BTNode* nodeE = BuyNode('E');
    BTNode* nodeF = BuyNode('F');
    BTNode* nodeG = BuyNode('G');

    nodeA->left = nodeB;
    nodeA->right = nodeC;
    nodeB->left = nodeD;
    nodeC->left = nodeE;
    nodeC->right = nodeF;
    nodeB->right = nodeG;

    return nodeA;
}

void BinaryTreeDestory(BTNode* root)
{
    if (root == NULL)
        return ;
    BinaryTreeDestory(root->left);
    BinaryTreeDestory(root->right);
    free(root);
    root = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"BinaryTree.h"
#include"Queue.h"

int main()
{
    BTNode* root = CreateBinaryTree();
    /*PreOrder(root);
    printf("\n");

    InOrder(root);
    printf("\n");

    PostOrder(root);
    printf("\n");*/

    // 求二叉树节点的个数
    ////1.遍历计数又问题哈
    /*printf("size:%d\n", BinaryTreeSize(root));
    printf("size:%d\n", BinaryTreeSize(root));*/

    //2.求二叉树节点的个数
    int n1 = 0;
    BinaryTreeSize(root, &n1);
    printf("BinaryTreeSize:%d\n", n1);

    //3. 分治
    //printf("size:%d\n", BinaryTreeSize(root));
    
    printf("LeafSize:%d\n", BinaryTreeLeafSize(root));

    printf("BinaryTreeLevelKSize:%d\n", BinaryTreeLevelKSize(root,4));

    printf("BinaryTreeDepth:%d\n", BinaryTreeDepth(root));

    BTNode* p = BinaryTreeFind(root, 'D');
    printf("BinaryTreeFind:%c\n", p->data);

    LevelOrder(root);

    printf("BinaryTreeComplete:%d\n", BinaryTreeComplete(root));

    BinaryTreeDestory(root);
    root = NULL;
    return 0;
}

Queue.h

#pragma once

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

//注意是树的节点--数据类型
//前置声明
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QDataType;

//队列
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;

//多个变量，那就用结构体封起来
typedef struct Queue
{
    QueueNode* head;
    QueueNode* tail;
}Queue;

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);

//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//求队列中有效元素个数
int QueueSize(Queue* pq);
//判断队列是否为空？
bool QueueEmpty(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
}

void QueueDestroy(Queue* pq)
{
    assert(pq);
    QueueNode* cur = pq->head;
    while (cur)
    {
        QueueNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    newnode->data = x;
    newnode->next = NULL;
    if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;//迭代
    }
}

void QueuePop(Queue* pq)
{
    assert(pq);
     assert(!QueueEmpty(pq));
    QueueNode* newhead = pq->head->next;
    free(pq->head);
    pq->head = newhead;
    if (pq->head == NULL)
    {
        pq->tail = NULL;
    }
}

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}

int QueueSize(Queue* pq)
{
    assert(pq);
    int size = 0;
    QueueNode* cur = pq->head;
    while (cur)
    {
        cur = cur->next;
        size++;
    } 
    return size;
}

bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}

马上更新一波二叉树经典题解@边同学

文章标签：
C++
存储
分布式数据库
@浮光掠影
目录
相关文章
Linux开发架构之路
|
存储 网络协议 编译器
探索C++14新特性：更强大、更高效的编程
探索C++14新特性：更强大、更高效的编程
Linux开发架构之路
935 0
探索C++14新特性：更强大、更高效的编程
卡尔特斯
|
小程序
微信小程序 - 二维码数据解析，如何扫码进入开发版测试二维码数据
微信小程序 - 二维码数据解析，如何扫码进入开发版测试二维码数据
卡尔特斯
962 0
游客rihqhtgkydneq
|
机器学习/深度学习 JSON JavaScript
图文讲解 Stable Diffusion API 调用教程
Stable Diffusion 是一个先进的深度学习模型，用于创造和修改图像。这个模型能够基于文本描述来生成图像，让机器理解和实现用户的创意。使用这项技术的关键在于掌握其 API，通过编程来操控图像生成的过程。
游客rihqhtgkydneq
2031 0
荔枝科研社
|
2月前
|
开发者 Python
2025年高教社杯A题——烟幕干扰弹的投放策略全国大学生数学建模（思路、代码、论文）
2025年高教社杯A题——烟幕干扰弹的投放策略全国大学生数学建模（思路、代码、论文）
荔枝科研社
344 0
阿里云开发者
|
3月前
|
存储 人工智能 机器人
别再只做聊天机器人：AI 应用商业闭环的工程落地指南，免费体验中
本文介绍了如何通过阿里云百炼平台创建一个星座运势分析AI智能体，并集成支付宝MCP服务实现支付闭环。解决AI产品无法直接变现的问题，完成“服务-支付-交易”全流程闭环，帮助开发者快速实现商业化。
阿里云开发者
331 9
python编程狮
|
数据采集 数据可视化 关系型数据库
【python案例】基于Python 爬虫的房地产数据可视化分析设计与实现
本文设计并实现了一个基于Python爬虫的房地产数据可视化分析系统，通过BeautifulSoup框架采集房源信息，使用pandas进行数据处理，MySQL存储数据，并利用pyecharts进行数据可视化，以帮助用户更直观地了解房源信息并辅助选房购房。
python编程狮
1749 4
游客dk6iqnpz2vtei
|
8月前
|
存储 监控 虚拟化
Hyper V上网优化：提升虚拟机网络速度
要优化Hyper-V虚拟机的网络速度，可从以下几方面入手：1. 优化虚拟交换机配置，如选择合适的交换机类型、启用SR-IOV、配置VLAN和QoS策略；2. 调整网络适配器设置，选择适当的适配器类型并启用VRQ等；3. 优化宿主机网络配置，更新网卡固件和驱动，启用硬件加速；4. 使用性能监视工具监控网络流量；5. 其他措施如启用硬件虚拟化、使用外部存储、配置NLB等。通过合理配置，可显著提升网络性能。
游客dk6iqnpz2vtei
965 17
楠竹11
|
机器学习/深度学习 人工智能
大模型架构将迎来除 Transformer 之外的突破
大模型架构将迎来除 Transformer 之外的突破
楠竹11
328 2
大模型架构将迎来除 Transformer 之外的突破
兮叶william-38860
|
机器学习/深度学习 人工智能 算法
AI在医疗影像识别中的应用与实践
本文综述了人工智能在医疗影像分析的应用，涵盖了基础理论、操作流程、关键算法及实践案例。通过探讨卷积神经网络等技术，展示了如何构建医疗影像分析系统并提高诊断精度和效率，为医疗行业的创新发展提供了有力支持。
兮叶william-38860
556 2
大鹏cool
|
XML 缓存 Java
Spring AOP 的三种使用方式(万字长文)
前言 Spring AOP 作为 Spring Framework 的核心模块，对 Spring IOC 加以补充，Spring 内部使用它提供了企业级的服务，如事务、异步、缓存等，同时它也允许用户自定义 Aspect，以便用 AOP 补充对 OOP 的使用。通常情况下，我们会通过 AspectJ 的注解来使用 Spring AOP，那么 Spring 一共提供了哪些使用 AOP 的方式呢？本篇将对其总结，并尝试了解 Spring AOP 的内部实现。
大鹏cool
420 0
Spring AOP 的三种使用方式(万字长文)

热门文章

最新文章

  • 1
    2019阿里云双11来袭,价格非常重要,但是懂得上云攻略更重要
  • 2
    OpenSearch大模型实践之Havenask篇
  • 3
    Git——初始化本地项目并上传到gitlab
  • 4
    07.Java基础（泛型）
  • 5
    沫沫金::一个小问题引发的大思考
  • 6
    Hough变换的方法检测直线段，效果良好
  • 7
    java发送内嵌图片邮件
  • 8
    STL——空间的配置和释放std::alloc（第一级配置器和第二级配置器）
  • 9
    MyBatis之一对多映射查询sql配置文件。
  • 10
    Eclipse 4.3正式版发布
  • 1
    《Unity多插件原生库依赖协同适配实战指南》
    41
  • 2
    《Unity安卓开发密钥管理全流程实战指南》
    35
  • 3
    租用阿里云服务器一个月多少钱？看完吓一跳，这么便宜了吗？
    58
  • 4
    基于微信小程序的防诈骗管理系统
    57
  • 5
    从零开始：用Python和Gemini 3四步搭建你自己的AI Agent
    74
  • 6
    云安全自动化：当攻击来敲门，我们用代码说“不”
    55
  • 7
    监控体系大一统：OpenTelemetry 就是运维人的“鸿蒙”
    58
  • 8
    到底该选谁？Hadoop、Spark、Flink、云大数据的“江湖全景图”
    44
  • 9
    jdguiwindows.rar使用步骤 手把手教你打开看jar包（附安装包）
    36
  • 10
    NeurlPS 2025！多伦多大学TIRE助力3D/4D 生成精准保留主体身份
    46

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    阿里云负载均衡收费标准：ALB、NLB和CLB价格，包括LCU费用、实例费和公网带宽价格