树形结构思维导图

U621655065

2022-12-25

浏览量: 16

存储结构

二叉树

哈夫曼树和哈夫曼编码

树图思维导图提供《树形结构》在线思维导图免费制作，点击“编辑”按钮，可对《树形结构》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：84c0db7d40af85c151316c5d74c1c968

思维导图大纲

树的存储结构

顺序存储结构

双亲表示法

typedef struct PTNode{ TElemType data; int parent; }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int r,n; //根的位置和结点数 }PTree;

定义逻辑：用一组连续的存储空间存储树的结点，同时在每个结点中，用一个变量存储该结点双亲结点的位置

链式存储结构

孩子表示法

typedef struct CTNode{ //孩子结点 int child; struct CTNode *next; }*ChildPtr; typedef struct{ //表头结点 TElemType data; ChildPtr firstchild; //孩子链表头结点 }CTBox; typedef struct{ CTBox nodes[MAX_TREE_SIZE]; int n,r; //结点数和根的位置 }CTree;

孩子链表：把每个节点的孩子排列在一条单链表中，所有n个表头指针组成一个线性表

孩子兄弟表示法

typedef struct CSNode{ ElemType data; struct CSNode *firstchild,*nextsibling; //指向第一个孩子结点和下一个兄弟结点 }CSNode,*CSTree;

孩子兄弟：两个链表域、一个链接孩子结点，一个链接下一个兄弟结点

树的基本概念

定义

树是n个结点的有限集

特点

有且仅有一个特定称为根（root）的结点

除根以外的结点只有一个前驱

除根节点以外的其余结点可分为m个不相交的有限集，每一个集合本身又是一棵树（子树）

二叉树

定义

有且仅有一个称之为根的结点；除了根结点以外的其余结点分为两个互不干扰的子集T1和T2。分别称为左子树和右子树。

结点度小于等于2；有序树（子树有序，不可以颠倒）

二叉树的五种形态

完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边

性质

在二叉树的第i层上至多有2^(i-1)个结点

深度为k的二叉树至多有2^k-1个结点

对于任何一棵二叉树，若度为2的结点有n2个，则叶子数n0=n2+1

具有n个结点的完全二叉树的深度必为[log2 n]+1

对于完全二叉树，若从上到下，从左到右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号为2i+1；双亲编号为i/2

存储结构

顺序存储

用一个数组来存储一颗二叉树，一般适用于完全二叉树：用一组连续的存储单元自上而下、自左而右存储各个结点的元素。

链式存储

二叉链表或三叉链表实现

typedef struct BiTNode{ TelemType data; struct NoTNode *lchild,*rchild; }BiTNode,*BiTree;

性质：如果含有n个结点的二叉链表中，右n+1个空指针域

基本操作

递归算法

递归的思路：每一个子树都是一个以叶子为根结点的二叉树

先序遍历：根左右

中序遍历：左根右

后序遍历：左右根

求二叉树深度

求二叉树结点个数

度为1的结点个数

从每个叶子结点到根结点的路径

交换二叉树每个结点的左孩子和右孩子

非递归算法

中序遍历

先序遍历

后序遍历

一个栈实现

两个栈实现

设计思路：通过创建一个新的栈，来实现逆序的输出

层序遍历

线索二叉树

概念

用空指针来存放当前结点的直接前驱和后继等线索，加快查找速度

线索：指向前驱或后继点的指针

线索二叉树：加上线索的二叉树

线索化：对二叉树按某种遍历的次序使其变为线索二叉树

查找前驱、后继结点

结构体定义

typedef enum {Link,Thread} PointerTag; //定义线索 typedef struct BithrNode{ char data; //结点数据 struct BithrNode *pLchild; struct BithrNode *pRchild; //左右孩子 PointerTag Ltag; PointerTag Rtag; //左右标志 }BiThrNode,*BiThrTree;

中序遍历线索化过程

递归算法

非递归算法