二叉树（Binary Tree）是有n（n≥0）个结点的有限集合：
（1) 该集合或者为空（n=0)；
（2）或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树；
（3）左子树和右子树同样又都是二叉树。
在一棵非空的二叉树中，每个结点至多只有两棵子树，分别称为左子树和右子树，且左右子树的次序不能任意交换。所以，二叉树是特殊的有序树。值得注意的是，由于二叉树上任结点的子树有左、右之分，因此即使一个结点只有一棵非空子树，仍须区别它是该结点的左子树还是右子树，这是与树不同的。

2、二叉树的五种形态

二叉树的子树：

在二叉树中，一个子树是指由二叉树中的某个节点及其后代节点组成的树。换句话说，对于一个给定的二叉树，可以选择其中的一个节点作为子树的根节点，并且包含该节点的所有后代节点，形成一个新的子树。

具体定义如下：
在一个二叉树中，每个节点最多只有两个子节点，分别为左子节点和右子节点。对于任意一个节点，在它的左子节点和右子节点上又可以分别构成两个独立的子树，这样就形成了一个递归的结构。

3、满二叉树与完全二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。特点：树高为h时，前h-1层节点为满。 要注意的是满二叉树是一种特殊的完全二叉树。

4、二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点。
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1。
对任何一棵二叉树, 如果度为0的叶结点个数为n0，度为2的分支结点个数为n2，则有 n0 = n2 + 1。
若规定根节点的层数为1，具有n个结点的满二叉树的深度h= log2(n+1)。（这里的log是以2为底的对数）
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
a. 若i > 0，i位置节点的双亲序号为(i-1)/2，若i = 0，则i为根节点编号，无双亲节点。
b. 若2i+1 < n，左孩子序号为2i+1，若2i+1 >= n，则无左孩子。
c. 若2i+2 < n，右孩子序号为2i+2，若2i+2 >= n，则无右孩子。

5、二叉树的存储结构

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

1、顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的博客会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2、链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，本节内容我们主要讲解二叉链式存储结构。

链式二叉树结点定义如下：


typedef char BTDataType; // 使用typedef关键字给char类型取了一个别名BTDataType
 
typedef struct BTNode // 使用struct关键字定义了一个名为BTNode的结构体
{
    BTDataType data;        // 二叉树节点的数据域，用于存储具体的数据值
    struct BTNode* left;    // 二叉树节点的左子节点指针，指向左子节点
    struct BTNode* right;   // 二叉树节点的右子节点指针，指向右子节点
} BTNode;   // 使用BTNode作为该结构体类型的别名

二、二叉树的遍历

按照前序序列构建二叉树

在对二叉树进行遍历之前我们先对通过前序遍历的数组"ABD##E#H##CF##G##"构建一颗二叉树。注意：'#' 字符代表该节点为空。


