龙胜网站建设公司,个人网站如何做推广,吉安网站设计,山西seo排名厂家前记上周我投递出了简历#xff0c;岗位是后端开发工程师。这周腾讯面试官给我进行了视频面试。面试过程中他问了二叉树的问题。二叉树相关算法题#xff0c;在面试中出现的次数非常非常多#xff0c;所以我面试之前也有所准备。今天结合面试问题详细讲一讲二叉树#xff0…前记上周我投递出了简历岗位是后端开发工程师。这周腾讯面试官给我进行了视频面试。面试过程中他问了二叉树的问题。二叉树相关算法题在面试中出现的次数非常非常多所以我面试之前也有所准备。今天结合面试问题详细讲一讲二叉树结合实例分析二叉树的存储结构的建立方法和遍历过程。面试官面试问题面试官大佬看你的简历上写熟悉数据结构谈谈二叉树遍历的方式我(这可难不倒我)先序遍历先访问根节点后依次访问左孩子和右孩子递归算法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;}总结咱们玩归玩闹归闹别拿面试开玩笑。二叉树的遍历虽然简单但遍历方式多样也有递归算法和非递归算法之分。一旦问到了大家一定要回答全面不要丢三落四回答到点上。二叉树相关算法题在面试中出现的次数非常非常多大家面试前要把二叉树等数据结构的基础打牢。
