目录
一、二叉树的实现
前面我们已经说过了二叉树的定义与概念，现在我们讨论的是如何实现二叉树。
在二叉树中我们不仅无法确定其具体的孩子数，也无法确定其具体节点数。那该如何实现，那不就是无从下手吗？非也，咱们想不到，自有人会想到，这里，我们实现的思路为：左孩子、右兄弟表示法。即：根左边指向它的左孩子，右边指向它左孩子的兄弟也就是右孩子，这样不就表示出来了。可借助以下代码理解：
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
运用此方法，我们可较为方便的表示出各个节点之间的关系。我们现在能用到这样的方法就是因为：我们是站在巨人的肩膀上。
了解了二叉树的大逻辑后，我们现在要开始研究二叉树的细枝末节了。
1.1 二叉树的前序遍历
我们在用代码实现前，我们要先明白，什么是遍历？什么是前序遍历？
所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。
所谓的前序遍历即：二叉树沿着：根，左子树，右子树的顺序进行遍历。
我们已明白其实现逻辑，现在开始用代码实现吧！
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
return;//此处也可打印N
}
printf("%d", root->data);//按照前序遍历顺序：根
BinaryTreePrevOrder(root->left);//左子数
BinaryTreePrevOrder(root->right);//右子数
} 
上面帮助大家理解以下此代码。总之：记住顺序：根，左子树，右子树。
1.2 二叉树的中序遍历
在理解了前序遍历后，中序遍历也可以理解。中序遍历和前序遍历并无本质区别，只是顺序变换了一下，即：左子树，根，右子树。代码实现如下：
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreeInOrder(root->left);
printf("%d ", root->data);
BinaryTreeInOrder(root->right);//无不一样之处，只是交换了顺序
}1.3 二叉树的后续遍历
后续遍历的遍历顺序为：左子树，右子树，根。其余思路还是一致。代码实现如下：
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%d ", root->data);
}1.4 二叉树的节点个数
接下来，我们学习如何求二叉树的节点个数。
假如，你们学校有一个校长，两个院长，四个辅导员，八个班长。校长接到通知，要求统计在校师生人数，你觉得，校长会怎么干？是哪一个小本本，一个一个统计：计算机学院多少人，软件学院多少人，还是把他的左膀右臂——两个院长叫过来。答案显然易见，肯定会摇人，院长见校长这么想，肯定也会叫导员，层层外包，最后，班长成苦命的打工人。
统计节点个数的思路与上文类似，都是层层分封然后加上自己即可。代码实现如下：
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}1.5 二叉树叶子节点个数
此问题我们可不可以运用上题的思路解决，当然可以。实现代码如下：
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);
}这里的实现思路只不过换成只要是叶节点就放回一。
1.6 二叉树查找值为x的节点
相信有一部分人看到此题，说：“简单”。然后写出以下代码：
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
return BinaryTreeFind(root->left,x);
return BinaryTreeFind(root->right,x);
}这个代码乍一看，大逻辑好像是对的，其实不然，如果，左子树，能够找到，那最好了。但，右子树和部分左子树根本找不到。为啥？一个函数是不是只有一个返回值，结构体可以有多个。既然只有一个，那么注定只能放回一个，其余的哪怕是找到了也会没找到，无法得用。
优化后代码如下：
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode*p1 = BinaryTreeFind(root->left,x);
if (p1)
{
return p1;
}
BTNode* p2 = BinaryTreeFind(root->right,x);//分别用指针记录，找到才返回
if (p2)
{
return p2;
}
return NULL;
}1.7 二叉树第k层节点个数
求第k层高度，各位读者有没有思路。这里的难点为：如何找到该层。只要能找到，统计节点，那都会，对吧。
这里提供一种想法，仅供参考：每一次使k--，叫k的值和一比。如果等于一，则到了要找的层，不为一就继续，没有就返回0。代码实现思路如下：
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);
}1.8 二叉树的高度
我们在这里想，如何求出二叉树的高度呢？是不是可以转换成左子树和右子树谁更高的问题。谁高就加一，对吧。来先看以下代码：
int TreeHight(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return TreeHight(root->left) > TreeHight(root->right) ?
TreeHight(root->left) + 1 : TreeHight(root->right) + 1;
}这代码，从逻辑和结果上来看，没啥问题。但，复杂度太高。
咱们的想法是运用递归实现，本题中的代码，没有一个记录的，本次用完，别人想用，就忘记了，就要重新调。读者可能认为是2倍的关系。其实不然，我用故事来解释一下：
当班长把统计的人数告诉导员时候，导员说：知道了，你回去吧。走到半路，接到电话，导员说：你在来一下，我给院长汇报时忘记了。班长去汇报，回来。又去为啥：院长统计时又忘记了，又去，又回来，没完没了了，可用下图表示：
从此图可以看出复杂度是很高的，越是底层，干的就越多。所以，我们可做以下优化：
int TreeHight(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int left = TreeHight(root->left);
int right = TreeHight(root->right);
return left > right ?
left + 1 : right + 1;
}1.9 二叉树的销毁
二叉树的销毁其实传不传二级指针都行，不传的话，只需在调用后，手动置空即可。
void TreeDestory(BTNode* root)
{
if (root == NULL)
return;
TreeDestory(root->left);
TreeDestory(root->right);
free(root);
}二、二叉树的层序遍历
以上我们已经明白了二叉树的基本结构的实现。接下来，我们来思考一件事如何实现二叉树的层序遍历。
首先，我们要说一下何为层序遍历？顾名思义，层序遍历即：一层一层的遍历每个节点即可。
明白了我们要做的事情，那我们应该如何去完成？大家可能第一时间想到的是递归，毕竟二叉树就是递归实现的。那么？层序遍历用递归可行吗？好像有点不太可行。因为你要顺序的访问每一个节点，递归实现好像有点困难。那我们能否转变思路，这个要求的是层序遍历，那么？我们能否借助数组或链表一个一个把它们放入到该结构中。在我们学习中，符合该结构又符合先进先出的只有那一种结构了——队列！
那，我们能否借助队列实现，当然可以。实现思路如下：
队列该数据结构特点为：先进先出。我们可以先把根节点放入，我们把它放入后这时叫他出队，出队的同时把它的左右护法放入，对每个节点都进行该操作，直到节点为空。
这里强调一点：存放数据的类型为 struct BinaryTreeNode* 类型，这样才能存储。实现代码如下：
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front->left)
{
QueueFront(front->left);
}
if (front->right)
{
QueueFront(front->right);
}
}
}这时 ，读者可能会有以下问题：这里pop掉q，那front能找到它的左右护法吗？大家想一想。答案是：不影响。就好比：你们抓鲁迅管我周树人什么事？（bushi） 你们看咱们只是改变q此时的指向，二叉树的节点全放在队列里面，队列里面pop并不影响你这个二叉树的结构。原来的关系没有改变，故可以找到。
那有人可能要问了？那它们不是指向同一块地址吗？这种思维有点不太正确。队列中存储的是树节点的指针，而不是节点本身。当从队列中弹出一个节点时，只是移除了节点指针在队列中的位置，不会影响树结构或树中的节点
三、判断二叉树是否是完全二叉树
学习完如何遍历了，我们现在来学习如何判断二叉树是否为完全二叉树。
我们对其有何实现思路。递归？然后用节点范围来判断？听起来似乎可行，但又不可行。为何？
如图的二叉树就无法用此方法来判断。 现在似乎陷入了僵局，该如何处理？我们可否参考上图的结构，每一个入队列，遇到空截止。然后再继续层序遍历，遇到不为空的返回false，一直为空返回true。思路上是可行的，如果上图的二叉树再接一个节点会进队列吗？答案很明显：不会。但是，影响吗？不影响？因为我们通过以上就可以判断出它不为完全二叉树了，那最后一个进不进又区别吗？所以，我们代码实现思路不就出来了？代码实现如下：
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueueFront(&q);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
{
break;
}
if (front->left)
{
QueueFront(front->left);
}
if (front->right)
{
QueueFront(front->right);
}
}
while (!QueueEmpty(&q))
{
QNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
{
return false;
}
}
return true;
}四、代码展示
BTNode.h
#pragma once
#include<stdio.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
//求二叉树高度
int TreeHight(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
BTNode.c
#include"BTNode.h"
//二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
return;//此处也可打印N
}
printf("%d", root->data);//按照前序遍历顺序：根
BinaryTreePrevOrder(root->left);//左子数
BinaryTreePrevOrder(root->right);//右子数
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreeInOrder(root->left);
printf("%d ", root->data);
BinaryTreeInOrder(root->right);//无不一样之处，只是交换了顺序
}
//二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%d ", root->data);
}
// 二叉树节点个数
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);
}
// 二叉树第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);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode*p1 = BinaryTreeFind(root->left,x);
if (p1)
{
return p1;
}
BTNode* p2 = BinaryTreeFind(root->right,x);//分别用指针记录，找到才返回
if (p2)
{
return p2;
}
return NULL;
}
//求二叉树高度
int TreeHight(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int left = TreeHight(root->left);
int right = TreeHight(root->right);
return left > right ?
left + 1 : right + 1;
}
// 二叉树销毁
void TreeDestory(BTNode* root)
{
if (root == NULL)
return;
TreeDestory(root->left);
TreeDestory(root->right);
free(root);
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front->left)
{
QueueFront(front->left);
}
if (front->right)
{
QueueFront(front->right);
}
}
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueueFront(&q);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
{
break;
}
if (front->left)
{
QueueFront(front->left);
}
if (front->right)
{
QueueFront(front->right);
}
}
while (!QueueEmpty(&q))
{
QNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
{
return false;
}
}
return true;
}Queue.h
#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
typedef struct BinaryTreeNode* QDataType;
// 链式结构：表示队列
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* phead;
QNode* ptatil;
int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
Queue.c
#include"Queue.h"
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->phead = q->ptatil = NULL;
q->size = 0;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = data;
newnode->next = NULL;
if (q->phead == NULL)
{
q->phead = q->ptatil = newnode;
}
else
{
q->ptatil->next = newnode;
q->ptatil = newnode;
}
q->size++;
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->size > 0);
if (q->phead->next == NULL)
{
q->phead = q->ptatil = NULL;
}
else
{
QNode* tmp = q->phead->next;
free(q->phead);
q->phead = tmp;
}
q->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->phead);
return q->phead->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->ptatil);
return q->ptatil->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* tmp = q->phead;
while (tmp)
{
QNode* next = tmp->next;
free(tmp);
tmp = next;
}
}
最后
以上，便是我所有说的二叉树的大部分内容了，剩下的部分会在明天我为大家准备的练习题中进行讲解。如果今天讲出来，不太利于大家的理解。希望大家能把今天讲的知识拿去练习，好好理解巩固一下，我们明天再会！
完！