// 前序建立二叉树的函数
BTNode* CreateBinaryTreePre(BTDataType* a, int n, int* pi)
{
    // 如果数组索引超出数组长度，返回空指针
    if (*pi >= n)
    {
        return NULL;
    }
    
    // 如果当前位置的值为 '#'，表示当前位置为空节点，将数组索引向后移动，并返回空指针
    if (a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    
    // 动态分配一个新的二叉树节点
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    
    // 如果内存分配成功
    if (root)
    {
        // 将当前位置的值存储到新节点的数据域中
        root->data = a[(*pi)++];
        
        // 递归调用CreateBinaryTreePre函数，构建新节点的左子树
        root->left = CreateBinaryTreePre(a, n, pi);
        
        // 递归调用CreateBinaryTreePre函数，构建新节点的右子树
        root->right = CreateBinaryTreePre(a, n, pi);
    }
    else
    {
        // 如果内存分配失败，打印错误信息并退出程序
        perror("malloc fail!");
        exit(-1);
    }
    
    return root;  // 返回根节点
}
 
// 主函数
int main()
{
    BTNode* root;   // 定义二叉树的根节点指针
    BTDataType a[] = { 'A','B','D','#','#',
                      'E','#','H','#','#','C','F','#','#','G','#','#' ,'\0' };
    int n = strlen(a);
    int pi = 0;   // 定义一个变量用于追踪数组的索引位置
    
    // 调用CreateBinaryTreePre函数，传入数组a、数组长度n和索引位置的指针pi，
    //生成二叉树，并返回根节点指针
    root = CreateBinaryTreePre(a, n, &pi);
    
    return 0;
}

1、前 (先) 序遍历(Preorder Traversal )

访问根结点的操作发生在遍历其左右子树之前——即： 根节点 -> 左子树 -> 右子树。

前序遍历二叉树的算法可以按照如下的步骤实现：

如果二叉树为空，直接返回。
访问当前节点，即输出当前节点的值。
对当前节点的左子树进行前序遍历。
对当前节点的右子树进行前序遍历。

我们如何理解遍历顺序呢？博主在这里分享一下自己的方法：

对于一棵二叉树，我们先找到其根节点，打印出根结点的值后，我们对其左子树进行遍历。由于一颗二叉树可以划分出许多子树，那么遍历左子树时我们即可将当前节点（即根结点的左孩子结点）看作左子树的根结点，然后对当前子树再进行根节点 -> 左子树 -> 右子树 的遍历方法，如果当前结点为空，返回上一层递归。在当前根节点的左子树遍历完成时我们再对右子树进行遍历，如此循环往复，直至遍历完整棵树停止。

简而言之，就是当遍历到一个新结点时，把当前结点当作根节点，接着去遍历当前结点的左右子树。进入下一个子树遍历时，继续把当前结点当作根节点，如此循环往复下去，直至遇到空结点，递归开始回溯。

前序遍历动态过程图：

下面是前序遍历的递归图解：

前序遍历代码及注释：


// 前序遍历二叉树
void PrintPreOrder(BTNode* root)
{
    // 如果当前节点为空，返回
    if (!root)
    {
        return;
    }
    
    // 打印当前节点的值
    printf("%c ", root->data);
    
    // 递归遍历左子树
    PrintPreOrder(root->left);
    
    // 递归遍历右子树
    PrintPreOrder(root->right);
}

2. 中序遍历(Inorder Traversal)

访问根结点的操作发生在遍历其左右子树之中（间）——即： 左子树 --> 根节点 --> 右子树。

中序遍历二叉树的算法可以按照如下步骤实现：

如果二叉树为空，直接返回。
对当前节点的左子树进行中序遍历。
访问当前节点，即输出当前节点的值。
对当前节点的右子树进行中序遍历。

对于中序遍历，我们采取类似的方法。当我们遍历时，将当前结点当作子树的根节点，先去寻找该根节点有没有左孩子，如果有，我们就向左进行遍历，当到达新结点时，我们依旧将其看作根节点去寻找该结点的左孩子，如果当前结点为空，再回溯到其父结点打印数据，再去寻找它的右孩子。当当前子树遍历完成时，我们回溯到此子树根节点的上一层的节点，打印节点数据，之后再去找该结点的右孩子。如此循环往复，直至遍历完整棵树停止。

中序遍历动态过程图：

中序遍历代码及注释：


// 中序遍历
void PrintInOrder(BTNode* root)
{
    // 如果当前节点为空，即已经到达叶子节点或者是空树的情况，直接返回
    if (!root)
    {
        return;
    }
  
    // 递归调用中序遍历函数，遍历左子树
    PrintInOrder(root->left);
  
    // 打印当前节点的数据
    printf("%c ", root->data);
  
    // 递归调用中序遍历函数，遍历右子树
    PrintInOrder(root->right);
}

3. 后序遍历(Postorder Traversal)

访问根结点的操作发生在遍历其左右子树之后——即： 左子树 -->右子树 --> 根节点。

后序遍历二叉树的算法可以按照如下的步骤实现：

如果二叉树为空，直接返回。
对当前节点的左子树进行后序遍历。
对当前节点的右子树进行后序遍历。
访问当前节点，即输出当前节点的值。

对于后序遍历，我们依然按照之前的方法。当我们遍历时，将当前结点当作子树的根节点，先去寻找该根节点有没有左孩子，如果有，我们就向左进行遍历，直至树的底部；如果当前结点为空，返回上一层递归，再去判断当前节点有没有右孩子，如果有我们再向右遍历，重复上面的过程。当当前子树左右孩子遍历完后，我们回退至子树的根结点打印数据。如此循环往复，直至遍历完整棵树停止。

后序遍历动态过程图：

后序遍历代码及注释：


// 后序遍历
void PrintPostOrder(BTNode* root)
{
    // 如果当前节点为空，直接返回
    if (!root)
    {
        return;
    }
  
    // 递归调用后序遍历函数，遍历左子树
    PrintPostOrder(root->left);
  
    // 递归调用后序遍历函数，遍历右子树
    PrintPostOrder(root->right);
  
    // 打印当前节点的数据
    printf("%c ", root->data);
}

4、层序遍历

层序遍历是二叉树中最常用的遍历方法之一，它依次按层遍历二叉树中的结点。

具体实现思路如下：

创建一个队列，将根节点插入队列中。
取出队列的首个节点，访问该节点。
若该节点有左子节点，将左子节点插入队列中。
若该节点有右子节点，将右子节点插入队列中。
重复步骤 2 ~ 4，直到队列为空为止。

层序遍历代码及注释：


typedef char BTDataType;  // 二叉树中每个节点所存储的数据类型为 char
 
typedef struct BTNode
{
	BTDataType data;  // 节点存储的数据
	struct BTNode* left;  // 左子节点
	struct BTNode* right;  // 右子节点
}BTNode;  // 定义二叉树结构体
 
typedef BTNode* QueueDataType;  // 队列中每个节点所存储的数据类型为 BTNode 指针
 
typedef struct QNode
{
	QueueDataType val;  // 节点存储的数据
	struct QNode* next;  // 指向下一个节点的指针
}QNode;  // 定义队列节点结构体
 
typedef struct Queue
{
	QNode* front;  // 队头指针
	QNode* rear;  // 队尾指针
	int size;  // 队列中元素的个数
}Queue;  // 定义队列结构体
 
// 初始化队列
void QueueInit(Queue* q)
{
    assert(q);
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}
 
// 入队
void QueuePush(Queue* q, QueueDataType x)
{
    assert(q);
    QNode* temp = (QNode*)malloc(sizeof(QNode));
    if (temp == NULL)
    {
        perror("malloc fail!");
        exit(-1);
    }
    temp->val = x;
    temp->next = NULL;
    if (q->front == NULL)
    {
        q->front = q->rear = temp;  // 队列为空时，新元素既是队头也是队尾
    }
    else
    {
        q->rear->next = temp;  // 把新元素连接到队尾后
        q->rear = temp;  // 更新队尾指针为新的元素
    }
    q->size++;  // 队列元素个数加1
}
 
// 判断队列是否为空
bool QueueEmpty(Queue* q)
{
    assert(q);
    if (q->front == NULL)
    {
        return true;  // 队列为空
    }
    return false;  // 队列不为空
}
 
// 获取队头元素
QueueDataType QueueTop(Queue* q)
{
    assert(q);
    if (!QueueEmpty(q))
    {
        return q->front->val;  // 返回队头元素的值
    }
    else
    {
        printf("队空，无法获取队头元素！\n");
        exit(-1);
    }
}
 
// 出队
void QueuePop(Queue* q)
{
    assert(q);
    if (!QueueEmpty(q))
    {
        QNode* temp = q->front;  // 保存队头指针
        q->front = q->front->next;  // 移动队头指针到下一个元素
        free(temp);  // 释放原队头节点的内存空间
        q->size--;  // 队列元素个数减1
    }
    else
    {
        printf("队空，无法删除队头元素！\n");
        exit(-1);
    }
}
 
// 获取队列元素个数
int QueueSize(Queue* q)
{
    assert(q);
    return q->size;  // 返回队列元素个数
}
 
// 二叉树的层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
    assert(root);
    Queue q;
    QueueInit(&q);  // 初始化队列
    QueuePush(&q, root);  // 将根节点入队
    int TSize = 1;
    while (!QueueEmpty(&q))
    {
        // 遍历当前层级的结点
        while (TSize > 0)
        {
            BTNode* cur = QueueTop(&q);  // 获取队头元素
            QueuePop(&q);  // 出队
            printf("%c ", cur->data);  // 输出当前结点的数据
            if (cur->left)
            {
                QueuePush(&q, cur->left);  // 左子节点入队
            }
            if (cur->right)
            {
                QueuePush(&q, cur->right);  // 右子节点入队
            }
            TSize--;  // 减少当前层级元素个数
        }
        printf("\n");  // 输出换行符表示当前层级遍历结束
        TSize = QueueSize(&q);  // 更新当前层级元素个数
    }
}

