1. 二叉树基础操作

1.1 二叉树遍历

下面以这棵二叉树为例:

前中后序遍历也被称为深度遍历.
即先访问根结点.后选择一子结点访问并访问该节点的子结点.持续深入后再依序访问其他子树.可以用递归或栈的方式实现,下面以递归方式实现.

1.1.1 前序遍历

前序遍历(Pre-Order Traversal)

指先访问根，然后访问子树左右孩子的遍历方式
以’#'代替空子树

// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12

结果:1 2 3 # # # 4 5 # # 6 # #

1.1.2 中序遍历

中序遍历(In-Order Traversal)

指先访问左（右）子树,然后访问根,最后访问右（左）子树的遍历方式

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%d ", root->data);
	BinaryTreeInOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12

结果:# 3 # 2 # 1 # 5 # 4 # 6 #

1.1.3 后序遍历

后序遍历(Post-Order Traversal)

指先访问子树,然后访问根的遍历方式

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%d ", root->data);
}
1
2
3
4
5
6
7
8
9
10
11
12

结果:# # 3 # 2 # # 5 # # 6 4 1

小结

前中后序遍历的本质区别是访问根结点的时机不同
前序遍历:根左右
中序遍历:左根右
后序遍历:左右根

二叉树的前中后序遍历体现了递归思想:树是被递归定义的,所以使用树需要通过递归(非递归也可,只不过是进阶的内容).

1.1.4 层序遍历

层序遍历先访问离根节点最近的节点.层序遍历又称为广度优先遍历.
顾名思义,即以根结点为原点,一层层地向下访问.
层序遍历借助队列实现.

注意事项:

1. 队列的元素类型是二叉树结点类型
2. Queue各种接口需要自行实现(C语言),C++/Java有各自的库

思路(使用队列–先进先出):
以层为组,将二叉树分为若干组.

1. 将前面一组结点(数据非空)入队
2. 然后出队,同时把出队的结点的孩子入队
3. 重复上述操作直至队列为空.

这样就得到了二叉树每一层的结点.

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	//创建并初始化队列
	Queue q;
	QueueInit(&q);
	//把根结点放入
	if (root)
	{
		QueuePush(&q, root);
	}
	//每次只取队头元素(当前的根结点),
	//然后将当前根结点的非空孩子结点存入
	//终止条件:队空
	while (!QueueEmpty(&q))
	{
		//取队头元素后pop
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);

		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	QueueDestory(&q);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

复习递归
递归三部曲:

1. 确定递归函数和参数返回值
2. 终止条件
3. 单层递归的逻辑

递归的结束

并不是结束程序本身,而是回到调用当前函数的位置.结合函数栈帧理解:
调用一次函数,创建该函数的栈帧,而返回即销毁栈帧.
上述的代码中结点的地址是作为参数,以局部变量的形式存在于函数栈帧中.

分治算法

分治是一种典型的递归(也可以用其他方法实现分治),递归是分治思想的体现.分治思想即将大问题分为类似规模的小问题.
如:宿舍阿伯想知道一栋楼有多少个学生,那他只需要得到每层的楼长上报的每层楼的人数即可;而楼长需要知道每个宿舍长上报的人数;宿舍长需要知道每个床位有多少个人,显而易见,每床一人,实际上,这就是递归中的终止条件.

分治算法为暴力遍历这种低效(样本很大时)的方式提供了优化.这也是后续学习和解决二叉树中许多问题的重要思想.
广度优先遍历和深度优先遍历的区别

广度优先遍历(BFS)就是层序遍历
深度优先遍历(DFS)就是前中后序遍历
前者:把二叉树的层结构当做洋葱挖出来的一个角.广度优先遍历就是从洋葱芯开始,往外遍历.
后者:从根结点出发,通过父子关系,一定会走到二叉树的最后一个叶子结点,然后再通过父子关系走回根结点,这就是深度优先遍历.

1.2 结点个数

1.2.1 二叉树总结点个数

求二叉树结点个数,最容易想到的方法是遍历计数.
思路1:
用一个count变量计数,每次遇到一个非空结点,更新一次计数器.这样做虽然符合常规思维,但这里有一个不小的问题:计数器必须是全局变量.
如果计数器是局部变量,递归遍历二叉树需要开辟很多个栈帧,每个栈帧都有一个计数器,这样起不到作用.
但全局变量能不用就不用,因为任何地方都可以调用它,安全性低.
思路2:
分治思想
当前结点是它下面所有节点的祖先,也就是说,以当前结点为根的子树的结点数量等于当前结点下面所有结点数量**+1**.这个1是当前结点本身.
这就是递归的函数式,而想要实现它的前提是首先过滤掉结点为空的情况.

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	/*if (root == NULL)
		return 0;
	return   BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;*/
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
1
2
3
4
5
6
7
8

代码十分简单,但其中的分治思想需要细细体会.(善用三目表达式)

1.2.2 二叉树叶子结点个数

