知心宝贝 2022-01-14 15:43:41 840 收藏 38
版权
图解数据结构
专栏收录该内容
9 篇文章 32 订阅
订阅专栏
目录
一, 前言
二, 树的存储结构
1. 双亲表示法
2. 孩子表示法
3. 孩子兄弟表示法
三, 树转换成二叉树
四, 二叉树转换成树
五, 森林转化成二叉树
六, 树的遍历
七, 附录:
一, 前言
学习目标: 掌握树的三种存储结构, 树和二叉树的相互转换 (不要求算法, 要求画出图形), 先根先序遍历转换 (常考选择题)
重点: 树和二叉树的相互转换
二, 树的存储结构
1. 双亲表示法
实现: 定义结构数组来存放树的结点, 每个结点包含两个域
数据域 (data): 存放结点本身信息
双亲域 (parent): 本结点的双亲在数组中的位置
结构体:
- # define MAX_TREE_SIZE 100
- typedef struct PTNode { // 结点结构
- TElemType data;
- int parent; // 保存双亲位置
- } PTNode;
- typedef struct
- { // 树结构
- PTNode nodes[MAX_TREE_SIZE];
- int r, n; // 根的位置和结点数
- } PTree;
特点:
对于一个结点来说, 使用双亲表示法可以快速的找到它的双亲, 但孩子却很困难
2. 孩子表示法
degree: 当前结点
data: 当前结点存放的数据
child1,2...n: 指向该结点的孩子
childd: 表示结点 degree 有几个孩子, 表示该结点的度
结构体:
- typedef struct CTNode
- {
- int child;// 孩子结点
- struct CTNode *next;
- } *ChildPtr;
- typedef struct
- {
- ElemType data; // 结点的数据元素
- ChildPtr firstchild; // 孩子链表头指针
- } CTBox;
- typedef struct
- {
- CTBox nodes[MAX_TREE_SIZE];
- int n, r; // 结点数和根结点的位置
- } CTree;
特点:
无法寻找双亲结点
3. 孩子兄弟表示法
和孩子表示法差不多, 不过多了一个指向兄弟的指针
结构体:
- #define ElemType char
- typedef struct CSNode{
- ElemType data;
- struct CSNode * firstchild,*nextsibling;
- }CSNode,*CSTree;
特点:
操作容易, 但破坏了树的层次关系
三, 树转换成二叉树
动态图:
讲解:
连接所有兄弟结点
对树中的每一个结点, 只保留与第一个结点的连线, 其它删除
整棵树顺时针旋转 90 度
四, 二叉树转换成树
动态图:
讲解:
将左孩子的右孩子, 右孩子的右孩子...... 全部连接起来
所有双亲结点删除与右孩子的连线
调整角度
五, 森林转化成二叉树
动态图:
讲解:
先将森林中每棵树转换成二叉树
将二叉树根节点视为兄弟连接起来
调整一定的角度
六, 树的遍历
树的先根遍历 == 二叉树的先序遍历
树的中根遍历 == 二叉树的后序遍历
树的后根遍历 == 二叉树的中序遍历
七, 附录:
[图解数据结构] 串全面总结
[图解数据结构] 栈全面总结
[图解数据结构] 队列全面总结
[图解数据结构] 数组和广义表全面总结
[图解数据结构] 排序全面总结 (一)
[图解数据结构] 排序全面总结 (二)
[图解数据结构] 树和二叉树全面总结 (上)
[图解数据结构] 数和二叉树全面总结 (中)
欢迎大家订阅专栏!
来源: https://blog.csdn.net/qq_53673551/article/details/122274500