三、二叉树总结点个数

算法思路：

如果当前节点为空，则返回0。
如果当前节点非空，则递归计算其左子树节点个数、右子树节点个数以及当前节点本身，然后将它们累加起来，即可得到整棵树的节点个数。


// 二叉树的节点个数
int BinaryTreeSize(BTNode* root)
{
    // 如果当前节点为空，则返回0，表示节点个数为0
	if (root == NULL)
	{
		return 0;
	}
    // 如果当前节点非空，则递归计算左子树节点个数、右子树节点个数以及当前节点本身的个数
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

四、二叉树叶子结点个数

算法思路：

如果当前节点为空，则说明当前二叉树为空，返回0。
如果当前节点的左右子节点都为空，即为叶子节点，则返回1。
否则，递归计算当前节点的左子树和右子树中叶子节点的个数，然后将它们相加得到整棵树的叶子节点个数。


// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
    // 如果当前节点为空，则返回0
	if (root == NULL)
	{
		return 0;
	}
    // 如果当前节点的左右子节点都为空，即为叶子节点，则返回1
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
    // 否则，递归计算当前节点的左子树和右子树中叶子节点的个数，然后将它们相加得到整棵树的叶子节点个数
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

五、二叉树第k层的结点个数

注意：设根节点所在层数为第一层

算法思路：

如果当前节点为空，则说明当前二叉树为空，返回0。
如果当前层数k为1，并且当前节点非空，则返回1，表示当前节点是第一层中唯一的节点。
否则，递归计算当前节点的左子树和右子树在第k-1层的节点个数，然后将它们相加得到第k层的节点个数。


// 二叉树第k层的结点个数
int BinaryTreeLevelSize(BTNode* root, int k)
{
    // 如果当前节点为空，则返回0，因为当前节点所在的树一定为空树
	if (root == NULL)
	{
		return 0;
	}
    // 如果当前层数k为1，并且当前节点非空，则返回1，表示当前节点是第一层中唯一的节点
	if (k == 1 && root != NULL)
	{
		return 1;
	}
    // 否则，递归计算当前节点的左子树和右子树在第k-1层的节点个数，然后将它们相加得到第k层的节点个数
	return BinaryTreeLevelSize(root->left, k - 1) + BinaryTreeLevelSize(root->right, k - 1);
}

六、二叉树的最大高度

算法思路：

如果当前节点为空，则说明当前二叉树为空，返回0。
否则，递归计算当前节点的左子树的高度和右子树的高度，并取其中较大值。
将较大值加1，表示当前节点所在的子树的高度，并将结果返回。


// 二叉树的最大高度
int BinaryTreeHeight(BTNode* root)
{
    // 如果当前节点为空，则返回0
	if (root == NULL)
	{
		return 0;
	}
 
    // 递归计算当前节点的左子树的高度和右子树的高度
	int left = 1 + BinaryTreeHeight(root->left);
	int right = 1 + BinaryTreeHeight(root->right);
 
    // 取左右子树的最大值，返回最大高度
	return left > right ? left : right;
}

七、在二叉树中查找值为x的结点

算法思路：

如果当前节点为空，则说明当前二叉树为空，返回false。
如果当前节点的值等于x，则找到了目标节点，返回true。
否则，分别在当前节点的左子树和右子树中递归查找值为x的节点，只要有一棵子树找到了目标节点，就返回true。
如果在整棵树中都没有找到目标节点，最终返回false。


// 在二叉树中查找值为x的节点
bool BinaryTreeSearch(BTNode* root, BTDataType x)
{
    // 如果当前节点为空，则返回false
	if (root == NULL)
	{
		return false;
	}
    // 如果当前节点的值等于x，则找到了目标节点，返回true
	if (root->data == x)
	{
		return true;
	}
    // 在当前节点的左子树和右子树中递归查找值为x的节点，只要有一棵子树找到了目标节点，就返回true
	return BinaryTreeSearch(root->left, x) || BinaryTreeSearch(root->right, x);
}

八、销毁二叉树

算法思路：

如果当前节点为空，则说明当前二叉树为空，直接返回。
否则，先递归销毁当前节点的左子树，再递归销毁当前节点的右子树。
最后，销毁当前节点，即释放当前节点的内存空间，回溯至上一层节点。


// 销毁二叉树
void DestroyBinaryTree(BTNode* root)
{
    // 如果当前节点为空，则直接返回
    if (!root)
    {
        return;
    }
    // 递归销毁当前节点的左子树
    DestroyBinaryTree(root->left);
    // 递归销毁当前节点的右子树
    DestroyBinaryTree(root->right);
    // 销毁当前节点，即释放当前节点的内存空间，回溯至上一层节点。
    free(root);
}

完整测试代码：


#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<stdbool.h>
 
typedef char BTDataType;
 
typedef struct BTNode
{
	BTDataType data;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;
 
typedef BTNode* QueueDataType;
 
typedef struct QNode
{
	QueueDataType val;
	struct QNode* next;
}QNode;
 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
	int size;
}Queue;
 
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* CreateBinaryTreePre(BTDataType* a, int n, int* pi);
//前序遍历
void PrintPreOrder(BTNode* root);
//中序遍历
void PrintInOrder(BTNode* root);
//后序遍历
void PrintPostOrder(BTNode* root);
//层次遍历
void BinaryTreeLevelOrder(BTNode* root);
//销毁二叉树
void DestoryBinaryTree(BTNode* root);
//初始化队列
void QueueInit(Queue* q);
//入队
void QueuePush(Queue* q, QueueDataType x);
//判断队列是否为空
bool QueueEmpty(Queue* q);
//获取队头元素
QueueDataType QueueTop(Queue* q);
//获取队列元素个数
int QueueSize(Queue* q);
//出队
void QueuePop(Queue* q);
//二叉树的节点个数
int BinaryTreeSize(BTNode* root);
//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
//二叉树的最大高度
int BinaryTreeHeight(BTNode* root);
//二叉树第k层的结点个数
int BinaryTreeLevelSize(BTNode* root, int k);
//在二叉树中查找值为x的结点
bool BinaryTreeSearch(BTNode* root, BTDataType x);
 
//前序建立二叉树
BTNode* CreateBinaryTreePre(BTDataType* a, int n, int* pi)
{
	if (*pi >= n)
	{
		return NULL;
	}
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root)
	{
		root->data = a[(*pi)++];
		root->left = CreateBinaryTreePre(a, n, pi);
		root->right = CreateBinaryTreePre(a, n, pi);
	}
	else
	{
		perror("malloc fail!");
		exit(-1);
	}
	return root;
}
//前序遍历
void PrintPreOrder(BTNode* root)
{
	if (!root)
	{
		return;
	}
	printf("%c ", root->data);
	PrintPreOrder(root->left);
	PrintPreOrder(root->right);
}
 
