开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构之二叉树(链式) -> 正文阅读

[数据结构与算法]数据结构之二叉树(链式)

1. 二叉树的概念及结构

1.1、概念

一棵二叉树是结点的一个有限集合，该集合:

空树
由一个根节点加上两棵别称为左子树和右子树的二叉树组成
非空：根节点，根节点的左子树、根节点的右子树组成

在这里插入图片描述

二叉树不存在度大于2的节点
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注意：对于任意的二叉树都是由以下几种情况复合而成的：

在这里插入图片描述

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的

1.2、构造二叉树

因为二叉树不适于进行增删查改等接口操作，没有意义，所以这里直接构造一个二叉树

#include <stdio.h>
#include <stdlib.h>
typedef int BTDataType;

typedef struct BinaryTreeNode
{
    struct BinaryTreeNode *left;  //左孩子节点
    struct BinaryTreeNode *right; //右孩子节点
    BTDataType val;
} BTNode;

//构造节点
BTNode *BuyBTNode(BTDataType x)
{
    BTNode *p = (BTNode *)malloc(sizeof(BTDataType));
    //判空
    if (p == NULL)
    {
        printf("malloc fail!!!\n");
        exit(EXIT_FAILURE);
    }
    p->val = x;
    //左右子树初始化为NULL
    p->left = p->right = NULL;

    return p;
}

//构造二叉树
BTNode *CreatBinaryTree()
{
    BTNode *node1 = BuyBTNode(1);
    BTNode *node2 = BuyBTNode(2);
    BTNode *node3 = BuyBTNode(3);
    BTNode *node4 = BuyBTNode(4);
    BTNode *node5 = BuyBTNode(5);
    BTNode *node6 = BuyBTNode(6);

    node1->left = node2;
    node2->left = node3;
    node1->right = node4;
    node4->left = node5;
    node4->right = node6;

    //返回根节点
    return node1;
}

int main()
{
    BTNode *Tree = CreatBinaryTree();
    return 0;
}

构建好的二叉树是这样的：如下图所示

在这里插入图片描述

2. 二叉树的遍历

2.1.1、前中后序遍历概念

学习二叉树结构，最简单的方式就是遍历。
所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。
访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前（依次访问：根节点左子树右子树）
中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之间(依次访问：左子树根节点右子树)
后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后（依次访问：左子树右子树根节点）

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

在这里插入图片描述

2. 1.2、前序遍历

//前序遍历
void PrevOrdef(BTNode *root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    printf("%d ", root->val);
    PrevOrdef(root->left);
    PrevOrdef(root->right);
}

前序遍历递归图解:
在这里插入图片描述

在这里插入图片描述

前序遍历实际输出(包括NULL)： 1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL

2.1.3、中序遍历

//中序遍历
void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    InOrder(root->left);
    printf("%d ", root->val);
    InOrder(root->right);
}

中序遍历递归图解:
在这里插入图片描述

前序遍历实际输出(包括NULL)：NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL

2.1.4、后序遍历

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

后序遍历递归图解:

在这里插入图片描述

前序遍历实际输出(包括NULL)：NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1

2.2.1、层序遍历

遍历分为二种：

深度优先遍历（DFS）：前序、中序和后序遍历
广度优先遍历（BFS）：层序遍历
注意：层序遍历是通过使用"队列"来辅助实现的

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历

在这里插入图片描述

造轮子：队列实现代码

Queue.h
#ifndef QUEUE_H_
#define QUEUE_H_

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

//链式队列->队列节点里面包含队列头和尾
struct BinaryTreeNode;
typedef struct BinaryTreeNode *QDataType;

typedef struct QueueNode
{
    QDataType val;          //数据域
    struct QueueNode *next; //指针域
} QNode;

typedef struct Queue
{
    QNode *head; //头节点->队列头
    QNode *tail; //尾结点->队列尾
} Queue;

void QueueInit(Queue *q);              //初始化
void QueueDestory(Queue *q);           //释放队列
void QueuePush(Queue *q, QDataType x); //数据入队列(从队尾进入)
void QueuePop(Queue *q);
bool QueueEmpty(Queue *q);      //判断队列是否为空
size_t QueueSize(Queue *q);     //队列长度
QDataType QueueFront(Queue *q); //队头数据
QDataType QueueBack(Queue *q);  //队尾数据
#endif



Queue.c
#include "Queue.h"

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

