算法笔记树

以你之姓@ 2022-06-01 01:11 107阅读 0赞

1.  树的定义和性质  
    现实中的树是由树根，茎干，树叶组成的，树的营养时由树根出发，通过茎干与树枝来不断传递，最终到达树叶的。在数据结构中，树则是用来概括这种传递关系的一种数据结构。为了简化，数据结构中把树枝分叉处，树叶，树根抽象为结点，其中树根抽象为根结点，且对一棵树来说最多存在一个根结点；把树叶概括为叶子结点，且叶子结点不再延伸出新的结点；把茎干和树枝统一抽象为边，且一条边只用来连接两个结点(一个端点一个)。这样，树就被定义为由若干个结点和若干条边组成的数据结构，且在树中的结点不能被边连接成环。在数据结构中，一般把根节点置于最上方（与现实中的树恰好相反），然后向下延伸出若干条边到达子结点（从而向下形成子树），而子结点又向下延伸出边并连接一些结点……直至到达叶子结点，看起来就像是把现实中的树颠倒过来的样子。  
    ![这里写图片描述][SouthEast]  
    下面给给出几个比较使用实用的概念概念和性质，其中性质①⑤经常被用来出边界数据：  
    ①树可以没有结点，这种情况下把树称为空树；  
    ②树的层次从根结点开始算起，即根结点为第一层，根结点子树的根结点为第二层，以此类推；  
    ③把结点的子树棵树称为结点的度，而树中结点的最大的度称为树的度（也称为数的宽度），如上图三棵树的度分别为2，3，5.  
    ④由于一条边连接两个结点，且树中不存在环，因为对此有n个结点的树，边数一定是n-1.且***满足连通，边数等于顶点数减一的结构一定是一棵树。***  
    ⑤叶子结点被定义为度为0的结点，因此当树中只有一个结点（即只有根结点）时，根结点也算作叶子结点；  
    ⑥结点的深度是指从根结点（深度为1）开始自顶向下逐层累加至该结点时的深度值；结点的高度是指从最底层叶子结点（高度为1）开始自底向上逐层累加至该结点时的高度值。树的深度是指树中结点的最大深度，树的高度是指树中结点的最大高度。对树而言，深度和高度是相等的，例如上图中的三棵树的深度高度分别为4，4，2，但是具体到某个结点来说深度和高度就不一定相等了。  
    ⑦多棵树组合在一起称为森林，即森林就是若干棵树的集合。

> 摘自《算法笔记》胡凡，曾磊主编

[SouthEast]: /images/20220601/8f24b00df8304bc3bac616afab5f1a32.png