注意：树和二叉树是两种数据结构，但都属于树形结构而已。

树

  • 树是一个或多个节点的集合；
  • 树必须有一个根节点；

即 树至少有一个根节点，子树可以为0。

相关概念

  1. 度 - 子节点的个数；
  2. 叶 - 度为0的节点；
  3. 分支节点 - 非叶的节点；
  4. 级 - 节点到根节点的距离；
  5. 有序树 - 认为A(B,C)和A(C,B)是不同的树；
  6. 森林 - m≥0个不相交的树的集合。

    二叉树

  • 二叉树是m≥0节点的集合T；
  • T要么为空，要么由一个根节点和两个二叉树组成。

即 每个节点必须有两个子节点，且子节点可以为空。

树和二叉树的区别

  • 区别
    • 二叉树可以为空，但是树不可以；
    • 二叉树每个节点的度不大于2，但是树是没有限制的；
    • 二叉树是有序的，但是树分为有序树和无序树。
  • 二叉树 VS 度最大为2的有序树
    • 两者也是不一样的
    • 对于二叉树来说，空节点也是节点，但是对于树来说是没有空节点的。

image.png

表示树结构的形式

  1. 画图

image.pngimage.png

  1. 括号

image.png

  1. 图书目录

image.png

  1. 代码表示

    1. const node1 = {
    2.  value: 12, left: node2, right: node3
    3. }
    4. const binaryTree1 = {
    5. value: 'A',
    6. left: {
    7.  value: 'B',
    8.  left: {value: 'C', left:null, right:null},
    9.  right: null
    10. },
    11. right: {
    12.  value: 'D',
    13.  left: {value: 'E', left:null, right:null},
    14.  right: {value: 'F', left:null, right:null},
    15. }
    16. }

    树可以表示的内容

  2. 公司结构

  3. 公式

image.png

  1. 代码 - AST

    将扁平结构变成树