//中序遍历
void PrintInOrder(BTNode* root)
{
	if (!root)
	{
		return;
	}
	PrintInOrder(root->left);
	printf("%c ", root->data);
	PrintInOrder(root->right);
}
 
//后序遍历
void PrintPostOrder(BTNode* root)
{
	if (!root)
	{
		return;
	}
	PrintPostOrder(root->left);
	PrintPostOrder(root->right);
	printf("%c ", root->data);
}
//销毁二叉树
void DestoryBinaryTree(BTNode* root)
{
	if (!root)
	{
		return;
	}
	DestoryBinaryTree(root->left);
	DestoryBinaryTree(root->right);
	free(root);
	root = NULL;
}
 
//初始化队列
void QueueInit(Queue* q)
{
	assert(q);
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}
 
//入队
void QueuePush(Queue* q, QueueDataType x)
{
	assert(q);
	QNode* temp = (QNode*)malloc(sizeof(QNode));
	if (temp == NULL)
	{
		perror("malloc fail!");
		exit(-1);
	}
	temp->val = x;
	temp->next = NULL;
	if (q->front == NULL)
	{
		q->front = q->rear = temp;
	}
	else
	{
		q->rear->next = temp;
		q->rear = temp;
	}
	q->size++;
}
 
//判断队列是否为空
bool QueueEmpty(Queue* q)
{
	assert(q);
	if (q->front == NULL)
	{
		return true;
	}
	return false;
}
 
