腾讯面试官这样问我二叉树，我刚好都会 前记 面试问题 面试官

发表于

前记

上周我投递出了简历，岗位是后端开发工程师。这周腾讯面试官给我进行了视频面试。面试过程中他问了二叉树的问题。二叉树相关算法题，在面试中出现的次数非常非常多，所以我面试之前也有所准备。今天结合面试问题详细讲一讲二叉树，结合实例分析二叉树的存储结构的建立方法和遍历过程。

面试问题

面试官大佬：看你的简历上写熟悉数据结构，谈谈二叉树遍历的方式？

我：（这可难不倒我）

先序遍历

先访问根节点，后依次访问左孩子和右孩子

递归算法

1
2
3
4
5
6
7
8
9
10
11
12
复制代码void PreOrder1(BTREE bt) //递归先根遍历 
{
	if (bt)
	{
		if (bt->data != '#')
		{
			printf(" %c", bt->data);//结点不空 ，打印结点值 
		}
		PreOrder1(bt->lchild);//依次访问左右节点 
		PreOrder1(bt->rchild);
	}
}

非递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
复制代码void PreOrder2(BTREE p)//非递归先根遍历 ,先访问根节点，后依次访问左孩子和右孩子 
{
	int top = -1;
	node *Q[N];
	while (p != NULL || top != -1)
	{
		while (p != NULL)
		{
			if (p->data != '#')
			{
				printf(" %c", p->data);
			}
			Q[++top] = p;
			p = p->lchild;
		}
		if (top != -1)
		{
			p = Q[top--];
			p = p->rchild;
		}
	}
}

中序遍历

先访问左孩子，后依次访问根节点和右孩子

递归算法

1
2
3
4
5
6
7
8
9
10
11
12
复制代码void InOrder1(BTREE bt)//递归中序遍历
{
	if (bt)
	{
		InOrder1(bt->lchild);//先访问左节点 
		if (bt->data != '#')
		{
			printf(" %c", bt->data);//结点不空 ，打印结点值 
		}
		InOrder1(bt->rchild);//先访问右节点 
	}
}

非递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
复制代码void InOrder2(BTREE p)//非递归中序遍历，先访问左孩子，然后访问根节点，后访问右孩子
{
	int top = -1;
	node *Q[N];
	while (p != NULL || top != -1)
	{
		while (p != NULL)
		{
			Q[++top] = p;
			p = p->lchild;
		}
		if (top != -1)
		{
			p = Q[top--];
			if (p->data != '#')
			{
				printf(" %c",p->data);
			}
			p = p->rchild;
		}
	}
}

后序遍历

先访问左孩子孩子，后依次访问右孩子和根节点

递归算法

1
2
3
4
5
6
7
8
9
10
11
12
复制代码void PostOrder1(BTREE bt)//后序遍历 
{
	if (bt)
	{
		PostOrder1(bt->lchild);//先访问左，右孩子节点 
		PostOrder1(bt->rchild);
		if (bt->data != '#')
		{
			printf(" %c", bt->data);//后访问根节点 
		}
	}
}

非递归算法

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
复制代码void PostOrder2(BTREE p)//非递归后序遍历 ，先访问左孩子，然后访问右孩子，后访问根节点 
{
	int top = -1;
	node *Q[N];
	int flag[N] = { 0 };
	while (p != NULL || top != -1)
	{
		while (p != NULL)
		{
			top++;
			Q[top] = p;
			flag[top] = 1;
			p = p->lchild;
		}
		while (top != -1 && flag[top] == 2)
		{
			if (Q[top]->data != '#')
			{
				printf(" %c", Q[top]->data);
				top--;
			}
		}
		if (top != -1)
		{
			flag[top] = 2;
			p = Q[top]->rchild;
		}
	}
}

面试官大佬：你回答得很好，还有其他遍历方式吗

我：……

沉默了几秒，我（这可难不倒我）：还有一种层序遍历

层序遍历

从根开始，依次向下，对于每一层从左向右遍历

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
复制代码//层序遍历 
void Sequense(BTREE bt)//建立栈，依次将根节点，左孩子，右孩子压栈 ，并打印栈顶元素 
{
	node *Q[N];
	node *p;
	int front = 0, top = 0;
	if (bt != NULL)
	{
		Q[++top] = bt;//将根节点压栈
		while (front < top) //遍历栈 
		{
			p = Q[++front];
			if (p->data != '#')
			{
				printf(" %c", p->data);//打印栈顶元素 
			}
			if (p->lchild)
			{
				Q[++top] = p->lchild;//将左孩子压栈
			}
			if (p->rchild)
			{
				Q[++top] = p->rchild;//将右孩子压栈
			}
		}
	}
}

遍历算法总结

在这里插入图片描述

面试官大佬：如何判断是否完全二叉树呢

我：（这可难不倒我）

判断完全二叉树

  1. 按层遍历二叉树, 从每层从左向右遍历所有的结点
  2. 如果当前结点有右孩子, 但没有左孩子, 那么不是完全二叉树
  3. 如果当前结点有左孩子但无右孩子, 那么它之后的所有结点都必须为叶子结点，否则不是完全二叉树
  4. 如果当前结点有左孩子和右孩子, 继续遍历
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
复制代码int Compnode(BTREE G)//判断是否是完全二叉树 
{
	node *D[N], *p; //建立一个队列D[N]
	int front = 0, last = 0; //front是队头指针,last是队尾指针
	int tree_signal = 1;//tree_signal是判断是否为完全二叉树的标志
	int odd_signal = 1;//odd_signal是判断是否存在无左孩子的节点的标志
	if (G != NULL)
	{
		last++;
		D[last] = G; //将根节点压入队尾
		while (front != last)
		{
			front++;
			p = D[front];
			if (p->lchild == NULL ||(p->lchild)->data == '#') //*p节点没有左孩子
			{
				odd_signal = 0;
				if (p->rchild != NULL && (p->rchild)->data != '#') //没有左孩子但有右孩子，不是完全二叉树
					tree_signal = 0; 
			}
			else //*p节点有左子树
			{
				if (odd_signal == 1) //目前不存在无左孩子的节点
				{
					last++; //左孩子进队
					D[last] = p->lchild;
					if (p->rchild == NULL || (p->rchild)->data == '#') //*p有左孩子但没有右孩子
					{
						odd_signal = 0;
					}
					else
					{
						last++; //右孩子进队
						D[last] = p->rchild;
					}
				}
				else       //目前存在有左孩子的节点，不是完全二叉树
				{
					tree_signal = 0; 
				}
			}
		}
	}
	else
	{
		tree_signal = 0;//假设空树不是完全二叉树
	}
	return tree_signal;
}

总结

咱们玩归玩，闹归闹，别拿面试开玩笑。

二叉树的遍历虽然简单，但遍历方式多样，也有递归算法和非递归算法之分。一旦问到了，大家一定要回答全面，不要丢三落四，回答到点上。二叉树相关算法题，在面试中出现的次数非常非常多，大家面试前要把二叉树等数据结构的基础打牢。

如果有收获？希望老铁们来个双连击，给更多的人看到这篇文章

1、老铁们，关注我的原创微信公众号「程序猿的进阶」，主要是IT与竞赛

2、创作不易，顺便点个赞呗，可以让更多的人看到这篇文章，激励一下我这个小白。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%