做者 | 天才程序YUANphp
责编 | 夕颜node
封图 | CSDN下载自视觉中国程序员
出品 | CSDN(ID:CSDNnews)面试
前记算法
上周我投递出了简历,岗位是后端开发工程师。这周腾讯面试官给我进行了视频面试。面试过程当中他问了二叉树的问题。二叉树相关算法题,在面试中出现的次数很是很是多,因此我面试以前也有所准备。今天结合面试问题详细讲一讲二叉树,结合实例分析二叉树的存储结构的创建方法和遍历过程。后端
面试问题数据结构
面试官大佬:看你的简历上写熟悉数据结构,谈谈二叉树遍历的方式?框架
我:(这可难不倒我)机器学习
先序遍历ide
先访问根节点,后依次访问左孩子和右孩子
递归算法
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;//将右孩子压栈 } } } }
遍历算法总结
面试官大佬:如何判断是否彻底二叉树呢?
我:(这可难不倒我)
判断彻底二叉树
按层遍历二叉树, 从每层从左向右遍历全部的结点
若是当前结点有右孩子, 但没有左孩子, 那么不是彻底二叉树
若是当前结点有左孩子但无右孩子, 那么它以后的全部结点都必须为叶子结点,不然不是彻底二叉树
若是当前结点有左孩子和右孩子, 继续遍历
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 技术生态论
今日福利:评论区留言入选,可得到价值299元的「2020 AI开发者万人大会」在线直播门票一张。 快来动动手指,写下你想说的话吧。
点击阅读原文,精彩继续!
你点的每一个“在看”,我都认真当成了喜欢