可以做四级听力的网站,wordpress连接公众号,国外设计网站pinterest网址,西安建站目录 一、树
1.1树的存储结构
1.1.1双亲表示法
1.1.2孩子链表
1.1.3孩子兄弟表示法
1.2树与二叉树的转换
1.2.1将树转换成二叉树#xff1a; 1.2.2将二叉树转换成树
二、森林
2.1森林与二叉树的转换
2.1.1将森林转换成二叉树
2.1.2二叉树转换成森林
三、树和森林的…目录 一、树
1.1树的存储结构
1.1.1双亲表示法
1.1.2孩子链表
1.1.3孩子兄弟表示法
1.2树与二叉树的转换
1.2.1将树转换成二叉树 1.2.2将二叉树转换成树
二、森林
2.1森林与二叉树的转换
2.1.1将森林转换成二叉树
2.1.2二叉树转换成森林
三、树和森林的遍历
3.1树的遍历
3.2森林的遍历
3.2.1先序遍历 3.2.2中序遍历 一、树
1.1树的存储结构
1.1.1双亲表示法
实现定义结构数组存放树的结点每个结点含两个域
数据域——存放结点本身信息双亲域——指示本结点的双亲结点在数组中的位置 根结点数组下标为0个数n10
找双亲容易找孩子难
1.1.2孩子链表 孩子结点结构child next 双亲结构特点 data firstchild
找孩子容易找双亲难
带双亲的孩子链表 1.1.3孩子兄弟表示法
实现用二叉链表作树的存储结构链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。 1.2树与二叉树的转换 给定一棵树可以找到唯一的一棵二叉树与之对应。
1.2.1将树转换成二叉树
①加线在兄弟之间加一条线
②抹线对每个结点除了其左孩子外去除其与其余孩子之间的关系
③以树的根结点为轴心将整树顺时针旋转45°
树变二叉树兄弟相连留长子
例 1.2.2将二叉树转换成树
①加线若p结点时双亲结点的左孩子则将p的右孩子右孩子的右孩子沿分支找到的所有右孩子都与p的双亲用线连起来
②抹线抹掉原二叉树中双亲与右孩子之间的连线
③调整将结点按层次排列形成树结构
二叉树变树左孩右右连双亲去掉原来右孩线
例 二、森林
2.1森林与二叉树的转换
2.1.1将森林转换成二叉树
①将各棵树分别转换成二叉树
②将每棵树的根结点用线相连
③以第一棵树的根结点作为二叉树的根再以根结点为轴心顺时针旋转构成二叉树型结构
森林变二叉树树变二叉根相连
例 2.1.2二叉树转换成森林
①抹线将二叉树中根结点与其右孩子连线及沿有分支搜索到的所有右孩子间连线全部抹掉使之变成孤立的二叉树
②还原将孤立的二叉树还原成树
二叉树变森林去掉全部右孩线孤立二叉再还原
例 三、树和森林的遍历
3.1树的遍历
先根遍历若树不空则先访问根结点再依次先根遍历各棵子树
后根遍历若树不空则先依次后根遍历各棵子树然后访问根结点
层次遍历若树不空则自上而下自左至右访问树中每个结点
例 3.2森林的遍历
把森林看作由三部分构成
①森林中第一棵树的根结点
②森林中第一棵树的子树森林
③森林中其他树构成的森林 3.2.1先序遍历
若森林不空则
①访问森林中第一棵树的根结点
②先序遍历森林中第一棵树的子树森林
③先序遍历森林中除第一棵树之外其余树构成的森林
即依次从左至右对森林中的每一棵树进行先根遍历
例 3.2.2中序遍历
若森林不空则
①中序遍历森林中第一棵树的子树森林
②访问森林中第一棵树的根结点
③中序遍历森林中除第一棵树之外其余树构成的森林
即依次从左至右对森林中的每一棵树进行后根遍历
例
