当前位置: 首页 > news >正文

数据结构(五)——树森林

5.4 树和森林

5.4.1 树的存储结构

树的存储1:双亲表示法
用数组顺序存储各结点,每个结点中保存数据元素、指向双亲结点(父结点)的“指针”

#define MAX_TREE_SIZE 100// 树的结点
typedef struct{ElemType data;int parent;
}PTNode;// 树的类型
typedef struct{PTNode nodes[MAX_TREE_SIZE];int n;	//结点数量
}PTree;


优点:找双亲(父结点)很方便
缺点:找孩子不方便,只能从头到尾遍历整个数组

树的存储2:孩子表示法(顺序+链式存储)

#define MAX_TREE_SIZE 100struct CTNode{int child;	//孩子结点在数组中的位置struct CTNode *next;	//下一个孩子
}typedef struct{ElemType data;struct CTNode *firstChild;	//第一个孩子
}CTBox;typedef struct{CTBox node[MAX_TREE_SIZE];int n,r;	//结点数和根的位置
}CTree;

优点:找孩子很方便
缺点:找双亲(父结点)不方便,只能遍历每个链表

树的存储3:孩子兄弟表示法
树的孩子兄弟表示法与二叉树类似,采用二叉链表实现,每个结点内保存数据元素和两个指针,但两个指针的含义和二叉树结点不同

//孩子兄弟表示法结点
typedef struct CSNode{ElemType data;struct CSNode *firstchild, *nextsibling;	//第一个孩子和右兄弟结点
}CSNode, *CSTree;

 

5.4.2 树、森林与二叉树的转换

树到二叉树的转换
①先在二叉树中,画一个根节点。
②按“树的层序”依次处理每个结点。
处理一个结点的方法是:如果当前处理的结点在树中有孩子,就把所有孩子结点 “用右指针串成糖葫芦”,并在二叉树中把第一个孩子挂在当前结点的左指针下方

森林到二叉树的转换
①先把所有树的根结点画出来,在二叉树中用右指针串成糖葫芦。
②按“森林的层序”依次处理每个结点。
处理一个结点的方法是:如果当前处理的结点在树中有孩子,就把所有孩子结点“用右 指针串成糖葫芦”,并在二叉树中把第一个孩子挂在当前结点的左指针下方

注意:森林中各棵树的根节点视为平级的兄弟关系

二叉树到树的转换
①先画出树的根节点
②从树的根节点开始,按“树的层序”恢复每个结点的孩子
如何恢复一个结点的孩子:在二叉树中,如果当前处理的结点有左孩子,就把左孩 子和“一整串右指针糖葫芦” 拆下来,按顺序挂在当前结点的下方


二叉树到森林的转换
①先把二叉树的根节点和“一整串右指针糖葫芦”拆下来,作为多棵树的根节点
②按“森林的层序”恢复每个结点的孩子
如何恢复一个结点的孩子:在二叉树中,如果当前处理的结点有左孩子,就把左孩子和“一整串右指针糖葫 芦” 拆下来,按顺序挂在当前结点的下方


5.4.3 树和森林的遍历

树的先根遍历。若树非空,先访问根结点, 再依次对每棵子树进行先根遍历。(深度优先遍历)

void PreOrder(TreeNode *R){if(R!=NULL){visit(R);while(R还有下一个子树T)PreOrder(T);}
}

树的先根遍历序列与这棵树相应二叉树的先序序列相同

树的后根遍历。若树非空,先依次对每棵子树进行后根遍历,最后再访问根结点。(深度优先遍历)

树的后根遍历序列与这棵树相应二叉树的中序序列相同。

树的层次遍历(用队列实现):(广度优先遍历)
   ①若树非空,则根节点入队
   ②若队列非空,队头元素出队并访问,同时将该元素的孩子依次入队
   ③重复②直到队列为空

森林的先序遍历
森林。森林是m (m>0)棵互不相交的树的集合。每棵树去掉根节点后,其各个子树又组成森林。

若森林为非空,则按如下规则进行遍历:

  1. 访问森林中第一棵树的根结点。
  2. 先序遍历第一棵树中根结点的子树森林。
  3. 先序遍历除去第一棵树之后剩余的树构成的森林。

效果等同于依次对各个树进行先根遍历,等同于对二叉树的先序遍历。

森林的中序遍历

  1. 中序遍历森林中第一棵树的根结点的子树森林。
  2. 访问第一棵树的根结点。
  3. 中序遍历除去第一棵树之后剩余的树构成的森林

效果等同于依次对各个树进行后根遍历,等同于对二叉树的中序遍历。

http://www.lryc.cn/news/324604.html

相关文章:

  • vscode配置c/c++调试环境
  • 食品输送带的材质
  • 普通用户权限运行Docker
  • 7.Java并发编程—掌握线程池的标准创建方式和优雅关闭技巧,提升任务调度效率
  • 从边缘设备丰富你的 Elasticsearch 文档
  • day29|leetcode|C++|491. 非递减子序列|46. 全排列|47. 全排列 II
  • [Java、Android面试]_12_java访问修饰符、抽象类和接口
  • Linux:Prometheus的源码包安装及操作(2)
  • MongoDB聚合运算符:$integral
  • 手撕算法-买卖股票的最佳时机 II(买卖多次)
  • 技术创新与产业升级
  • 透视未来工厂:山海鲸可视化打造数字孪生新篇章
  • 三.寄存器(内存访问)
  • Day31 贪心算法
  • 【WEEK4】 【DAY5】AJAX - Part Two【English Version】
  • 力扣100热题[哈希]:最长连续序列
  • python笔记基础--文件和存储数据(7)
  • Vue黑马笔记(最新)
  • 安全工具介绍 SCNR/Arachni
  • 赋能数据收集:从机票网站提取特价优惠的JavaScript技巧
  • 【大模型】在VS Code(Visual Studio Code)上安装中文汉化版插件
  • 自定义WordPress顶部的菜单的方法
  • 独孤思维:流量暴涨,却惨遭违规
  • 【python 装饰器 - 重试】做一个简易重试装饰器,如果函数执行错误则会自动重新执行,可设置重试次数,对爬虫比较友好
  • Linux线程补充之——同步
  • 面试九 设计模式
  • c++和c语言的区别实例
  • 图论基础|841.钥匙和房间、463. 岛屿的周长
  • 把 Taro 项目作为一个完整分包,Taro项目里分包的样式丢失
  • 腾讯云服务器价格查询系统,2024年1年、3年和5年活动价格表