目录
1前置说明
下文将链式二叉树简称为二叉树
学习二叉树首先需要创建一棵二叉树，但初学者直接学习二叉树的创建方式，难度可谓是从入门到入土，所以下面先手动创建一棵二叉树，了解二叉树的部分操作后再回过头来研究二叉树真正的创建方式
typedef int BTDataType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BTDataType val;
}BTNode;
BTNode* BuyBTNode(BTDataType val)
{
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
if (!root)
{
perror("malloc fail");
return NULL;
}
root->left = NULL;
root->right = NULL;
root->val = val;
return root;
}
BTNode* CreateBinaryTree()
{
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;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}(1)上述代码重命名了 int 类型，方便后续更改数据类型
(2)一棵二叉树的一个节点包含：储存变量val，左右孩子节点指针left、right
(3)BuyBTNode函数在堆上开辟空间，并初始化每个节点
(4)CreateBinaryTree函数手动创建了一棵二叉树，并返回根节点指针。如下图：
2.二叉树的遍历
2.1前序、中序、后序遍历
1. 前序遍历(先序遍历、先根遍历)——访问根结点的操作发生在遍历其左右子树之前
即 根 左子树 右子树
2. 中序遍历(中根遍历)——访问根结点的操作发生在遍历其左右子树之中（间）
即 左子树 根 右子树
3. 后序遍历(后根遍历)——访问根结点的操作发生在遍历其左右子树之后
即 左子树 右子树 根
由于遍历访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）可解释为 根、根的左子树和根的右子树。NLR、LNR和LRN分别称为先根遍历、中根遍历和后根遍历
//根 左 右
void PrevOrder(BTNode* root){
if (!root){
printf("NULL ");
return;}
printf("%d ", root->val);
PrevOrder(root->left);
PrevOrder(root->right);
}
// 左 根 右
void InOrder(BTNode* root){
if (!root){
printf("NULL ");
return;}
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}
// 左 右 根
void PostOrder(BTNode* root){
if (!root){
printf("NULL ");
return;}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}
三种遍历实现方式及运行结果如上
以前序遍历为例，下面通过递归展开图，更好体会遍历的过程
如上图
调用PrevOrder函数并传入根节点(节点存储值为1)的指针，指针不为空，打印节点值，然后递归调用PrevOrder函数访问根节点的左子树(节点存储值为2)，指针不为空，打印节点值，然后递归调用PrevOrder函数访问当前节点的左子树(节点存储值为3)，指针不为空，打印节点值，然后递归调用PrevOrder函数访问当前节点的左子树,指针为空，函数返回，开始访问值为3的节点的右子树，指针为空，函数返回，开始访问值为2的节点的右孩子，指针为空，函数返回，开始访问值为1的节点的右子树，.........
上诉过程中，打印节点值、函数返回就是遍历访问节点的一种方式
首先访问根节点，然后是根节点的左子树，左子树又是由根、左子树、右子树构成的，所以先访问根，再访问根的左子树的左子树，左子树又是由根、左子树、右子树构成的，所以先访问根，再访问根的左子树的左子树的左子树，此时为空树，该方向的遍历停止，开始访问根的左子树的左子树的右子树，此时为空树，该方向的遍历停止，开始访问根的左子树的右子树，此时为空树，该方向的遍历停止，开始访问根的右子树...........
前中后序的遍历落实到了递归上，可根据下图再理解理解
三种遍历的本质差异在于访问根节点的时机
2.2层序遍历
顾名思义，层序遍历就是一层一层的访问二叉树的节点(先第一层，再第二层......)
这里需要用到前面队列的特性，首先树为空直接返回，否则，从根节点开始，将节点的指针
(不为空)入队，然后在出队的同时，将该节点的左右孩子节点入队，队列为空时就停止
如上图所示，(以节点存储值代替节点指针说明)
1入队，1出队，同时2、4入队；2出队，同时3入队(2的右孩子为空，没必要入队);4出队，同时5、6入队；3出队(左右孩子为空，没必要入队)，5出队(左右孩子为空，没必要入队)，6出队(左右孩子为空，没必要入队)，停止
void LevelOrder(BTNode* root){
if (!root)
return;
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q)){
BTNode* Front = QueueFront(&q);
QueuePop(&q);
//if (Front)
//第一次插入的树节点指针不为空
//第一次可以放心打印，后续控制不进空，就直接打印
printf("%d ", Front->val);
//空没有必要进，
if (Front->left)
QueuePush(&q, Front->left);
if (Front->right)
QueuePush(&q, Front->right);}
QueueDestroy(&q);}(1)树为空，直接返回，否则初始化队列，并将根节点指针入队
(2)调用QueueFront函数拿到队首元素中存储的节点指针值，
然后出队，同时代入其不为空的孩子节点
(3)队列为空时停止，注意销毁队列，防止内存泄漏
3.节点个数
//左 + 右 + 1
int TreeSize(BTNode* root){
if (!root)
return 0;
return TreeSize(root->left) +
TreeSize(root->right) + 1;
}代码非常简洁，意思就是节点为空返回0，否则该棵树的节点个数等于
左子树的节点个数 + 右子树的节点个数 + 1
如上图
调用TreeSize函数并传入根节点(节点存储值为1)的指针，指针不为空，调用TreeSize函数计算节点(节点存储值为1)的左子树(根节点存储值为2)的节点个数，指针不为空，调用TreeSize函数计算节点(节点存储值为2)的左子树(根节点存储值为3)的节点个数，指针不为空，调用TreeSize函数计算节点(节点存储值为3)的左子树的节点个数,指针为空，函数返回0，开始计算节点存储值为3的节点的右子树的节点个数，指针为空，函数返回0，开始计算值为2的节点的右子树的节点个数，指针为空，函数返回0，开始计算值为1的节点的右子树的节点个数，.........
总结来说，这又是一次递归实战，重要的是求出递推公式，找到最小子问题及其结束条件
对于本题来说，
递推公式:
该棵树的节点个数等于左子树的节点个数 + 右子树的节点个数 + 1
最小子问题及其结束条件：
对于某一个节点，为空就返回0，不为空就套用递推公式
4.树的高度(根节点的高度为1)
//左右子树较高者 + 1
int TreeHeight(BTNode* root){
if (!root)
return 0;
int l = TreeHeight(root->left);
int r = TreeHeight(root->right);
return l > r ? l + 1 : r + 1;
}同样是递归实战，递推公式: 树高 = 左右子树较高者的高度 + 1
最小子问题及其结束条件：树为空就返回0，否则先分别计算左右子树的高度，再比较返回
以节点存储值代替节点指针进行说明
1不为空，先计算1的左子树(根节点存储值为2)的高度，2不为空，先计算2的左子树(根节点存储值为3)的高度，3不为空，先计算3的左子树的高度，树为空，返回0，再计算3的右子树的高度，树为空，返回0，比较返回1，(即2的左子树(根节点存储值为3)的高度),再计算2的右子树的高度，树为空，返回0，比较返回2，(即1的左子树(根节点存储值为2)的高度)，此时该树的左子树的高度计算完毕，开始计算其右子树的高度..........
5.树的第K层的节点个数 (层数大于0)
//左右子树第K - 1 层的节点个数之和
int TreeKLevel(BTNode* root, int k){
assert(k > 0);
if (!root)
return 0;
if (k == 1)
return 1;
return TreeKLevel(root->left, k - 1)
+ TreeKLevel(root->right, k - 1);
}递推公式: 树的第K层节点个数 = 左子树第 K - 1 层节点个数 + 右子树第 K - 1 层节点个数
最小子问题及其结束条件：对于某一节点，为空就返回0，不为空且所在层数(设为w)为1就返回1，否则需分别计算其左右子树第1+k - w层(不用手动计算，递归调用时，层数自动递减)的节点个数，再求和
以节点存储值代替节点指针进行说明
1不为空，先计算1的左子树(根节点存储值为2)第2层的节点个数，2不为空，先计算2的左子树(根节点存储值为3)第1层的节点个数，3不为空且层数为1，返回1，再计算2的右子树的第1层的节点个数，树为空，返回0，求和返回得到1的左子树的第2层的节点个数，此时该树的左子树的第2层的节点个数计算完毕，开始计算其右子树的第2层的节点个数..........
6.查找
// 自己 左右子树中找
BTNode* BinaryTreeFind(BTNode* root, BTDataType x){
if (!root)
return NULL;
if (root->val == x)
return root;
BTNode* left = BinaryTreeFind(root->left, x);
if (left)
return left;
BTNode* right = BinaryTreeFind(root->right, x);
if (right)
return right;
return NULL;
}在普通二叉树中查找某个值的思路：先在当前节点找，再到左右子树去找
最小子问题及结束条件就是，对于某一节点，如果为空，返回空，如果所存储值就是要找的值就返回该节点的指针，否则再去它的左右子树找，找不到就返回空
7.判别完全二叉树
层序遍历二叉树的节点指针(空树NULL也算)，可以发现
完全二叉树层序遍历的特点：不为空的节点指针连续
普通二叉树层序遍历的特点：为空的节点指针不连续
bool BinaryTreeComplete(BTNode* root)
{
if (!root)
return true;
//首先入队
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* Front = QueueFront(&q);
QueuePop(&q);
//空也入队
if (Front)
{
QueuePush(&q, Front->left);
QueuePush(&q, Front->right);
}
else
{
break;
}
}
//完全二叉树的空是连续的！！
while (!QueueEmpty(&q))
{
if (QueueFront(&q))
{
//注意资源清理
QueueDestroy(&q);
return false;
}
QueuePop(&q);
}
QueueDestroy(&q);
return true;
}(1)树为空，返回真，否则根节点指针入队
(2)取得队首元素的节点存储值，出队，然后代入该节点的左右孩子(如果有的话)
(3)没有左右孩子，说明遇到了第一个NULL节点，此时选择跳出循环，遍历队列中剩下的元素，如果存在队首元素的节点存储值不为空，返回false，并及时清理队列资源，遍历完成则意味着该树是完全二叉树，返回true，并及时清理队列资源
8.销毁二叉树
销毁一棵二叉树，第一想法就是遍历销毁，可选择哪种遍历方式呢？
先序遍历，直接就把根节点给销毁了，需要提前保存左右孩子节点
中序遍历，根节点会先于右孩子节点销毁了，需要提前保存右孩子节点
所以选择后序遍历，先销毁孩子节点再销毁根而无需提前保存孩子节点
void BinaryTreeDestory(BTNode** root)
{
//root一定不为空
assert(root);
if (!(*root))
return;
BinaryTreeDestory(&((*root)->_left));
BinaryTreeDestory(&((*root)->_right));
free(*root);
*root = NULL;
}最小子问题及其结束条件：节点为空即返回，否则先销毁它的孩子节点，再销毁自己
9.创建二叉树
通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
思路：遍历字符数组，遇到'#'(意味着空节点)就返回，否则就开辟一个节点的空间存储该值，
并用下一个字符所在的节点作为上一个字符所在节点的左孩子，......直到遇见'#'，左孩子方向创建完毕，开始创建右孩子节点
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
root->_data = a[(*pi)++];
root->_left = BinaryTreeCreate(a, pi);
root->_right = BinaryTreeCreate(a, pi);
return root;
}(1)下标 i 遍历数组，需要传入它的地址使其按需改变
(2)思路就是按照先序遍历的顺序，先创建根节点，再创建根节点的左孩子，左孩子是一棵子树的根节点，所以再创建根节点的左孩子的左孩子，......直到为空，开始创建右孩子节点....