//获取队头元素
QueueDataType QueueTop(Queue* q)
{
	assert(q);
	if (!QueueEmpty(q))
	{
		return q->front->val;
	}
	else
	{
		printf("队空，无法获取队头元素！\n");
		exit(-1);
	}
}
 
//出队
void QueuePop(Queue* q)
{
	assert(q);
	if (!QueueEmpty(q))
	{
		QNode* temp = q->front;
		q->front = q->front->next;
		free(temp);
		q->size--;
	}
	else
	{
		printf("队空，无法删除队头元素！\n");
		exit(-1);
	}
}
 
//获取队列元素个数
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
 
//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	assert(root);
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	int TSize = 1;
	while (!QueueEmpty(&q))
	{
		while (TSize > 0)
		{
			BTNode* cur = QueueTop(&q);
			QueuePop(&q);
			printf("%c ", cur->data);
			if (cur->left)
			{
				QueuePush(&q, cur->left);
			}
			if (cur->right)
			{
				QueuePush(&q, cur->right);
			}
			TSize--;
		}
		printf("\n");
		TSize = QueueSize(&q);
	}
}
 
//二叉树的节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 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);
}
 
//二叉树的最大高度
int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = 1 + BinaryTreeHeight(root->left);
	int right =1 + BinaryTreeHeight(root->right);
	return left > right ? left : right;
}
 
