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

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

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

@TOC

正文开始@小边同学还爱编程吗: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++
存储
分布式数据库
@浮光掠影
目录
相关文章
泡沫o0
|
2月前
|
算法 C++ 开发者
【C/C++ 数据结构 】二叉树基本性质：对于任何一颗二叉树T，若其终端结点为n0 ，那么度数为2的结点数为n2。则n0=n2+1...
【C/C++ 数据结构 】二叉树基本性质：对于任何一颗二叉树T，若其终端结点为n0 ，那么度数为2的结点数为n2。则n0=n2+1...
泡沫o0
31 0
是Nero哦
|
2月前
二叉树基础oj练习（对称二叉树、翻转二叉树、另一棵树的子树二叉树的构建及遍历）
二叉树基础oj练习（对称二叉树、翻转二叉树、另一棵树的子树二叉树的构建及遍历）
是Nero哦
28 0
走在努力路上的自己
|
2月前
|
存储
二叉树详解(深度优先遍历、前序，中序，后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数)
二叉树详解(深度优先遍历、前序，中序，后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数)
走在努力路上的自己
114 0
sky_qiyi
|
24天前
|
算法
数据结构和算法学习记录——层序遍历（层次遍历）、二叉树遍历的应用（输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树）
数据结构和算法学习记录——层序遍历（层次遍历）、二叉树遍历的应用（输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树）
sky_qiyi
17 0
只是雪豹
|
2月前
|
存储
二叉树链式结构的实现和二叉树的遍历以及判断完全二叉树
二叉树链式结构的实现和二叉树的遍历以及判断完全二叉树
只是雪豹
28 1
ForcibleBugMaker
|
2月前
|
机器学习/深度学习 C++
初阶数据结构之---二叉树链式结构（二叉树的构建，二叉树的前序，中序，后序和层序遍历，计算二叉树结点个数，第k层结点个数，叶子结点个数，判断是否为完全二叉树）
初阶数据结构之---二叉树链式结构（二叉树的构建，二叉树的前序，中序，后序和层序遍历，计算二叉树结点个数，第k层结点个数，叶子结点个数，判断是否为完全二叉树）
ForcibleBugMaker
37 0
柠檬叶子C
|
8月前
【霍罗维兹数据结构】二叉树前中后序遍历 | 层序遍历 | 复制二叉树 | 判断两个二叉树全等 | 可满足性问题
【霍罗维兹数据结构】二叉树前中后序遍历 | 层序遍历 | 复制二叉树 | 判断两个二叉树全等 | 可满足性问题
柠檬叶子C
51 0
无聊看看天T
|
2月前
|
算法
二叉树的结点个数、叶子结点个数的代码实现＜分治算法＞
二叉树的结点个数、叶子结点个数的代码实现＜分治算法＞
无聊看看天T
38 0
初阶牛
|
算法 安全
二叉树的基本操作(如何计算二叉树的结点个数,二叉树的高度)
二叉树的基本操作(如何计算二叉树的结点个数,二叉树的高度)
初阶牛
207 0
小王师傅66
|
算法
【算法】二叉排序树：创建二叉树，并以中序遍历输出
【算法】二叉排序树：创建二叉树，并以中序遍历输出
小王师傅66
193 0