思路:
叶子结点的特征是左右孩子都为空,只需遍历的同时判断其是否符合叶子结点的特征即可.

// 二叉树叶子节点个数
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
2
3
4
5
6
7
8
9

其中不变的是分治思想.

1.2.3 第k层结点的个数

思路:
思想仍然是分治思想.

1. 以k>=1为终止条件,能控制遍历的层数为k层.
2. 当k=1时,就相当于求最后一层的节点个数,只需返回1,也就是最后一层的结点本身.
3. 其他思路同2.1.1

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k >= 1);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->left, k - 1) 
         + BinaryTreeLevelKSize(root->right, k - 1) + 1;
}
1
2
3
4
5
6
7
8
9
10
11

1.3 查找结点

查找值为x的结点.
思路:
遍历查找,找到则返回,否则返回NULL.

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
	{
		printf("%d\n", root->data);
		return root;

	}
	BinaryTreeFind(root->left, x);
	BinaryTreeFind(root->right, x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

查找最好使用前序遍历.
使用中序和后序的缺点:时间复杂度可能会更高,因为首先访问当前结点会更快.
但并不是所有的遍历都是前序遍历,需视具体情况.如下文提到的求二叉树的深度需要用后序遍历.

2. 基础练习题

2.1 单值二叉树

也就是说,只要每个结点的值都相同就是单值二叉树.这种问题通常需要从另一面思考,也就是一旦有值不同,就不是单值二叉树.
思路:

1. 特殊情况:根结点为空,返回true.
2. 如果根结点和父结点值相同,父结点和孙子节点值相同,则根结点和孙子节点值相同.

如果当前结点和左孩子结点的值不相等,返回false;
如果当前结点和右孩子结点的值不相等,返回false.

3. 否则就递归地判断当前结点左右子树是否出现不同值的结点,否则相同.

bool isUnivalTree(struct TreeNode* root){
    if(root == NULL)
        return true;
    if(root->left && root->val != root->left->val)
        return false;
    if(root->right && root->val != root->right->val)
        return false;
    
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}
1
2
3
4
5
6
7
8
9
10

注意事项:

1. 根结点为空是符合题意的
2. 注意判断当前结点和左右孩子结点值的时候,注意要保证其孩子节点不为空
3. 如果根结点不为空且其当前结点值和它的左右孩子结点相等,就可以继续往下判断.注意分治思想的应用.
4. 最后应该以’&&'判断当前结点的左右子树是否出现了不同值的结点.

2.2 相同的树

思路:
既然要知道两棵树是否是相同的数,那就少不了比较它们.所以可以边遍历它们的同时边比较,如果相同位置的结点不相等,返回false,否则返回true.
问题是:如何保证遍历的位置是相同的?

k个结点的二叉树,看作k个树,比较这k个树是否相等.

1. 首先一定是特殊情况:如果两棵树的根结点都为空,符合条件,返回false
2. 还有特殊情况:只有一棵树的根结点为空,返回false
3. 判断完根结点,再判断当前结点的值,不相等返回false
4. 最后再递归地判断左右子树是否相等

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 isSameTrree(p->left, q->left) 
        && isSameTree(p->right, q->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.3 对称二叉树

思路:
轴对称图形就是以中心轴线为折痕,左右两边重叠的图形.
所以可以通过比较轴线两边的子树是否相等来判断二叉树是否关于中心轴对称.
也就是说,这道题是上一题的升级,无非是在"轴线两边"判断两棵树是否相等.
但是需要注意的是,轴线两边的"左子树"和"右子树"是相互对应的,就像上图的"3"结点一样.

1. 特殊情况:空树或只有一个结点,符合题意,返回true
2. 特殊情况:如果当前关于轴线对称位置的左右结点只有一个是空,那么它不关于轴线对称,返回false
3. 如果当前结点的值不相等,返回false;否则判断当前以对称结点为根结点的子树是否相等.值得注意的是,这里需要将"左"和"右"对应.

bool isSymmetricSubTree(struct TreeNode* root1, struct TreeNode* root2)
{
    //只有一个结点
    if(root1 == NULL && root2 == NULL)
        return true;
    //最后一层不对称
    if(root1 == NULL || root2 == NULL)
        return false;
    //判断当前结点
    if(root1->val != root2->val)
        return false;
    //用轴把树一分为二,左边的右子树和右边的左子树比较,反之则否
    return isSymmetricSubTree(root1->left, root2->right)
        && isSymmetricSubTree(root1->right, root2->left);
}
bool isSymmetric(struct TreeNode* root){
    //先处理根结点
    if(root == NULL)
        return true;
    //剩下的都是根结点不为空的情况
    return isSymmetricSubTree(root->left, root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

小结:
本题在判断左右两个对称位置结点的情况后,还需要判断一它们为根结点的子树是否相等,所以需要使用一个函数把"比较两个子树是否相等"这个功能封装,以符合二叉树递归定义这一特性.

2.4 另一颗树的子树

思路:
本题同样是比较树的升级,区别在于比较的是一棵树和另一棵树的子树.
想要知道A树是否是B树的子树,就必须找出B树的所有子树,然后将让它们与A树一一比较,一旦遇到不相同的子树,返回false;同样,一旦遇到相同的子树返回true.请注意:这里返回true和返回false并不是补集关系.
如何找出B树的所有子树?
遍历B树,以每个当前结点为根结点的子树,和A树比较.

bool isSametree(struct TreeNode* root1, struct TreeNode* root2)
{
    if(root1 == NULL && root2 == NULL)
        return true;
    if(root1 == NULL || root2 == NULL)
        return false;
    if(root1->val != root2->val)
        return false;
    return isSametree(root1->left, root2->left) 
        && isSametree(root1->right, root2->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    //遍历每个结点,与subRoot比较
    if(root == NULL)
        return false;
    if(isSametree(root, subRoot))
        return true;
    //注意||而不是&&
    return isSubtree(root->left, subRoot)
        || isSubtree(root->right, subRoot);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

需要注意的是,将比较功能独立封装为一个函数,能更清晰地过滤许多情况.

1. 首先要判断的依然是特殊情况:空树不符合条件.
2. 其次是判断当前结点所在子树
3. 最后要注意返回的条件是用"||"链接,因为左右子树中只要有一个符合条件即可.

2.5 二叉树的深度

回顾二叉树的深度:

结点的最大层次
也就是说,二叉树的深度是需要通过比较左右子树的深度得出的.

思路:
用分治思想递归地得到根结点的左右子树的深度,然后返回较大的深度.

int maxDepth(struct TreeNode* root){
    if(root == NULL)
        return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return leftDepth>rightDepth?leftDepth+1:rightDepth+1;
}
1
2
3
4
5
6
7

2.6 二叉树遍历

题目的意思是:
用前序遍历处理给定的字符串,将有效字符(除了’#'之外的字符)以链式结构创建二叉树.
思路:

1. 题目首先要让我们把有效字符按照前序遍历的规则用链式结构存储,所以首先要用一个数组存储字符串;其次是"链式结构",少不了用结构体创建二叉树结点作为模板,其中包括字符,左右孩子指针,这样才能建立二叉树
2. 有了结点模板和有效字符还不够,二叉树的结点随着字符数量的增加而增加.所以需要一个具有创建结点功能的函数.
3. 最重要的是创建二叉树,在里面进行有效字符的获取和二叉树结点的创建,需要注意的是:创建的结点作为当前结点.而创建二叉树必须遵循它的"递归性",所以将当前结点的左右孩子的创建放在它的下一层栈帧中创建.

#include <stdio.h>
#include <stdlib.h>
//创建二叉树结点
typedef char BTDataType;
typedef struct BTNode
{
    struct BTNode* left;
    struct BTNode* right;
    BTDataType data;
}BTNode;
BTNode* CreateNode(BTDataType x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    newnode->data = x;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}
//前序遍历存入数组
BTNode* CreateBinaryTree(char* str, int* pi)
{
    if(str[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    
    BTNode* root = CreateNode(str[(*pi)++]);
    root->left = CreateBinaryTree(str, pi);
    root->right = CreateBinaryTree(str, pi);
    return root;
}
//中序遍历打印
void InOrder(struct BTNode* root)
{
    if(root == NULL)
        return;
    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}

int main()
{
    char str[100];
    scanf("%s", str);
    int i = 0;
    BTNode* root = CreateBinaryTree(str, &i);
    InOrder(root);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

注意事项:
若要保证按顺序地读取给定字符串中的有效字符,就必须保证下标的有序性.所以要使用一个计数器,这里有两种办法:一是使用全局/静态变量,二是将计数器的指针传入函数中.毫无疑问,应该选择后者,这样即使在不同的函数栈帧中,也能访问到同一个计数器.

总结

二叉树的题目总是有点让人难以琢磨,但一旦写出/参考优秀的代码,就会有一种豁然开朗的感觉,简洁的代码往往蕴含着丰富的思考.
写了几个关于二叉树比较的题,就会发现这其实是有固定思路的:

1. 首先考虑当前结点为空或者只有一个根结点,具体看题目.要比较它们相等,往往要用到"&&".
2. 其次是看当前结点只有一个为空,常常要用到"||"
3. 然后判断当前结点的值是否符合题目要求
4. 最后才递归地判断当前结点的左右孩子结点,这里可能会用到"&&“和”||",需要视情况而定

总的来说:
初阶二叉树的许多题目需要按一定的步骤来,因为二叉树有严格的结构.
而每一层的判断最好按顺序来,比如第一层判断根结点(当前结点)是否为空,那么第二层就不用判断当前结点为空的情况了,等等.
根据我们的需要,按照一定逻辑的执行的判断语句,就像一层层筛网,最上面的孔最大,然后依层变小,最后才能较严谨和顺利地得到我们想要的结果.

---

6/28/22
1