void QueueDestory(Queue *q)
{
    assert(q);

    QNode *cur = q->head;
    while (cur)
    {
        QNode *next = cur->next;
        free(cur);
        cur = next;
    }
    q->head = q->tail = NULL;
}

void QueuePush(Queue *q, QDataType x)
{
    assert(q);

    //开辟新节点
    QNode *newnode = (QNode *)malloc(sizeof(QNode));
    //判空
    if (newnode == NULL)
    {
        printf("malloc fail!!!\n");
        exit(EXIT_FAILURE);
    }
    else
    {
        newnode->val = x;
        newnode->next = NULL;
    }

    //入队列
    if (q->head == NULL && q->tail == NULL)
    {
        //如果队头和队尾都为NULL，则它们同时指向头节点
        q->head = newnode;
        q->tail = newnode;
    }
    else
    {
        q->tail->next = newnode;
        //更新队尾
        q->tail = newnode;
    }
}

void QueuePop(Queue *q)
{
    assert(q);
    assert(q->head != NULL);

    //出队列(从队头出)
    if (q->head->next == NULL)
    {
        //当只有一个节点时，头被释放，tail还是指向原来的头节点，这将导致不确定性
        free(q->head);
        q->tail = q->head = NULL;
    }
    else
    {
        QNode *next = q->head->next;
        free(q->head);
        q->head = next;
    }
}

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

size_t QueueSize(Queue *q)
{
    assert(q);
    assert(q->head);

    QNode *cur = q->head;
    size_t Size = 0;
    while (cur)
    {
        ++Size;
        cur = cur->next;
    }
    return Size;
}

QDataType QueueFront(Queue *q)
{
    assert(q);
    assert(q->head);

    return q->head->val;
}

QDataType QueueBack(Queue *q)
{
    assert(q);
    assert(q->tail);

    return q->tail->val;
}

层序遍历的实现：

//层序遍历->使用队列实现->注意：这里入队列入的是二叉树的根节点指针，不是根节点的值，入值就找不到左右子树的地址(指针)
#include "Queue.h"
void LevelOrder(BTNode *root)
{
    //声明队列并且初始化
    Queue q;
    QueueInit(&q);

    //判断根节点是否为空树，不是则入队列
    if (root != NULL)
        QueuePush(&q, root);

    //当队列为空就停止循环
    while (!QueueEmpty(&q))
    {
        //保存队头的数据(根节点指针)
        BTNode *front = QueueFront(&q);
        QueuePop(&q); //出队列

        printf("%d ", front->val); //出一个打印一个数据

        //判断根节点(front)的左子树和右子树是否为空，不为空就继续入队列
        if (front->left)
            QueuePush(&q, front->left);
        if (front->right)
            QueuePush(&q, front->right);
    }
    printf("\n");

    //释放队列，防止内存泄漏
    QueueDestory(&q);
}

层序遍历图解:
在这里插入图片描述

层序遍历实际输出：1 2 4 3 5 6

3. 前、中、后序和层序的变形接口

3.1.1、判断是否为完全二叉树

这是一个"层序遍历的变形接口"

首先来了解一下什么是"完全二叉树"

完全二叉树是由满二叉树而引出来的。满二叉树是一个节点满足2^k-1(通过等比数列推导出来)的二叉树，也就是说满二叉树每层都是满的。
完全二叉树是一个从第一层节点(根节点)开始到第k-1层都是满的，最后一层节点必须是连续的特殊二叉树。

在这里插入图片描述

代码实现：

//判断是否为完全二叉树
#include "Queue.h"
bool BTreeComplete(BTNode *root)
{
    //创建队列并且初始化
    Queue q;
    QueueInit(&q);

    //判断根节点是否为空树，不是则入队列
    if (root != NULL)
        QueuePush(&q, root); //根节点入队列

    while (!QueueEmpty(&q))
    {
        //保存队头的数据(根节点指针)
        BTNode *front = QueueFront(&q);
        QueuePop(&q); //出队列

        //如果节点为叶节点，则不用继续入队列了
        if (front == NULL)
            break;

        //这里不用判断节点是否为空，因为"空"也一起进队列
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }

    //判断剩余没出队列的数据，如果全是叶节点(左右子树都为NULL)则为完全二叉树
    while (!QueueEmpty(&q))
    {
        //保存队头的数据
        BTNode *front = QueueFront(&q);
        QueuePop(&q); //出队列

        //判断队列中数据是否为全空，如果不是"全空"则不是完全二叉树.
        // 空后面出到非空，那么说明不是完全二叉树
        if (front)
            //释放队列，防止内存泄漏
            QueueDestory(&q);
        return false;
    }

    //释放队列，防止内存泄漏
    QueueDestory(&q);
    return true;
}

