数据结构----树及二叉树的遍历JS

喜欢ヅ旅行 2023-10-09 11:16 15阅读 0赞

**树：**  
一种非顺序数据结构-树，它对于存储需要快速查找的数据非常有用。

相关概念：

*  根节点：位于树顶部的节点，没有父节点；
 *  内部节点：至少有一个子节点的节点（7，5，9，15，13，20）；
 *  外部节点（叶节点）：没有子元素的节点（第3层）；
 *  子树：由节点和它的后代构成（节点13，12，14构成了一个子树）；
 *  深度：节点的深度取决于它的祖先节点的数量；
 *  高度：取决于所有节点深度的最大值。

# 二叉树 #

二叉树是另一种特殊的树形结构，它的特定是每个至多有两棵树，二叉树的子节点有左右之分，其次序不能任意颠倒。二叉树的结构简单，存储效率较高，运算的算法也相对简单。并且任何树或森林与二叉树之间可以通过简单的操作规则相互转换，在树的应用中，它起着举足轻重的作用。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70]

## 二叉树的存储结构 ##

### 1.顺序存储结构 ###

用一组连续的存储单元依次自上而下，自左至右存储完全二叉树上的结点元素，即将二叉树上编号为i的结点元素存储在加上定义的一维数组中下标为i-1的分量中。“0”表示不存在此结点。这种顺序存储结构仅适用于完全二叉树。  
因为，在最坏情况下，一个深度为k且只有k个结点的单支树（树中不存在度为2的结点）却需要长度为2的n次方-1的一维数组。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 1]

### 2.链式存储结构 ###

二叉树的结点由一个数据元素和分别指向其左右子树的两个分支构成，则表示二叉树的链表中的结点至少包含三个域：数据域和左右指针域。有时，为了便于找到结点的双亲，则还可在结点结构中增加一个指向其双亲结点的指针域。利用这两种结构所得的二叉树的存储结构分别称之为二叉链表和三叉链表。  
在含有n个结点的二叉链表中有n+1个空链域，我们可以利用这些空链域存储其他有用信息，从而得到另一种链式存储结构—线索链表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 2]

## 二叉树的遍历 ##

前序遍历：根节点->左子树->右子树
    
    中序遍历：左子树->根节点->右子树
    
    后序遍历：左子树->右子树->根节点

![在这里插入图片描述][20190925100325575.png]

*  前序遍历：abdefgc
 *  中序遍历：debgfac
 *  后序遍历：edgfbca

### 中序遍历： ###

一种应用是对树进行排序操作。

this.inOrderTraverse = function {
        callback} {
        
      inOrderTraverse(root, callback); // 回调函数用来处理遍历到的每个节点
    };
    
    var inOrderTraverseNode = function (node, callback) {
        
      if (node !== null) {
        
        inOrderTraverseNode(node.left, callback);
        callback(node.key);
        inOrderTraverseNode(node.right, callback);
      }
    }

### 先序遍历： ###

一种应用是打印一个结构化的文档。

this.preOrderTraverse = function (callback) {
        
      preOrderTraverseNode(root, callback);
    }
    
    var preOrderTraverseNode = function (node, callback) {
        
      if (node !== null) {
        
        callback(node.key);
        preOrderTraverseNode(node.left, callback);
        preOrderTraverseNode(node.right, callback);
      }
    }

### 后序遍历： ###

一种应用是计算一个目录和它的子目录中所有文件所占的空间大小。

this.postOrderTraverse = function (callback) {
        
      postOrderTraverse(root, callback);
    }
    
    var postOrderTraverse = function (callback) {
        
      if (node !== null) {
        
        postOrderTraverse(node.left, callback);
        postOrderTraverse(node.right, callback);
        callback(node.key);
      }
    }

参考：  
[我对JS树的简单学习][JS]  
[javascript实现数据结构： 树和二叉树,二叉树的遍历和基本操作][javascript_]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190925103238460.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190925103720842.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190925103736533.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5,size_16,color_FFFFFF,t_70
[20190925100325575.png]: https://img-blog.csdnimg.cn/20190925100325575.png
[JS]: https://segmentfault.com/a/1190000009041222
[javascript_]: https://www.cnblogs.com/webFrontDev/p/3865719.html