文章目录
前言
二叉树的顺序结构就是用数组来存储，而「数组」一般只适合表示「满二叉树」或「完全二叉树」，因为不是完全二叉树会有「空间的浪费」。
普通二叉树的增删查改没有意义，主要学习它的结构，要加上搜索树的规则，才有价值。
二叉树的链式结构
二叉树链式结构的实现
在学习二叉树的基本操作前，需先要创建一棵二叉树，这里手动快速创建一棵简单的二叉树
#include<stdio.h> // perror, printf
#include<stdlib.h> // malloc
typedef char BTDataType;
// 定义二叉树的结点
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
// 动态申请一个新结点
BTNode* BuyNode(BTDataType x)
{
//
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->left = newnode->right = NULL;
return newnode;
}
// 二叉树的链式结构
BTNode* CreatBinaryTree()
{
// 创建多个结点
BTNode* node_A = BuyNode('A');
BTNode* node_B = BuyNode('B');
BTNode* node_C = BuyNode('C');
BTNode* node_D = BuyNode('D');
BTNode* node_E = BuyNode('E');
BTNode* node_F = BuyNode('F');
// 用链来指示结点间的逻辑关系
node_A->left = node_B;
node_A->right = node_C;
node_B->left = node_D;
node_C->left = node_E;
node_C->right = node_F;
return node_A;
}
注意：上述代码并不是创建二叉树的方式
二叉树的遍历方式
二叉树的深度优先遍历
由于被访问的结点必是「某子树的根」，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
前序遍历(先根遍历)
遍历顺序：根->左子树->右子树
//前序遍历
void BinaryPrevOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
//根->左子树->右子树
printf("%c ", root->data);
BinaryPrevOrder(root->left);
BinaryPrevOrder(root->right);
}
这里的访问路径是：A B D NULL NULL NULL C E NULL NULL F NULL NULL
接下来的两个遍历可以自己试试画一下递归图。
中序遍历(中根遍历)
遍历顺序：左子树->根->右子树
void BinaryInOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
//左子树->根->右子树
BinaryInOrder(root->left);
printf("%c ", root->data);
BinaryInOrder(root->right);
}
这里的访问路径是：NULL D NULL B NULL A NULL E NULL C NULL F NULL
后序遍历(后根遍历)
遍历顺序：左子树->右子树->根
//后序遍历
void BinaryPostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
//左子树->右子树->根
BinaryPostOrder(root->left);
BinaryPostOrder(root->right);
printf("%c ", root->data);
}
这里的访问路径是：NULL NULL D NULL B NULL NULL E NULL NULL F C A
二叉树的广度优先遍历
层序遍历
层序遍历，自上而下，从左往右逐层访问树的结点的过程就是层序遍历。
我们借助队列来实现：
先入根结点，然后出队列，再入他的两个孩子，然后一样的出孩子，再入孩子的孩子，重复即可。（NULL不入）
//层序遍历
void BinaryLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);//初始化队列
if (root != NULL)
QueuePush(&q, root);
int levelSize = 1;
while (!QueueEmpty(&q))//当队列不为空时，循环继续
{
//一层一层出
while (levelSize--)
{
BTNode* front = QueueFront(&q);//读取队头元素
QueuePop(&q);//删除队头元素
printf("%c ", front->data);//打印出队的元素
if (front->left)
{
QueuePush(&q, front->left);//出队元素的左孩子入队列
}
if (front->right)
{
QueuePush(&q, front->right);//出队元素的右孩子入队列
}
}
printf("\n");
levelSize = QueueSize(&q);
}
printf("\n");
QueueDestroy(&q);//销毁队列
}
二叉树链式结构接口实现
二叉树结点个数
子问题拆解：
1.若为空，则结点个数为0。
2.若不为空，则结点个数 = 左子树结点个数 + 右子树结点个数 + 1（自己）。
//结点的个数
int BinaryTreeSize(BTNode* root)
{
//结点个数 = 左子树的结点个数 + 右子树的结点个数 + 自己
return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
二叉树叶子结点个数
子问题拆解：
1.若为空，则叶子结点个数为0。
2.若结点的左指针和右指针均为空，则叶子结点个数为1。
3.除上述两种情况外，说明该树存在子树，其叶子结点个数 = 左子树的叶子结点个数 + 右子树的叶子结点个数。
//叶子结点的个数
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 就是当前树的深度
// 二叉树的深度(高度)
int BinaryTreeMaxDepth(BTNode* root)
{
// 先判断当前树的根结点是否为空
if (root == NULL)
{
return 0;
}
// 当前树的根结点不为空，分别计算其左右子树的深度
int leftDepth = BinaryTreeMaxDepth(root->left);
int rightDepth = BinaryTreeMaxDepth(root->right);
// 比较当前树左右子树的深度，最大的那个+1 就是当前树的深度
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
二叉树第k层结点个数
//第k层结点的个数O(N)
int BinaryTreeKLevelSize(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)
return 0;
if (k == 1)//第一层结点个数
return 1;
//相对于父结点的第k层的结点个数 = 相对于两个孩子结点的第k-1层的结点个数之和
return BinaryTreeKLevelSize(root->left, k - 1)
+ BinaryTreeKLevelSize(root->right, k - 1);
}
二叉树查找x值的结点
//查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)//空树
return NULL;
if (root->data == x)//先判断根结点
return root;
BTNode* leftret = BinaryTreeFind(root->left, x);//在左子树中找
if (leftret)
return leftret;
BTNode* rightret = BinaryTreeFind(root->right, x);//在右子树中找
if (rightret)
return rightret;
return NULL;//根结点和左右子树中均没有找到
}
销毁二叉树
这里要用后序遍历来销毁，左子树->右子树->根
//销毁二叉树
void BinaryTreeDestroy(BTNode* root)
{
if (root == NULL)
return;
BinaryTreeDestroy(root->left);
BinaryTreeDestroy(root->right);
free(root);//没有用二级指针，这里只是实参的拷贝，需要用完主动置空再函数外置空
}
二叉树的创建及遍历
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
依次读取字符，拆分成子问题：
1.如果不是#，创建结点，存值，然后递归其左子树和右子树；
2.如果是#，说明不能构建结点了，直接返回NULL；
#include <stdio.h>
typedef char BTDataType;
typedef struct BinaryTreeNode{
BTDataType data;
struct BinaryTreeNode*left;
struct BinaryTreeNode*right;
}BTNode;
BTNode*BinaryTreeCreat(char*arr,int*pi)
{
if(arr[*pi]=='#')
{
(*pi)++;
return NULL;
}
BTNode*node=(BTNode*)malloc(sizeof(BTNode));
node->data=arr[*pi];
(*pi)++;
node->left=NULL;
node->right=NULL;
node->left=BinaryTreeCreat(arr,pi);//递归构建左子树
node->right=BinaryTreeCreat(arr,pi);//递归构建右子树
return node;
}
//中序遍历
void BinaryInOrder(BTNode*root)
{
if(root==NULL)
return;
BinaryInOrder(root->left);
printf("%c ",root->data);
BinaryInOrder(root->right);
}
int main() {
char ret[100];
scanf("%s",&ret );
int i=0;
BTNode*root= BinaryTreeCreat(ret,&i);
BinaryInOrder(root);
printf("\n");
return 0;
}
衍生题
判断二叉树是否为完全二叉树
用一个队列来判断
将根从队尾入列，然后从队头出数据，出根的时候入它的左孩子和右孩子，NULL也入列。重复次操作，当出数据第一次遇到NULL时，停止入队列并且检查队列中是否还有数据，如果全部为NULL则此树时完全二叉树
如果队列中还有数据，则不是完全二叉树。
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);//初始化队列
if (root != NULL)
QueuePush(&q, root);
while (!QueueEmpty(&q))//当队列不为空时，循环继续
{
BTNode* front = QueueFront(&q);//读取队头元素
QueuePop(&q);//删除队头元素
//遇到第一个NULL结点直接跳出循环
if (front == NULL)
break;
QueuePush(&q, front->left);//出队元素的左孩子入队列（NULL也入）
QueuePush(&q, front->right);//出队元素的右孩子入队列（NULL也入）
}
//前面遇到空以后，后面还有非空就不是完全二叉树
while (!QueueEmpty(&q))//当队列不为空时，循环继续
{
BTNode* front = QueueFront(&q);//读取队头元素
QueuePop(&q);//删除队头元素
if (front)
{
QueueDestroy(&q);//销毁队列
return false;
}
}
//没有遇到说明是完全二叉树
QueueDestroy(&q);//销毁队列
return true;
}
判断二叉树是否为单值二叉树
单值二叉树，所有结点的值都相同的二叉树即为单值二叉树，判断某一棵二叉树是否是单值二叉树的一般步骤如下：
1.判断根的左孩子的值与根结点是否相同。
2.判断根的右孩子的值与根结点是否相同。
3.判断以根的左孩子为根的二叉树是否是单值二叉树。
4.判断以根的右孩子为根的二叉树是否是单值二叉树。
若满足以上情况，则是单值二叉树。
bool isUnivalTree(struct TreeNode* root) {
if(root==NULL)
return true;
if(root->left&&root->left->val!=root->val)
return false;
if(root->right&&root->right->val!=root->val)
return false;
return isUnivalTree(root->left)&&isUnivalTree(root->right);
}
判断两颗二叉树是否相同
拆分成子问题：
先判断根是否为空
再比较根的左子树是否相同
再比较跟根的右子树是否相同
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
if(p==NULL&&q==NULL)
return true;
if(p==NULL||q==NULL)
return false;
if(p->val!=q->val)
return false;
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
判断二叉树是否为对称二叉树
实际上就是要判断根节点的左右两个子树是否镜像对称。因此，其解决方案为：按照对称的方式遍历左右子树，比较同时遍历的节点是否一致。而且在遍历过程中，只有两个子树的根节点对称了，继续比较左右子树是否对称才有意义，因此我们使用"中序遍历"（其实不是严格的中序遍历，只是我们先比较根节点）
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(p==NULL&&q==NULL)
return true;
if(p==NULL||q==NULL)
return false;
if(p->val!=q->val)
return false;
return isSameTree(p->left,q->right)&&isSameTree(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root) {
if(root==NULL)
return true;
return isSameTree(root->left,root->right);
}
判断一颗二叉树是否为另一颗二叉树的子树
两个树都是空树，返回true
如果两个树一个是空，一个不是空，不包含
两个树都是非空，比较根节点的值是不是相等，如果相等的话，比较一下p和q是不是相同的树
递归的判定一下，p是否被q的左子树包含
递归的判定一下，p是否被q的右子树包含。
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(p==NULL&&q==NULL)
return true;
if(p==NULL||q==NULL)
return false;
if(p->val!=q->val)
return false;
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root==NULL)
return false;
if(isSameTree(root->left,subRoot))
return true;
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}
判断二叉树是否为平衡二叉树
如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
子问题：
求出左子树的深度。
求出右子树的深度。
若左子树与右子树的深度差的绝对值不超过1，并且左右子树也是平衡二叉树，则该树是平衡二叉树。
int max(int x, int y)
{
return x>y?x:y;
}
int height(struct TreeNode* root)
{
if (root == NULL)
return 0;
return max(height(root->left), height(root->right)) + 1;
}
bool isBalanced(struct TreeNode* root)
{
if (root == NULL)
return true;
//左右子树高度差的绝对值不超过1 && 其左子树是平衡二叉树 && 其右子树是平衡二叉树
return fabs(height(root->left) - height(root->right)) <= 1 &&
isBalanced(root->left) &&
isBalanced(root->right);//fabs取绝对值，要用要包含头文件#include<math.h>
}
翻转二叉树
子问题：
翻转左子树。
翻转右子树。
交换左右子树的位置。
//翻转二叉树
struct TreeNode* invertTree(struct TreeNode* root)
{
if (root == NULL)//根为空，直接返回
return root;
struct TreeNode* left = invertTree(root->left);//翻转左子树
struct TreeNode* right = invertTree(root->right);//翻转右子树
//左右子树位置交换
root->left = right;
root->right = left;
return root;
}