二叉树

这周本来要期中考试的,结果几天前栖霞区出现了聚集性感染,又被迫线上课了,只好推迟考试,所以继续学习相关的内容。我们目前学的树还仅限于二叉树,操作也只有创建遍历两种,但实际上树的问题十分复杂,并且能由它引申出很多高级数据结构,比如前缀树、平衡树、红黑树、线段树……估计也不在这门课的学习范围内了吧(我也就略知一二,搜到板子会用而已)。

言归正传,这节课我们花了很多时间来讲先、中、后序遍历的非递归算法,以及树的**#号表示法**。

二叉树的遍历

不同于线性结构(数组、链表)中每个元素最多有一个前驱和一个后继,二叉树中每个元素可以有两个后继,这导致二叉树的遍历也有好几种方法,可以分为深度优先遍历广度优先遍历两大类,而深度优先遍历根据父节点何时遍历又可以分为先序遍历中序遍历后序遍历,广度优先遍历也叫层序遍历。注意,不特别说明,所有的遍历都是自左向右的。

用一个例子来说明他们的差别:

二叉树遍历

先序遍历结果:ABDFKICEHJG

中序遍历结果:DBKFIAHEJCG

后序遍历结果:DKIFBHJEGCA

层序遍历结果:ABCDFEGKIHJ

注意,父节点的遍历顺序是针对左右子树的,而不是左右孩子,比如在中序遍历中,我们要将左子树遍历完,才轮得到父节点,而每一个子树都是如此,所以最先遍历的是左下角的那个节点。

这样的思想很自然地带着递归的感觉,所以用递归来写遍历算法是最简洁、最方便的,如果在算法竞赛这些赶时间的时候,肯定选择递归了,不过非递归的写法空间消耗小,因为自己维护的栈要比递归栈开销小,这是一种常数优化。而掌握遍历的非递归算法也是真正理解递归的一个证明,所以在学习的过程中,会重点讲非递归算法(也是因为递归算法太自然了,没什么可讲的),我是暑假时跟着邓俊辉老师的网课学的,当时云里雾里,想得多了,便也差不多理解了。

在进入遍历算法前,先亮出我的树节点的定义:

1
2
3
4
struct TreeNode{
TreeNode *left=NULL,*right=NULL;//左右孩子指针
int val=0;//值
};

深度优先遍历

先序遍历

先序遍历,就是遇到一棵树,先遍历根节点,然后分别遍历左右子树,这是方法和代码都最清晰的遍历方式了。

递归代码如下,没什么好说的:

1
2
3
4
5
6
7
8
void preOrderTrav(TreeNode *node)
{
if(node==NULL)
return ;
visit(node);
preOrderTrav(node->left);
preOrderTrav(node->right);
}

先序遍历的非递归算法,其实也很好写。只需要每次取出栈顶,直接访问,然后将两个孩子入栈即可,注意,由于是先左后右访问,而栈是后入先出,所以应该先右后左入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void preOrderTrav(TreeNode *root)
{
if(root==NULL)
return ;
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty())
{
TreeNode *node=stk.top();
visit(node);
stk.pop();
if(node->right) stk.push(node->right);
if(node->left) stk.push(node->left);
}
return ans;
}

然而,用这种方法来改写中序遍历和后序遍历,比较困难,因为父节点不能直接访问了,就不好控制访问的时机,比如说,在中序遍历时,只有左孩子被访问了,才能访问它,我们又如何得知左孩子的访问情况呢?如果捆绑一个标记,岂不是与我们的初衷“优化”背道而驰了吗。所以,我们要寻求一种新的方法。

注意到,在三种遍历中,都有一个顺左孩子而下的过程,先序遍历直接访问沿途节点,而中序、后序则是以此找到第一个访问的节点。我们以这种特性来重写非递归算法,在后面两种改写过程中会看到它的作用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void preOrderTrav(TreeNode *root)
{
TreeNode *node = root;
stack<TreeNode *> stk;
while (true)
{
while (node)//visit along left branch
{
visit(node);//直接访问沿途节点
stk.push(node);//入栈,这是为了保存它们的右子树
node = node->left;
}
if (stk.empty())
return ;
node = stk.top()->right;//左子树遍历过了,访问右子树(逐层向上)
stk.pop();
}
return ;
}