图解：

在这里插入图片描述

实际输出为：0（false）
注意：我构建的树为：1 2 4 3 5 6（层序遍历）

3.1.2、二叉树的节点

思想1:：前、中、后序遍历，设置一个计数器，计算节点个数
思想2：分治

思想1实现：
注意：思想1实现时，不能把计数器（pi）进行传值，因为递归回归时，会把栈帧给销毁，回归后pi的值还是不变的…

//遍历计数方法比分治效率差一些，并且多了一个指针参数的内存空间
void BTreeSize2(BTNode *root, int *pi)
{
    if (root == NULL)
        return;
    //前序遍历计数
    ++(*pi);
    BTreeSize2(root->left, pi);
    BTreeSize2(root->right, pi);
}

这里就不画图解了，跟前序遍历一样，只不过加了个计数器…

思想2:实现：

//分治->左子树加右子树的个数，最后加上根节点的个数就能得到全部节点的数量
int BTreeSize(BTNode *root)
{
    if (root == NULL)
        return 0;
    return BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

图解：

在这里插入图片描述

实际输出为：6

3.1.3、二叉树叶节点

思想：分治->找左子树和右子树都为空的节点，空树返回0

代码实现：

//分治----求叶节点个数
int BTreeLeafSize(BTNode *root)
{
    //空树返回0
    if (root == NULL)
        return 0;
     //当左子树和右子树都为空时，就是叶节点，返回1
    else if (root->left == NULL && root->right == NULL)
        return 1;
    //递归判断往前走
    return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

图解：

在这里插入图片描述

实际输出：3

3.2.1、二叉树第k层节点个数

思路：分治->每次左子树或右子树的走到最后一层的k为1时，节点个数加1，空节点就回归

代码实现：

//第k层的节点个数->根节点为第一个层
int BTreeKLevelSize(BTNode *root, int k)
{
    if (root == NULL)
        return 0;
    if (k == 1)
        return 1;
    return BTreeKLevelSize(root->left, k - 1) + BTreeKLevelSize(root->right, k - 1);
}

图解：

在这里插入图片描述

实际输出：3

3.2.2、二叉树的高度

思想：分治->分别判断左子树和右子树的高度，判断两棵树中最高的那颗，高的则每次高度加1，空树高度为0

代码实现：

//二叉树的高度
int BTreeDepth(BTNode *root)
{
    if (root == NULL)
        return 0;
    int leftDepth = BTreeDepth(root->left);
    int rightDepth = BTreeDepth(root->right);

    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

图解：

在这里插入图片描述

实际输出：4

3.2.3、二叉树的查找

查找值为x的节点的地址（指针）
思路1：前、中、后序遍历
思路2：分治

空树返回NULL
左子树查找
右子树查找
左子树右子树都没有找到则返回NULL

代码实现思路2：正规的写法

// 二叉树查找值为x的节点
BTNode *TreeFind(BTNode *root, BTDataType x)
{
    if (root == NULL)
        return NULL;

    if (root->val == x)
        return root;

    //判断左子树是否有值为x的节点
    BTNode *left_subTree = TreeFind(root->left, x);
    if (left_subTree)
        return left_subTree;

    //判断右子树是否有值为x的节点
    BTNode *right_subTree = TreeFind(root->right, x);
    if (right_subTree)
        return right_subTree;

    //没有找到则返回空指针
    return NULL;
}

图解：

在这里插入图片描述

3.2.3、二叉树的销毁

思想：使用后序遍历进行销毁

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

这里不画图解了，跟后序遍历一样…

4.二叉树实现完整代码

队列

Queue.h
#ifndef QUEUE_H_
#define QUEUE_H_

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

//链式队列->队列节点里面包含队列头和尾
struct BinaryTreeNode;
typedef struct BinaryTreeNode *QDataType;

typedef struct QueueNode
{
    QDataType val;          //数据域
    struct QueueNode *next; //指针域
} QNode;

typedef struct Queue
{
    QNode *head; //头节点->队列头
    QNode *tail; //尾结点->队列尾
} Queue;

void QueueInit(Queue *q);              //初始化
void QueueDestory(Queue *q);           //释放队列
void QueuePush(Queue *q, QDataType x); //数据入队列(从队尾进入)
void QueuePop(Queue *q);
bool QueueEmpty(Queue *q);      //判断队列是否为空
size_t QueueSize(Queue *q);     //队列长度
QDataType QueueFront(Queue *q); //队头数据
QDataType QueueBack(Queue *q);  //队尾数据

#endif




Queue.c
#include "Queue.h"

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

void QueueDestory(Queue *q)
{
    assert(q);

    QNode *cur = q->head;
    while (cur)
    {
        QNode *next = cur->next;
        free(cur);
        cur = next;
    }
    q->head = q->tail = NULL;
}

void QueuePush(Queue *q, QDataType x)
{
    assert(q);

    //开辟新节点
    QNode *newnode = (QNode *)malloc(sizeof(QNode));
    //判空
    if (newnode == NULL)
    {
        printf("malloc fail!!!\n");
        exit(EXIT_FAILURE);
    }
    else
    {
        newnode->val = x;
        newnode->next = NULL;
    }

    //入队列
    if (q->head == NULL && q->tail == NULL)
    {
        //如果队头和队尾都为NULL，则它们同时指向头节点
        q->head = newnode;
        q->tail = newnode;
    }
    else
    {
        q->tail->next = newnode;
        //更新队尾
        q->tail = newnode;
    }
}

void QueuePop(Queue *q)
{
    assert(q);
    assert(q->head != NULL);

    //出队列(从队头出)
    if (q->head->next == NULL)
    {
        //当只有一个节点时，头被释放，tail还是指向原来的头节点，这将导致不确定性
        free(q->head);
        q->tail = q->head = NULL;
    }
    else
    {
        QNode *next = q->head->next;
        free(q->head);
        q->head = next;
    }
}

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

size_t QueueSize(Queue *q)
{
    assert(q);
    assert(q->head);

    QNode *cur = q->head;
    size_t Size = 0;
    while (cur)
    {
        ++Size;
        cur = cur->next;
    }
    return Size;
}

QDataType QueueFront(Queue *q)
{
    assert(q);
    assert(q->head);

    return q->head->val;
}

QDataType QueueBack(Queue *q)
{
    assert(q);
    assert(q->tail);

    return q->tail->val;
}

实现二叉树

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "Queue.h"

typedef int BTDataType;

typedef struct BinaryTreeNode
{
    struct BinaryTreeNode *left;  //左孩子节点
    struct BinaryTreeNode *right; //右孩子节点
    BTDataType val;
} BTNode;

//构造节点
BTNode *BuyBTNode(BTDataType x)
{
    BTNode *p = (BTNode *)malloc(sizeof(BTDataType));
    if (p == NULL)
    {
        printf("malloc fail!!!\n");
        exit(EXIT_FAILURE);
    }
    p->val = x;
    p->left = p->right = NULL;

    return p;
}

//构造二叉树
BTNode *CreatBinaryTree()
{
    BTNode *node1 = BuyBTNode(1);
    BTNode *node2 = BuyBTNode(2);
    BTNode *node3 = BuyBTNode(3);
    BTNode *node4 = BuyBTNode(4);
    BTNode *node5 = BuyBTNode(5);
    BTNode *node6 = BuyBTNode(6);

    node1->left = node2;
    node2->left = node3;
    node1->right = node4;
    node4->left = node5;
    node4->right = node6;

    //返回根节点
    return node1;
}

//前序遍历
void PrevOrdef(BTNode *root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    printf("%d ", root->val);
    PrevOrdef(root->left);
    PrevOrdef(root->right);
}

//中序遍历
void InOrder(BTNode *root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    InOrder(root->left);
    printf("%d ", root->val);
    InOrder(root->right);
}

//后序遍历
void PostOrder(BTNode *root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->val);
}

//层序遍历->使用队列实现->注意：这里入队列入的是二叉树的根节点指针，不是跟节点的值，入值找不到左右子树的地址
void LevelOrder(BTNode *root)
{
    //声明队列并且初始化
    Queue q;
    QueueInit(&q);

    //判断根节点是否为空树，不是则入队列
    if (root != NULL)
        QueuePush(&q, root);

    //当队列为空就停止循环
    while (!QueueEmpty(&q))
    {
        //保存队头的数据(根节点指针)
        BTNode *front = QueueFront(&q);
        QueuePop(&q); //出队列

        printf("%d ", front->val); //出一个打印一个数据

        //判断根节点(front)的左子树和右子树是否为空，不为空就继续入队列
        if (front->left)
            QueuePush(&q, front->left);
        if (front->right)
            QueuePush(&q, front->right);
    }
    printf("\n");

    //释放队列，防止内存泄漏
    QueueDestory(&q);
}

//判断是否为完全二叉树
bool BTreeComplete(BTNode *root)
{
    //创建队列并且初始化
    Queue q;
    QueueInit(&q);

    //判断根节点是否为空树，不是则入队列
    if (root != NULL)
        QueuePush(&q, root); //根节点入队列

    while (!QueueEmpty(&q))
    {
        //保存队头的数据(根节点指针)
        BTNode *front = QueueFront(&q);
        QueuePop(&q); //出队列

        //如果节点为叶节点，则不用继续入出队列了
        if (front == NULL)
            break;

        //这里不用判断节点是否为空，因为"空"也一起进队列
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }

    //判断剩余没出队列的数据，全是叶节点(左右子树都为NULL)则为完全二叉树
    while (!QueueEmpty(&q))
    {
        //保存队头的数据(根节点指针)
        BTNode *front = QueueFront(&q);
        QueuePop(&q); //出队列

        //判断队列中数据是否为全空，如果不是"全空"则不是完全二叉树.
        // 空后面出到非空，那么说明不是完全二叉树
        if (front)
            //释放队列，防止内存泄漏
            QueueDestory(&q);
        return false;
    }

    //释放队列，防止内存泄漏
    QueueDestory(&q);
    return true;
}

//节点个数----分治->左子树加右子树最后加上根节点就能得到全部节点的数量
int BTreeSize(BTNode *root)
{
    if (root == NULL)
        return 0;
    return BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

//遍历计数方法比分治效率差一些，并且多了一个指针参数的内存空间
void BTreeSize2(BTNode *root, int *pi)
{
    if (root == NULL)
        return;
    //前序遍历计数
    ++(*pi);
    BTreeSize2(root->left, pi);
    BTreeSize2(root->right, pi);
}

//分治----求叶节点个数
int BTreeLeafSize(BTNode *root)
{
    if (root == NULL)
        return 0;
    else if (root->left == NULL && root->right == NULL)
        return 1;
    return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

//第k层的节点个数->根节点为第一个层
int BTreeKLevelSize(BTNode *root, int k)
{
    if (root == NULL)
        return 0;
    if (k == 1)
        return 1;
    return BTreeKLevelSize(root->left, k - 1) + BTreeKLevelSize(root->right, k - 1);
}

//二叉树的高度
int BTreeDepth(BTNode *root)
{
    if (root == NULL)
        return 0;
    int leftDepth = BTreeDepth(root->left);
    int rightDepth = BTreeDepth(root->right);

    return leftDepth > rightDepth
               ? leftDepth + 1
               : rightDepth + 1;
}

// 二叉树查找值为x的节点
BTNode *TreeFind(BTNode *root, BTDataType x)
{
    if (root == NULL)
        return NULL;

    if (root->val == x)
        return root;

    //判断左子树是否有值为x的节点
    BTNode *left_subTree = TreeFind(root->left, x);
    if (left_subTree)
        return left_subTree;

    //判断右子树是否有值为x的节点
    BTNode *right_subTree = TreeFind(root->right, x);
    if (right_subTree)
        return right_subTree;

    //没有找到则返回空指针
    return NULL;
}

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

int main()
{
    BTNode *Tree = CreatBinaryTree();
    //前序遍历
    printf("前序遍历: ");
    PrevOrdef(Tree);
    printf("\n");

    //中序遍历
    printf("中序遍历: ");
    InOrder(Tree);
    printf("\n");

    //后序遍历
    printf("后序遍历: ");
    PostOrder(Tree);
    printf("\n");

    //层序遍历
    printf("层序遍历: ");
    LevelOrder(Tree);

    printf("二叉树的节点个数为: %d\n", BTreeSize(Tree));

    int count = 0;
    BTreeSize2(Tree, &count);
    printf("二叉树的节点个数为: %d\n", count);

    printf("二叉树的叶节点个数为: %d\n", BTreeLeafSize(Tree));

    int k = 3;
    printf("二叉树第%d层的节点为: %d\n", k, BTreeKLevelSize(Tree, k));

    printf("二叉树的高度为: %d\n", BTreeDepth(Tree));

    for (int i = 1; i < 8; ++i)
    {
        printf("x: %d, 地址: %p\n", i, TreeFind(Tree, i));
    }

    printf("判断是否为完全二叉树: %d\n", BTreeComplete(Tree));

    //释放二叉树
    // BinaryTreeDestory(&Tree);
    system("pause");
    return 0;
}