《算法笔记》树与二叉树专题

一、树与二叉树

1、树的定义与性质

• 结点（node）：树枝分叉处、树叶、树根；
• 根结点（root）：树根，对一棵树来说最多存在一个根结点；
• 叶子结点（leaf）树叶，叶子结点不再延伸出新的结点；
• 边（edge）：茎秆和树枝，一条边只用来连接两个结点；

性质：

• 数可以没有结点，称为空树（empty tree）；
• 树的层次（layer）从根结点开始算起，根结点为第一层，根结点子树的根结点为第二层，以此类推；
• 把结点的子树棵树称为结点的度（degree），而树中结点的最大的度为树的度（树的宽度）；
• 由于一条边连接两个结点，且树中不存在环，所以有n个结点的树，边数是n-1，满足连通、边数等于顶点数-1的结构是一棵树；
• 叶子结点是度为0的结点，当树中只有一个结点时（只有根结点），根结点也算作叶子结点；
• 结点的深度（depth）：从根结点（深度为1）开始自顶向下逐层累加至该节点时的深度值；结点的高度（height）：从最底层叶子结点开始自底向上逐层累加至该节点时的高度值；
• 森林&