算法速成（十一）树操作之基本操作

算法速成（十一）树操作之基本操作2014-04-28 csdn 特种兵—AK47先前我们讲的都是“线性结构”，他的特征就是“一个节点最多有一个”前驱“和一个”后继“ 。那么我们今天讲的树会是怎样的呢？

我们可以对”线性结构“改造一下，变为”一个节点最多有一个"前驱“和”多个后继“。哈哈，这就是我们今天说的”树“。

一：树

我们思维中的”树“就是一种枝繁叶茂的形象，那么数据结构中的”树“该是怎么样呢？对的，他是一种现实中倒立的树。

1：术语

其实树中有很多术语的，这个是我们学习树形结构必须掌握的。

<1> 父节点，子节点，兄弟节点

这个就比较简单了，B和C的父节点就是A ，反过来说就是B和C是A的子节点。B和C就是兄弟节点。

<2> 结点的度

其实”度“就是”分支数“，比如A的分支数有两个“B和C",那么A的度为2。

<3> 树的度

看似比较莫名其妙吧，他和”结点的度“的区别就是，树的度讲究大局观，乃树中最大的结点度，其实也就是2。

<4> 叶结点，分支结点

叶结点就是既没有左孩子也没有右孩子结点，也就是结点度为0。分支节点也就是if的else的条件咯。

<5> 结点的层数

这个很简单，也就是树有几层。

<6> 有序树，无序树

有序树我们先前也用过，比如“堆”和“二叉排序树”，说明这种树是按照一定的规则进行排序的，else条件就是无序树。

<7> 森林

现实中，很多的树形成了森林，那在数据结构中，我们把上图的“A”节点砍掉，那么B，C子树合一起就是森林咯。

2: 树的表示

树这个结构的表示其实有很多种，常用的也就是“括号”表示法。

比如上面的树就可以表示为：（A（B（D）,（E））,（C（F）,（G）））