《算法与数据结构》第4章 树与二叉树ppt

《《算法与数据结构》第4章 树与二叉树ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与数据结构第4章树与二叉树树和二叉树在前两章讨论的数据结构都属于线性结构。线性结构的逻辑结构简单，易于实现各种运算和操作，主要用于描述客观世界中具有单一前趋和单一后继的数据关系。然而，客观世界中的许多事物的关系并非如此简单，如人类社会中的族谱、各种社会组织机构、交通道路和通讯网络等，其中的联系都是较为复杂的非线性关系，宜用非线性结构来描述其数据关系。树与二叉树中，每个数据元素至多只有一个前趋，但可以有多个后继；数据元素间的关系是一对多的层次关系，主要用于描述客观世界中具有层次结构的数据关系。第4章树与二叉树4.1树的基本概念

2、4.2二叉树4.3二叉树的遍历4.4线索二叉树4.5树和森林4.6哈夫曼树4.1树的基本概念4.1.1树的定义及表示4.1.2树的常用术语及运算树的定义及表示客观世界中的许多事物的关系可以用树来描述，如人类社会中家族成员之间的血缘关系，以英国女王家族为例可表示成如下图所示。上图看上去很像一棵倒置的树，树型结构便由此而得名。树的递归定义树（tree）是n（n≥0）个结点的有限集合T。当n=0时称为空树，否则称为非空树。在任一非空树中，①有且仅有一个称为树的根的结点；②除根结点之外的其余结点可分为m（m≥0）个互不相交的集合T1，T

3、2，…，Tm，其中每个集合本身又都是一棵树，并且称为根的子树。这是一个递归定义，即在树的定义中又用到了树这个术语，它反映了树的固有特性：即一棵树由若干棵子树构成，而每棵子树又都分别由若干棵更小的子树构成。树的递归定义（续）这个树的递归定义可以从如下三点来理解：没有任何结点的树称为空树，这是树的特例。非空树中至少有一个结点，只有一个结点时它就是树的根，只有根结点的树称为最小非空树。在含有多个结点的树中，除根结点外其余结点构成若干棵子树，且各子树间互不相交。树的示例下图中，(a)是只有一个根结点的树。(b)是有六个结点的一般树，其中

4、A是根，其余结点分成三个互不相交的子集：T1={B}，T2={C，E，F}，T3={D}；T1、T2和T3是A的子树，且其本身也都是一棵树；其中，T1的根为B其子树为空树，T3的根为D其子树为空树，T2的根为C剩余结点分成两个互不相交的子集T21={E}和T22={F}，T21和T22都是C的子树。树的非递归定义树的非递归定义可以叙述为：称数据结构tree(D,R)为树，则R中只有一个关系，且满足以下条件：(1)有且仅有一个没有前趋的结点w，称为树的根；(2)除根w外的每一个结点都有且只有一个前趋；(3)对于除根w外的每一个结点

5、K，都有一个从根w到k的一个结点序列K0(w)，K1，K2，…，Ki-1，Ki，…，Kn(k)（n≥1），其中Ki是Ki-1的后继。这个非递归定义中的(1)和(2)容易理解；对于(3)以前一页的图(b)中的任一结点如E说明一下，从根A到E存在一个线性序列A、C、E，序列中后一个结点是它前面一个结点的后继，即C是A的后继，E是C的后继。树的表示通常树的表示方法有树形表示、嵌套集合表示、凹入表示和广义表表示四种，如下图所示：4.1树的基本概念4.1.1树的定义及表示4.1.2树的常用术语及运算树常用的基本术语树的结点：是指一个数据元

6、素及其若干指向其子树的分支，通常用一个记录或结构体来描述，在树形表示中用一个圆圈及短线来表示。结点的度：是指结点拥有的子树数目。如右图中，结点A的度为3，C的度为2，B、D、E、F的度为0。叶子或终端结点：是指度为0的结点，如右图)中的B、D、E、F都是叶子结点。分支结点或非终端结点：是指度不为0的结点，如右图中的A和C结点；通常又把非根的分支结点称为内部结点，如右图中的C结点。树的度：是指树中各结点度的最大值，如右图中的树的度为3。树常用的基本术语（续）结点的层次：从根结点开始，根为第一层，根的孩子为第二层，依次类推。如右上图

7、中的A在第一层，B、C、D在第二层，E和F在第三层。树的深度或高度：是树中结点的最大层次数。如右上图中的树高度为3。有序树和无序树：如果将树中结点的各子树看成是从左到右依次有序且不能交换，则称该树为有序树，否则称为无序树。如右下图给出了两棵不同的有序树。森林：是m棵互不相交的树的集合。删除一棵树的根就会得到由子树构成的森林；反之，给森林加上一个根就会变成为一棵树。树的其它术语有时也引用家族树中的一些习惯用语，如孩子、双亲、祖先、子孙、兄弟等。如称结点的子树的根为该结点的孩子，该结点称为孩子的双亲；同一个双亲的孩子之间互称为兄弟；

8、从结点向上到达根结点所途经的所有结点称为该结点的祖先，从结点向下所能到达的所有结点称为该结点的子孙。如右图中，A是B、C和D的双亲，B、C和D都是A的孩子，B、C和D三者之间互为兄弟；A和C是E的祖先，A的子孙是B、C、D、E和F。树的基本运算setnull(T