《数据结构与算法 (24).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法 (24).pdf（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第8章树和森林8.1 树和森林的基本概念8.2 树的存储8.3 树和二叉树8.4 树的遍历第8章 树和森林1.树的定义树是由n(n0)个节点组成的有限集合，其中：当n0时，为空树；当n0时，有且仅有一个特定的节点，称为树的根，其余节点可分为m(m0)个互不相交的子集，其中每一个子集本身又是一棵树，并且称为根的子树。可见，树的定义也是一种递归定义。2.树结构特征：子树是不相交的；除了根结点外，每个结点有且仅有一个父结点；一棵N个结点的树有N-1条边。3(a)树树TABCDFGHIJKLMECHBFGLDIJKME(b)子树子树TA1(c)子树子树TA2(d)子树子树TA3(e)子树子树TA4树与
2、非树示例ABCDEFGHABCDEFGHABCDEFGH4结点层结点层：根结点的层定义为：根结点的层定义为1，其它依此类推；，其它依此类推；树的深度树的深度：树中最大的结点层；：树中最大的结点层；结点的度结点的度：结点子树的个数；：结点子树的个数；树的度树的度：树中最大的结点度；树中最大的结点度；叶子结点叶子结点：也叫终端结点，是度为：也叫终端结点，是度为 0 的结点；的结点；树的度为树的度为3树的深度为树的深度为4第第1层层第第3层层第第2层层第第4层层J JI IA AC CB BD DH HG GF FE EK KL LM M3.树的有关术语5分枝结点：分枝结点：度不为度不为0的结点；的
3、结点；有序树：有序树：子树有序的树，如：家族树；二叉树是一种特殊的有序子树有序的树，如：家族树；二叉树是一种特殊的有序树，但不是一般树的特例。树，但不是一般树的特例。无序树：无序树：不考虑子树的顺序；不考虑子树的顺序；3.树的有关术语64.森林：森林是m(m0)棵互不相交的树的集合。BCHGFEJIKDA树和森林的关系：树和森林的关系：（1）一棵树去掉根）一棵树去掉根，其子树构成一个森林；，其子树构成一个森林；（2）一个森林增加一个根结点成为树。）一个森林增加一个根结点成为树。78.1 树和森林的基本概念8.2 树的存储结构8.3 树和二叉树8.4 树的遍历第8章树和森林8 树的孩子兄弟表示法
4、：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。结点结构及类型定义如下：firstChilddatanextSibling长子域长子域数据域数据域兄弟域兄弟域typedef struct CSNodeElem data;struct CSNode*firstChild,*nextSibling;CSNode,*CSTree;910RBACDEFKHGRABECDGHFK树的孩子兄弟表示法图示与二叉树的二叉链表存储表示形式一样，但含义不同8.1 树和森林的基本概念8.2 树的存储8.3 树、森林和二叉树8.4 树的遍历第第8章章 树和森林树和森林1
5、1ACBED树树ABCDE二叉树二叉树A BC D E A BCDE 孩孩子子兄兄弟弟表表示示法法二二叉叉链链表表对应1.树和二叉树对应关系示例12树孩子兄弟表示法和二叉树的二叉链表表示法具有一致性，只是左右孩子表达的逻辑关系不同：二叉树：左右孩子；树的二叉链表：第一个孩子结点和右边第一个兄弟结点。1.树和二叉树对应关系把树和二叉树对应起来如何把树的转化成二叉树？如何把树的转化成二叉树？132.树转换为二叉树 树中所有相邻兄弟之间加一条连线。AEDCBHGF 对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。14 以树的根结点为轴心，将整棵树顺时针旋转一定的
6、角度，使之结构层次分明。如图所示，是树转换为二叉树示例图。AEDCBHGFAEDCBHGF153.森林转换为二叉树 将森林中的每棵树转换成相应的二叉树。将各二叉树的根结点连在一起。ADCBJIHGEFDCFJIEABDCFHGJI164.二叉树转换为树或森林，具体方法如下：若某结点 x 是其父结点 y 的左孩子，则把该结点 x的右孩子、右孩子的右孩子都与 y 节点用线连起来。删掉原二叉树中所有父结点与右孩子结点的连线。DCIEABFHGJEFADCBJIHG17 8.4.1 树的遍历树的遍历8.4.2 森林的遍历森林的遍历8.4 树(森林)的遍历18遍历：按一定规律走遍树的各个顶点，且使每一顶
7、点仅被访问一次，得到树中所有结点的一个线性排列。树的遍历有：先根（序）遍历、后根（序）遍历和层次遍历三种方式。191.树的先序（根）遍历过程：（1）若T为空，遍历结束；（2）若T非空，先访问T根结点，然后从左到右依次先序遍历访问根结点的每棵子树。A A B B E E F F G G K K C C H H D D I I J J 例子：以先序遍历方式访问如图所示的树。解：解：A-B-E-F-K-G-C-H-D-I-J20 树的先根遍历递归算法树的先根遍历递归算法void preordertre(CSnode*root)/*root 树的根结点树的根结点*/if(root!=NULL)visi
8、t(root-data);/*访问根结点访问根结点*/preordertre(root-firstchild);preordertre(root-nextsilbing);212.树后序（根）遍历过程：（1）若T为空，则遍历结束；（2）若T非空，则从左到右依次后序遍历根结点的各子树，然后访问根结点。例子：例子：以以后序后序遍历方式访问如图所示的二叉树。遍历方式访问如图所示的二叉树。解：解：E-K-F-G-B-H-C-I-J-D-A A A B B C C D D E E F F G G H H I I J J K K 22讨论：若采用“先转换，后遍历”方式，结果是否一样？abdec先序遍历：后序遍历：中序遍历：d e c b aabdeca b c d eb d c e a1.树的先根遍历与对应二叉树的先序遍历序列相同；2.树的后根遍历相当于对应二叉树的中序遍历；3.树没有中序遍历，因为子树无左右之分。结论：23ABCDEFGHIJKLMNO先序遍历：先序遍历：后序遍历：后序遍历：层次遍历：层次遍历：ABEFI GCDHJ KLNOMEIFGBCJKNOLMHDAABCDEFGHIJ KLMNO24