ppt第七章总结
树结构中常用的基本术语
父结点：若一个节点有子树，则该结点为父结点。孩子结点：一个结点子树的根。兄弟结点：同一个结点的孩子。
层次：根结点的层次为1，其余结点的层次是其父结点的层次加1。高度（深度）：树中结点的最大层次数。度：一个结点的孩子数目是这个结点的度。如：图中A的度为2叶子结点：度为0的结点。分支结点：度不为0的结点。树的度：树中结点的最大的度。
有序树/无序树：兄弟结点之间的排列是否有序。森林：
森林是m(m≥0)棵互不相交的树的集合。即：森林是多棵树。
EGA
HIDFCB
J树的存储:
1双亲表示法2孩子表示法
3孩子兄弟表示法双亲表示法:
实现：定义结构数组存放树的结点，每个结点含两个域数据域：存放结点本身信息
双亲域：指示本结点的双亲结点在数组中位置特点：找双亲容易，找孩子难.孩子表示法:实现：
(1)把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表；n个结点共有n个孩子链表（叶子结点的孩子链表为空表）。
(2)n个结点的数据和n个孩子链表的头指针组成一个顺序表。孩子兄弟表示法:实现：
用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。特点：
(1)操作容易
(2)破坏了树的层次
树(森林)与二叉树的转换:一、树转换为二叉树二、森林转换为二叉树
三、二叉树转换为树或森林
一、树转换为二叉树:
将一棵树转换为二叉树的方法是：
(1)树中所有相邻兄弟之间加一条连线。
(2)对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连
(3)以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。
下图是树转换为二叉树的结果示意图。
二、森林转换为二叉树:
森林转换为二叉树的方法如下：
(1)将森林中的每棵树转换成相应的二叉树。(2)将各二叉树的根结点连在一起。
三、二叉树转换为树或森林:
二叉树转换为树或森林，具体方法如下：
(1)若某结点x是其父结点y的左孩子，则把该结点x的右孩子、右孩子的右孩子……都与y用线连起来。(2)删掉原二叉树中所有父结点与右孩子结点的连线。
树的遍历:
遍历按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列。常用方法：
先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树；后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点；
按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点。
森林的遍历:先序遍历：若森林为空，返回；访问森林中第一棵树的根结点；
先序遍历第一棵树中根结点的子树森林；
先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历：
若森林为空，返回；
中序遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点；
中序遍历除去第一棵树之后剩余的树构成的森林。
结论：
当以二叉链表做树的存储结构时，树的先根序列和后根序列可借用二叉树的先序遍历和后序遍历的算法实现之；对于森林也一样。
习题：
1、已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，问该树中有多少片叶子？2、分别画出下图所示的森林的双亲表示形式、孩子链表表示形式和二叉链表表示形式。
3、将上图的森林转换为对应的二叉树。
扩展阅读：ppt第一章总结
数据是信息的载体数据元素是数据的基本单位数据项具有独立含义的最小标识单位
数据类型可分为两类：简单数据类型、结构数据类型
数据结构包含3个内容：数据的逻辑结构、数据的存储结构和数据的运算集合。数据的逻辑结构：
线性逻辑结构：元素之间一对一关系树型逻辑结构：元素之间一对多关系图型逻辑结构：元素之间多对多关系集合逻辑结构
数据的存储结构存储方式有四种：
顺序存储：逻辑上相邻的结点存储在物理位置相邻的存储单元中链接存储：逻辑上相邻的结点不一定存储在物理位置相邻的存储单元
索引存储：在存储结点信息的同时，建立附加的索引表。散列存储：应用一个函数，将每一个结点的关键字作为该函数的自变量，得到相应的函数值作为该结点的存储地址。顺序表线性结构栈队列数据的逻辑结构串及数组树形结构非线性结构数据结构图形结构散列结构顺序存储链式存储数据的存储结构索引存储散列存储
数据的运算：检索、排序、插入、删除、修改例题：已知定义：intx，*k=&x；试问：表达式*k，&x，*&x，&*k，&*x和*&k各表示什么？答：对于*k，表示变量x。
对于&x，&是地址运算符，&x表示变量x的地址。对于*&x，表示*k，即变量x。
对于&*k，*k表示变量x，&*k即表示变量x的地址(&x)。对于*&k，表示变量k。而&*x则存在语法错误。
等等算法性能分析：1、算法的时间性能分析2、算法的空间性能分析【例】for(i=1;i习题4、计算下列各程序段的时间复杂度(1)for(i=0；i
友情提示：本文中关于《ppt第七章总结》给出的范例仅供您参考拓展思维使用，ppt第七章总结：该篇文章建议您自主创作。
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
《ppt第七章总结》
由互联网用户整理提供,转载分享请保留原作者信息,谢谢!
http://m.bsmz.net/gongwen/736996.html
- 上一篇：食品安全总结
- 下一篇：八月份工作总结