6.树和二叉树

《6.树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构第六章树和二叉树本章内容6.1树的概念与基本术语6.2二叉树6.3遍历二叉树6.4线索二叉树6.5树与森林6.6赫夫曼树6-36树【学习指南】本章是整个课程的学习重点，也是整个课程中的一大难点。这一章中我们从顺序式的数据结构，转向层次式的数据结构。考研的角度上：要掌握树、二叉树的各种性质；树和二叉树的不同存储结构；森林、树和二叉树之间的转换；线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和Huffman树)；重点要熟练掌握的，是森林、树以及二叉树的前中后三种遍历方式，要能进行相应的算法设计。这一部分是数据结构考题历来的重点和难点，复习时要特别

2、关注。6-4树（tree）是树型结构的简称，是一类重要的非线性结构，其中以树和二叉树最为常用。6树线性结构：一个挨着一个顺序排列实际问题：族谱丁一丁二丁五丁三丁六丁四丁七丁八丁九丁十丁十一线性结构存储：一二三四五六七八九十十一双亲？几代？孩子？（后代）6-5树型结构丁一层次结构丁二丁三丁四丁五丁六丁七丁八丁九丁十丁十一应用广泛：人类社会：族谱、行政管理计算机领域：编译程序中源程序的语法结构层次关系（DB中）目录结构6树6-6树的应用举例——目录结构MyComputerC:D:E:etcWINDOWSProgramFilesPictur

3、eMusic…………………………………………6树6-76.1树的概念与基本术语树的定义(Tree)树是有n(n≥0)个结点的有限集合。如果n=0，称为空树；如果n>0,称为非空树,对于非空树,有且仅有一个特定的称为根(Root)的节点(无直接前驱)如果n>1，则除根以外的其它结点划分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。每个结点都有唯一的直接前驱，但可能有多个后继树的举例其中：A是根；其余结点分成三个互不相交的子集，T1={B,E,F,K,L}；T2={C,G}；T3={D,

4、H,I,J,M},T1,T2,T3都是根A的子树，且本身也是一棵树ACGBDEFKLHMIJ有13个结点的树A只有根结点的树1)树的定义定义：树是由n(n≥0)个结点组成的有限集合。其中当n>0时n=0时，为空树。特点：有且仅有一个特定的称之为根(root)的结点；n>1时,除根外的其余结点被划分为m(m>0)个互不相交的有限集合T1,T2,…,Tm，每个集合本身又是一棵树，称之为根的子树(subTree)。非空树中至少有一个结点——根树中各子树是互不相交的集合6.1树的概念与基本术语6-9某结点不能同时属于两个子集两个子集的结点之间不能有关系子树“互不

5、相交”的含义6-10n=1n>16.1树的概念与基本术语A是根，其余结点可以划分为3个互不相交的集合：T1={B,E,F，K，L}T2={C,G}T3={D,H,I,J，M}6-11从逻辑结构看：1）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。JIACBDHGFEKLM6.1树的概念与基本术语结点(node):表示树中的元素及若干指向其子树的分

6、支结点的度(degree)：一个结点拥有子树的个数树的度(degree)：一棵树中所有结点的最大度数叶子(leaf)结点：度为0的结点分支(branch)结点：度不为0的结点孩子/子女(child)结点：某结点子树的根双亲(parent)结点:某结点是其子树根的双亲6.1树的概念与基本术语兄弟(sibling)结点：具有同一双亲的所有结点祖先(ancestor)结点：从根到该结点所经分支上的所有结点子孙(descendant)结点：以某个结点为根的子树中的任一结点结点的层数(level)：规定根结点层数为1，其余结点层数等于其双亲结点层数加1树的高度/深

7、度(depth)：树中叶子结点所在的最大层次有序树：树中每个结点的各个子树从左到右是有次序的（不能互换）无序树：子树的次序可以互换路径：若树中存在一个结点序列k1,k2…kj,使得ki是ki+1(1≤i≤j)的双亲，则称该序列是k1到kj的路径森林：是m(m0)棵互不相交的树的集合。6.1树的概念与基本术语结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点H的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F,G

8、为堂兄弟结点A是结点F，G的祖先JIACBDHGFEKLM6.1树的概念与基本术