树

树形结构中的重要术语

1.节点: 树里面的元素

2.父子关系: 节点之间相连的边

3.子树: 当节点大于1时,其余的节点分为互不相交的集合称为子树

4.度: 一个节点拥有的子树数量称为节点的度

5.叶子: 度为0的节点

6.孩子: 节点的子树的根称为孩子节点

7.双亲: 和孩子节点对应

8.兄弟: 同一个双亲节点

9.森林: 由n个互不相交的树构成森林

10.节点的高度 节点到叶子节点 的最长路径

11.节点的深度: 根节点到该节点的边个数

12.节点的层数: 节点的深度+1

13.树的高度:根节点的高度

二叉树

binary tree : 一种特殊的树形结构,每个节点至多只有2颗子树

在二叉树的第N层上至多有2^(n-1)个节点,最多有2^n-1个节点个数

满二叉树 :除叶子节点外,每个节点都有左右两个子节点

完全二叉树:除最后一层外,其他的节点个数必须达到最大,并且最后一层节点都连续靠左排列

二叉树的四种遍历方式

重要口诀:根节点输出

前序 根 左 右

中序 左 根 右

后续 左 右 根

层次  (使用队列 将数据放入到队列中)