//二叉树第k层的结点个数
int BinaryTreeLevelSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1 && root != NULL)
	{
		return 1;
	}
	return BinaryTreeLevelSize(root->left, k - 1) + BinaryTreeLevelSize(root->right, k - 1);
}
 
//在二叉树中查找值为x的结点
bool BinaryTreeSearch(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return false;
	}
	if (root->data == x)
	{
		return true;
	}
	return BinaryTreeSearch(root->left, x) || BinaryTreeSearch(root->right, x);
}
 
int main()
{
	BTNode* root;
	BTDataType a[] = { 'A','B','D','#','#',
		'E','#','H','#','#','C','F','#','#','G','#','#' ,'\0' };
	int n = strlen(a);
	int pi = 0;
	root = CreateBinaryTreePre(a, n, &pi);
	BinaryTreeLevelOrder(root);
	printf("\n");
	int x;
	x = BinaryTreeSize(root);
	printf("TreeSize:%d\n", x);
	x = BinaryTreeLeafSize(root);
	printf("LeafSize:%d\n", x);
	x = BinaryTreeHeight(root);
	printf("Height:%d\n", x);
	x = BinaryTreeLevelSize(root, 3);
	printf("SizeK:%d\n", x);
	bool y;
	y = BinaryTreeSearch(root, 'Z');
	if (y)
	{
		printf("find\n");
	}
	else
	{
		printf("not find\n");
	}
	DestoryBinaryTree(root);
	return 0;
}

总结：

学会二叉树最重要的是深刻了解递归的过程。这就要求我们再学习二叉树的时候要多动手画图，理解递归是如何进行的，以及如何准确地甚至递归的终止条件。

本文在前、中、后序遍历中掺杂了许多个人见解。如果有小伙伴有更好的方法和见解，欢迎在评论区留言分享。

本文涵盖了链式二叉树的基本操作，从编写代码到博客的完成花了一个晚上，其中可能仍有不足。博客中的代码本人已经进行过测试。如果内容有的错误，欢迎各位小伙伴指出。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/718346

【数据结构】二叉树的基本操作大全，学会二叉树基本操作这一篇就够了：二叉树前序、中序、后序、层次遍历；求二叉树总结点个数，叶子结点个数，二叉树第k层的结点个数；求二叉树的高度；在二叉树中查找值为x的结点

一、二叉树的定义

1、二叉树的定义

2、二叉树的五种形态

二叉树的子树 ：

3、满二叉树与完全二叉树

4、二叉树的性质

5、二叉树的存储结构

1、顺序存储

2、链式存储

二、二叉树的遍历

按照前序序列构建二叉树

1、前 (先) 序遍历(Preorder Traversal )

前序遍历动态过程图：

下面是前序遍历的递归图解：

前序遍历代码及注释 ：

2. 中序遍历(Inorder Traversal)

中序遍历动态过程图：

中序遍历代码及注释：

3. 后序遍历(Postorder Traversal)

后序遍历动态过程图：

后序遍历代码及注释：

4、层序遍历

层序遍历代码及注释：

三、二叉树总结点个数

四、二叉树叶子结点个数

五、二叉树第k层的结点个数

六、二叉树的最大高度

七、在二叉树中查找值为x的结点

八、销毁二叉树

算法思路：

完整测试代码：

总结：

二叉树的子树：

前序遍历代码及注释：