查看原文
其他

腾讯面试官这样问我二叉树,我刚好都会 | 原力计划

CSDN 2020-10-16

The following article is from 程序猿的进阶 Author 甄菜姬




作者 | 天才程序YUAN
责编 | 夕颜
封图 | CSDN下载自视觉中国
出品 | CSDN(ID:CSDNnews)


前记


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


面试问题


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


我:(这可难不倒我)


先序遍历


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


递归算法


void PreOrder1(BTREE bt) //递归先根遍历 {if (bt){if (bt->data != '#'){printf(" %c", bt->data);//结点不空 ,打印结点值 }PreOrder1(bt->lchild);//依次访问左右节点 PreOrder1(bt->rchild);}}


非递归算法


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;}}}

中序遍历


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


递归算法


void InOrder1(BTREE bt)//递归中序遍历{if (bt){InOrder1(bt->lchild);//先访问左节点 if (bt->data != '#'){printf(" %c", bt->data);//结点不空 ,打印结点值 }InOrder1(bt->rchild);//先访问右节点 }}


非递归算法


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;}}}


后序遍历


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


递归算法


void PostOrder1(BTREE bt)//后序遍历 {if (bt){PostOrder1(bt->lchild);//先访问左,右孩子节点 PostOrder1(bt->rchild);if (bt->data != '#'){printf(" %c", bt->data);//后访问根节点 }}}


非递归算法


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;}}}


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


我:……


沉默了几秒,我(这可难不倒我):还有一种层序遍历


层序遍历


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


//层序遍历 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. 如果当前结点有左孩子和右孩子, 继续遍历


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;}


总结


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


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


原文链接:

https://blog.csdn.net/JAck_chen0309/article/details/104843101


【END】

更多精彩推荐
斩获GitHub 2000+ Star,阿里云开源的 Alink 机器学习平台如何跑赢双11数据“博弈”?| AI 技术生态论

2020 年,AI 芯片内存哪家强?

拜托,别再问我什么是 B+ 树了

程序员为什么应该旗帜鲜明地反对“最佳实践”?

半小时训练亿级规模知识图谱,亚马逊AI开源知识图谱嵌入表示框架DGL-KE

“出道” 5 年采用率达 78%,Kubernetes 的成功秘诀是什么?

警惕!新骗术出现:这些虚假二维码生成器已成功盗取 4.6 万美元!

今日福利:评论区留言入选,可获得价值299元的「2020 AI开发者万人大会」在线直播门票一张。  快来动动手指,写下你想说的话吧。

点击阅读原文,精彩继续!

你点的每个“在看”,我都认真当成了喜欢

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存