树Tree

基本认知Basic

树 和 图

树中不能出现环

计算机的树 一般往下长

结点相关名词

Depth

结点深度

距离根结点有几条边

Level

结点层级

距离根结点的边数 + 1

Height

树的高度

深度最高的结点深度

树 和 二叉树

二叉树

Full Binary Tree

每个 Branch 节点 都有 两个 Leaf

构建

使用链结构构建

一般树

1 2 3 
public class Node {    public List<Node> subNodes;}

二叉树

1 2 3 4 
public class Node {    public Node leftNodes;    public Node rightNodes;}

一般树 追溯父节点

1 2 3 4 
public class Node {    public List<Node> subNodes;    public Node parent;}

使用数组构建

案例

[1, 2, 3, _, _, 4, 5]
[1, 2, 3, 4, 5, 6, _]
[1, 2, 3, 4, 5, 6, 7]

找关系

parent: (index - 1) / 2
left child: index * 2 + 1
right child: index * 2 + 2

遍历

前序Preorder

一般树

第一次访问的时候记录

二叉树

第一次访问的时候记录

中序Inorder

一般树

没有中序遍历

二叉树

左子节点访问完了，再记录

后序Postorder

一般树

所有子节点都访问完了，再记录

二叉树

所有子节点都访问完了，再记录

逐层

等同 BFS 顺序