前言
链式结构二叉树的访问基本使用递归来进行访问，同时也可以体现出递归的暴力美学。因为有涉及到二叉树的相关操作，因此先要手动构造一个二叉树，在对其进行一些操作。
本篇一切对二叉树的操作都基于我创建的二叉树
这个是我构造的一颗二叉树 ：
//二叉树节点结构
struct TreeNode
{
int val;//存储数据
struct TreeNode* left;//左节点地址
struct TreeNode* right;//右节点地址
};
//创建二叉树节点
struct TreeNode* BuyNode(int x)
{
//创建节点
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(TreeNode));
node->val = x;
node->left = NULL;
node->right = NULL;
return node;
}
//手动构造一个二叉树
struct TreeNode* CreateTree()
{
struct TreeNode* A = BuyNode(1);
struct TreeNode* B = BuyNode(2);
struct TreeNode* C = BuyNode(3);
struct TreeNode* D = BuyNode(4);
struct TreeNode* E = BuyNode(5);
struct TreeNode* F = BuyNode(6);
A->left = B;
A->right = C;
B->left = D;
C->left = E;
C->right = F;
return A;
}一、前序遍历
前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前
访问顺序为：根结点、左⼦树、右⼦树
//前序遍历
void LastOrder(struct TreeNode* root)
{
//判断根节点是否为空
if (root == NULL)
{
printf("NULL ");
return;
}
//访问顺序为：根结点、左⼦树、右⼦树
printf("%d ", root->val);
LastOrder(root->left);
LastOrder(root->right);
}
二、中序遍历
中序遍历(Inorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）
访问顺序为：左⼦树、根结点、右⼦树
//中序遍历
void InOrder(struct TreeNode* root)
{
//判断根节点是否为空
if (root == NULL)
{
printf("NULL ");
return;
}
//访问顺序为：左⼦树、根结点、右⼦树
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}
三、后序遍历
后序遍历(Postorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之后
访问顺序为：左⼦树、右⼦树、根结点
//后序遍历
void PostOrder(struct TreeNode* root)
{
//判断根节点是否为空
if (root == NULL)
{
printf("NULL ");
return;
}
//访问顺序为：左⼦树、右⼦树、根结点
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}
四、二叉树节点个数
在递归调用的同时统计不是NULL节点就行
//树中节点个数
int TreeSize(struct TreeNode* root)
{
//判断根节点是否为空
if (root == NULL)
{
return 0;
}
//节点不为空就统计节点个数
//继续访问该节点的左右子树
return TreeSize(root->left) + TreeSize(root->right) + 1;
}
五、树中叶子节点个数
叶子节点即树中左右子树为空的节点
//树中叶子节点个数
int TreeLeafSize(struct TreeNode* root)
{
//判断根节点是否为空
if (root == NULL)
{
return 0;
}
//左右节点为空时，表示该节点为叶子节点
if (root->left == NULL && root->right == NULL)
{
return 1;
}
//继续访问该节点的左右子树
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
六、 二叉树中第K层节点个数
每次向下递归时，在当前的层数基础上减一，直到当前层数为1
//二叉树中第K层节点个数
int TreeLevelSize(struct TreeNode* root, int k)
{
//判断根节点是否为空
if (root == NULL)
{
return 0;
}
//当前层数为1时，表示已经到了目标层数
if (k - 1 == 0)
{
return 1;
}
//每向下访问左右子树时，同时层数减一
return TreeLevelSize(root->left, k - 1) + TreeLevelSize(root->right, k - 1);
}
七、二叉树的深度
每次向下递归时，深度加一，分别统计左右子树返回的最大深度并返回
//二叉树的深度
int TreeDeep(struct TreeNode* root)
{
//判断根节点是否为空
if (root == NULL)
{
return 0;
}
//分别统计左右子树返回的最大深度并返回
return max(TreeDeep(root->left) + 1, TreeDeep(root->right) + 1);
}
八、二叉树的查找
遍历二叉树，寻找与之匹配的节点
//二叉树的查找
struct TreeNode* TreeFind(struct TreeNode* root, int n)
{
//判断根节点是否为空
if (root == NULL)
{
return NULL;
}
//找到就返回
if (root->val == n)
{
return root;
}
//记录答案
struct TreeNode* ans = NULL;
if (ans == NULL)
{
ans = TreeFind(root->left, n);
}
if (ans == NULL)
{
ans = TreeFind(root->right, n);
}
return ans;
}
九、二叉树层序遍历
⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层序遍历
实现层序遍历需要额外借助数据结构：队列
//二叉树层序遍历
void LevelOrder(struct TreeNode* root)
{
//创建队列
queue<struct TreeNode*> queue;
//将根节点放入队列
queue.push(root);
//如果队列不为空就将队头节点的左右子树放入队列，前提是左右节点不为空
//每次将队头的数据输出并输出
while (!queue.empty())
{
printf("%d ", queue.front()->val);
if (queue.front()->left != NULL)
{
queue.push(queue.front()->left);
}
if (queue.front()->right != NULL)
{
queue.push(queue.front()->right);
}
queue.pop();
}
}
十、判断是否为完全二叉树
通过层序遍历，把NULL也入队，如果出队的是NULL，判断队列中剩余的元素是不是都是 NULL
//判断是否为完全二叉树
//层序遍历
//把NULL也入队，如果出队的是NULL，判断队列中剩余的元素是不是都是 NULL
bool IsNo(struct TreeNode* root)
{
queue<struct TreeNode*> queue;
queue.push(root);
while (queue.front() != NULL)
{
queue.push(queue.front()->left);
queue.push(queue.front()->right);
queue.pop();
}
//判断队列中剩余的元素是不是都是 NULL
//如果都是NULL就是完全二叉树
//如果不只有NULL就不是完全二叉树
while (!queue.empty())
{
if (queue.front() != NULL)
{
return false;
}
queue.pop();
}
return true;
}