本页目录

8.1 树型结构定义

发布时间:

定义：树型结构是一层次的嵌套结构，树是递归定义的。

二叉树 ​

节点：包含一个数据元素及若干指向子树的信息。
1. 叶子节点：终端节点
2. 分支节点：非终端节点，根节点

子树：分支节点链接的下一层树。
1. 左子树
2. 右子树

度：
1. 节点的度：一个节点拥有子树的数目称为节点的度
2. 树的度：树中所有节点的度的最大值（二叉树子节点一定不大于2） 3. 树的深度：树节点的最大层数成为树的深度（depth）或高度，层数从根开始，根为第一层。

二叉树遍历 ​

先序遍历
1. 访问根节点
2. 先序遍历左子树
3. 先序遍历右子树
根->左->右

中序遍历
1. 中序遍历左子树
2. 访问根节点
3. 中序遍历右子树
左-> 根->右

后序遍历
1. 后续遍历左子树
2. 后续遍历右子树
3. 访问根节点
左->右 -> 根

js 
           1
        /     \
      2         3
    /    \          \
  4       5          6
 /                  /   \
7                   8    9