中序遍历

中序遍历,就是先访问左子树,左子树完全访问完了,访问父节点,然后访问右子树。

递归代码如下,只需要将先序遍历变换一下访问位置而已

1
2
3
4
5
6
7
8
void inOrderTrav(TreeNode *node)
{
if(node==NULL)
return ;
inOrderTrav(node->left);
visit(node);
inOrderTrav(node->right);
}

而非递归算法,有了上面的铺垫,也就好写了。同样是先沿着左孩子向下,不过不直接访问,而是在出栈时访问,然后访问右子树。具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void inOrderTrav(TreeNode *root)
{
TreeNode *node = root;
stack<TreeNode *> stk;
while (true)
{
while (node)//visit along left branch
{
stk.push(node);//入栈
node = node->left;
}
if (stk.empty())
return ;
visit(stk.top());//在出栈时访问它,然后访问它的右子树
node = stk.top()->right;//左子树遍历过了,访问右子树(逐层向上)
stk.pop();
}
return ;
}

后序遍历

后序遍历,就是依次访问左右子树,最后访问父节点。

递归代码如下:

1
2
3
4
5
6
7
8
void postOrderTrav(TreeNode *node)
{
if(node==NULL)
return ;
postOrderTrav(node->left);
postOrderTrav(node->right);
visit(node);
}

而后序遍历的非递归算法,大体上与上面两个相似,然而要特别注意,访问父节点的标志是什么?既不是入栈时,也不是出栈时,而是右孩子被访问后,也就是说,与中序遍历相比,我们对栈顶多一个检验操作——如果右孩子被访问了,就访问并出栈,否则访问右孩子,方法是用一个pre指针记录前一个访问的节点是谁,只多出常数级别的消耗。具体代码如下:

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
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
TreeNode* node=root,*pre=NULL;
while(true)//对每一个节点,我们先找到左下角的点并将沿途的点全部入栈,然后将右子节点作为新的根
{
while(node)//visitAlongLeftBranch
{
stk.push(node);
node=node->left;
}
if(stk.empty())//为空,说明根节点完成了访问,结束
return ;
node=stk.top();
if(node->right==NULL||pre==node->right)//如果右子树访问过了或者根本没有右子树,访问当前节点
{
visit(node);
pre=node;
stk.pop();
node=NULL;
}
else
node=node->right;//否则访问右子树节点入栈
}
return ;
}

层序遍历

层序遍历可以体现出二叉树的层次,也就是说,可以明确知道某个节点在哪一层,以及各层的情况,因而得名。大体上有dfs和bfs两种方式实现。

层次遍历是自上而下自左而右的遍历顺序,因此bfs实现是比较直观的,dfs实现或许有些取巧——因为实际遍历顺序不是层序,只是能得出同样的结果而已。

深度优先遍历实现

由于深度优先遍历也有着自左而右的特点,我们只需要维护一个层数,并逐个添加结果即可,具体代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<vector<int>> ans;
void preOrderTrav(TreeNode*node,int depth)//这里使用先序遍历的代码,其他两者也可以做
{
if(node==NULL)
return ;
if(ans.size()>depth)
ans[depth].push_back(node->val);
else
ans.push_back({node->val});
preOrderTrav(node->left,depth+1);
preOrderTrav(node->right,depth+1);
}
vector<vector<int>> levelOrderTrav(TreeNode* root)
{
preOrderTrav(root,0);
return ans;
}

广度优先遍历实现

