面试官：说说你对树的理解？相关的操作有哪些？

[[425982]]

本文转载自微信公众号「JS每日一题」，作者灰灰。转载本文请联系JS每日一题公众号。

成都创新互联-专业网站定制、快速模板网站建设、高性价比剑阁网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式剑阁网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖剑阁地区。费用合理售后完善，10余年实体公司更值得信赖。

一、是什么

在计算机领域，树形数据结构是一类重要的非线性数据结构，可以表示数据之间一对多的关系。以树与二叉树最为常用，直观看来，树是以分支关系定义的层次结构

二叉树满足以下两个条件：

  • 本身是有序树
  • 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2

如下图，左侧的为二叉树，而右侧的因为头结点的子结点超过2，因此不属于二叉树：

同时，二叉树可以继续进行分类，分成了满二叉树和完成二叉树：

满二叉树：如果二叉树中除了叶子结点，每个结点的度都为 2

完成二叉树：如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布

二、操作

关于二叉树的遍历，常见的有：

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历

前序遍历

前序遍历的实现思想是：

  • 访问根节点
  • 访问当前节点的左子树
  • 若当前节点无左子树，则访问当前节点的右子

根据遍历特性，递归版本用代码表示则如下：

 
 
 
 
    
  
  
  
  
  1. const preOrder = (root) => { 
    2. 
  
  
  
  
  2.   if(!root){ return } 
    3. 
  
  
  
  
  3.   console.log(root) 
    4. 
  
  
  
  
  4.   preOrder(root.left) 
    5. 
  
  
  
  
  5.   preOrder(root.right) 
    6. 
  
  
  
  
  6. } 
    7.

如果不使用递归版本，可以借助栈先进后出的特性实现，先将根节点压入栈，再分别压入右节点和左节点，直到栈中没有元素，如下：

 
 
 
 
    
  
  
  
  
  1. const preOrder = (root) => { 
    2. 
  
  
  
  
  2.   if(!root){ return } 
    3. 
  
  
  
  
  3.   const stack = [root] 
    4. 
  
  
  
  
  4.   while (stack.length) { 
    5. 
  
  
  
  
  5.     const n = stack.pop() 
    6. 
  
  
  
  
  6.     console.log(n.val) 
    7. 
  
  
  
  
  7.     if (n.right) { 
    8. 
  
  
  
  
  8.       stack.push(n.right) 
    9. 
  
  
  
  
  9.     } 
    10. 
  
  
  
  
  10.     if (n.left) { 
    11. 
  
  
  
  
  11.       stack.push(n.left) 
    12. 
  
  
  
  
  12.     } 
    13. 
  
  
  
  
  13.   } 
    14. 
  
  
  
  
  14. } 
    15.

中序遍历

前序遍历的实现思想是：

  • 访问当前节点的左子树
  • 访问根节点
  • 访问当前节点的右子

递归版本很好理解，用代码表示则如下：

 
 
 
 
    
  
  
  
  
  1. const inOrder = (root) => { 
    2. 
  
  
  
  
  2.   if (!root) { return } 
    3. 
  
  
  
  
  3.   inOrder(root.left) 
    4. 
  
  
  
  
  4.   console.log(root.val) 
    5. 
  
  
  
  
  5.   inOrder(root.right) 
    6. 
  
  
  
  
  6. } 
    7.

非递归版本也是借助栈先进后出的特性，可以一直首先一直压入节点的左元素，当左节点没有后，才开始进行出栈操作，压入右节点，然后有依次压入左节点，如下：

 
 
 
 
    
  
  
  
  
  1. const inOrder = (root) => { 
    2. 
  
  
  
  
  2.   if (!root) { return } 
    3. 
  
  
  
  
  3.   const stack = [root] 
    4. 
  
  
  
  
  4.   let p = root 
    5. 
  
  
  
  
  5.   while(stack.length || p){ 
    6. 
  
  
  
  
  6.     while (p) { 
    7. 
  
  
  
  
  7.       stack.push(p) 
    8. 
  
  
  
  
  8.       p = p.left 
    9. 
  
  
  
  
  9.     } 
    10. 
  
  
  
  
  10.     const n = stack.pop() 
    11. 
  
  
  
  
  11.     console.log(n.val) 
    12. 
  
  
  
  
  12.     p = n.right 
    13. 
  
  
  
  
  13.   } 
    14. 
  
  
  
  
  14. } 
    15.

后序遍历