广度优先遍历,就要维护一个队列了,每次自左向右处理一层,并立即访问,然后将非空的孩子节点入队,直到队列为空。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<int>> levelOrder(TreeNode* root) {
if(root==NULL)
return {};
vector<vector<int>> ans;
queue<TreeNode*> q;
q.push(root);
while(!q.empty())//每次处理一层
{
ans.push_back({});//添加一层
int cnt=q.size();//当前q里面的全是上一层的,计数
for(int i=1;i<=cnt;++i)//执行cnt次后,全是下一层的了
{
TreeNode* node=q.front();
q.pop();
ans.back().push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
}
return ans;
}

二叉树的恢复

给我们怎样的信息,可以唯一确定一颗二叉树呢?应该有很多种组合,这里给出三种方法。

层序遍历序列(带null)

这种表示方法是把除叶节点外的每个节点都视为有两个孩子,进行层序遍历,如果事实上为空,就填null得到的序列。

这是比较清晰的,就像把整颗树画出来一样,具体可以参见297. 二叉树的序列化与反序列化 - 力扣(LeetCode),是通过层序遍历实现的,这里贴一下我的反序列化代码,也就是输入一个字符串,得到一棵树,其中利用了string流进行字符串切割,每次读入两个(左右孩子),而主体逻辑和层序遍历相同。

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
TreeNode* deserialize(string data) {
if(data=="")
return NULL;
stringstream in(data);
string v,v1,v2;
queue<TreeNode*> q;
TreeNode* root=new TreeNode;
in>>v;
root->val=stoi(v);
q.push(root);
while(!q.empty())
{
int cnt=q.size();
for(int i=1;i<=cnt&&in>>v1&&in>>v2;++i)
{
TreeNode* node=q.front();
q.pop();
if(v1!="null")
{
TreeNode* node1=new TreeNode;
node1->val=stoi(v1);
node->left=node1;
q.push(node1);
}
if(v2!="null")
{
TreeNode* node2=new TreeNode;
node2->val=stoi(v2);
node->right=node2;
q.push(node2);
}
}
}
return root;
}

井号法(深度优先遍历序列)

井号法是把包括叶节点的每个节点都视为有两个孩子,为空则填**#,然后进行深度优先遍历后得到的序列(一般是先序遍历),故而也会通过深度优先遍历来恢复。比如最上面那张图的二叉树,#法表示为:ABD##FK##I##CEH##J##G##**。

恢复代码为:

1
2
3
4
5
6
7
8
9
10
11
12
TreeNode *createTree()
{
char c;
scanf("%c", &c);
if (c == '#') //如果遇到#,返回空
return NULL;
TreeNode *node = new TreeNode;
node->val = c;
node->left = createTree();
node->right = createTree();
return node;
}

由于深度优先遍历的递归版本代码量本来就小,所以这种方法建树的代码也要少一点。不过,实际上这两种方法都是用特殊字符代替空值来体现二叉树的层次的。

(先序/后序)&中序遍历序列

这也是考察最多的问题了,通过先序、后序遍历序列中的一个,以及中序遍历序列,就可以唯一确定一棵树。具体可见105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode)基本思路是:先序遍历的第一个值就是根节点,而中序遍历中可以依此分隔左右子树,然后再根据大小在先序遍历序列中找到左右子树分点,递归求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> preOrderTrav,inOrderTrav;
TreeNode *createTree(int pbeg, int pend, int ibeg, int iend)
{
if (pbeg == pend)
return NULL;
TreeNode *node = new TreeNode;
node->val = preOrderTrav[pbeg];
int pos =find(inOrderTrav.begin()+ibeg,inOrderTrav.end(),node->val)-inOrderTrav.begin(),
mid = pbeg + pos - ibeg + 1; //在中序遍历序列中找到当前的根节点,并依此计算先序遍历中的分点
node->left = createTree(pbeg + 1, mid, ibeg, pos);
node->right = createTree(mid, pend, pos + 1, iend);
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
preOrderTrav=preorder,inOrderTrav=inorder;
return createTree(0,preorder.size(),0,inorder.size());
}

随便写几个问题,就这么多了,树结构可写的真是太多了,有时间再来补吧……