前序遍历的实现思想是：

  • 访问当前节点的左子树
  • 访问当前节点的右子
  • 访问根节点

递归版本，用代码表示则如下：

 
 
 
 
    
  
  
  
  
  1. const postOrder = (root) => { 
    2. 
  
  
  
  
  2.   if (!root) { return } 
    3. 
  
  
  
  
  3.   postOrder(root.left) 
    4. 
  
  
  
  
  4.   postOrder(root.right) 
    5. 
  
  
  
  
  5.   console.log(n.val) 
    6. 
  
  
  
  
  6.  } 
    7.

后序遍历非递归版本实际跟全序遍历是逆序关系，可以再多创建一个栈用来进行输出，如下：

 
 
 
 
    
  
  
  
  
  1. const preOrder = (root) => { 
    2. 
  
  
  
  
  2.   if(!root){ return } 
    3. 
  
  
  
  
  3.   const stack = [root] 
    4. 
  
  
  
  
  4.   const outPut = [] 
    5. 
  
  
  
  
  5.   while (stack.length) { 
    6. 
  
  
  
  
  6.     const n = stack.pop() 
    7. 
  
  
  
  
  7.     outPut.push(n.val) 
    8. 
  
  
  
  
  8.     if (n.right) { 
    9. 
  
  
  
  
  9.       stack.push(n.right) 
    10. 
  
  
  
  
  10.     } 
    11. 
  
  
  
  
  11.     if (n.left) { 
    12. 
  
  
  
  
  12.       stack.push(n.left) 
    13. 
  
  
  
  
  13.     } 
    14. 
  
  
  
  
  14.   } 
    15. 
  
  
  
  
  15.   while (outPut.length) { 
    16. 
  
  
  
  
  16.     const n = outPut.pop() 
    17. 
  
  
  
  
  17.     console.log(n.val) 
    18. 
  
  
  
  
  18.   } 
    19. 
  
  
  
  
  19. } 
    20.

层序遍历

按照二叉树中的层次从左到右依次遍历每层中的结点

借助队列先进先出的特性，从树的根结点开始，依次将其左孩子和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是层次遍历的最终结果

用代码表示则如下：

 
 
 
 
    
  
  
  
  
  1. const levelOrder = (root) => { 
    2. 
  
  
  
  
  2.     if (!root) { return [] } 
    3. 
  
  
  
  
  3.     const queue = [[root, 0]] 
    4. 
  
  
  
  
  4.     const res = [] 
    5. 
  
  
  
  
  5.     while (queue.length) { 
    6. 
  
  
  
  
  6.         const n = queue.shift() 
    7. 
  
  
  
  
  7.         const [node, leval] = n 
    8. 
  
  
  
  
  8.         if (!res[leval]) { 
    9. 
  
  
  
  
  9.             res[leval] = [node.val] 
    10. 
  
  
  
  
  10.         } else { 
    11. 
  
  
  
  
  11.             res[leval].push(node.val) 
    12. 
  
  
  
  
  12.         } 
    13. 
  
  
  
  
  13.         if (node.left) { queue.push([node.left, leval + 1]) } 
    14. 
  
  
  
  
  14.         if (node.right) { queue.push([node.right, leval + 1]) } 
    15. 
  
  
  
  
  15.     } 
    16. 
  
  
  
  
  16.     return res 
    17. 
  
  
  
  
  17. }; 
    18.

三、总结

树是一个非常重要的非线性结构，其中二叉树以二叉树最常见，二叉树的遍历方式可以分成前序遍历、中序遍历、后序遍历

同时，二叉树又分成了完成二叉树和满二叉树

参考文献

https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91

http://data.biancheng.net/view/27.html

当前标题：面试官：说说你对树的理解？相关的操作有哪些？
标题链接：http://www.gawzjz.com/qtweb2/news5/2355.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

虚拟主机知识

同城分类信息

微信公众号开发　　 　小谭建站　　 　班戈纳美网站　　 　泸州洋跃建站　　 　成都ssl证书认证　　 　成都商城网站建设　　 　成都网站制作　　 　h5页面制作　　 　成都商城网站建设　　 　移动APP　　 　成都免费自助建站　　 　做手机网站　　 　攀枝花网站建设　　 　南充护栏钻孔机　　 　高防服务器租用　　 　seo推广公司　　 　绵阳梓潼网站建设　　 　成都二枢机房　　 　葆金莱自动门　　 　成都小程序开发