树与二叉树
2021-08-27 12:35:05 1 举报AI智能生成
数据结构树于二叉树知识纲要
作者其他创作
大纲/内容
树的定义
性质
树的基本概念
完全二叉树
满二叉树
顺序存储结构
链式存储结构
存储结构
n个结点的二叉链表，共有n+1个空链域
二叉树共有5种形态
非空二叉树的 叶子结点数=度为2的结点数+1
非空二叉树第K层最多2^(k-1)个结点
高度为h的二叉树共有2^h-1个结点
二叉树的概念
根左右
先序遍历
左根右
中序遍历
左右根
后序遍历
层次遍历
前+中
后+中
层+中
由遍历序列构造二叉树
二叉树的遍历（遍历算法和程序实现）
指向结点前驱和后继的指针称为线索
为了加快查找结点的前驱和后继
概念
不能有效解决先序前驱的问题
先序线索二叉树
中序线索二叉树
不能有效解决后序后继的问题
后序线索二叉树
线索二叉树（物理结构）
二叉树的遍历和线索二叉树
需要一组连续的地址空间来存储每个节点，同时在每个结点添加一个伪指针，用来标明双亲结点在数组中的位置
双亲表示法
顺序存储
左孩子右兄弟
孩子兄弟表示法
将每个结点用单链表链接起来形成一个线性结构
孩子表示法
链式存储
树的存储结构
P163见图5.17
树、二叉树和森林的转换
树和森林的遍历
树、森林
若BST是一个只有左（右）孩子的单支树，则其平均查找长度O(n)
二叉排序树（BST）
在A的左孩子的左子树插入导致不平衡
LL平衡旋转(右单旋转)
RR平衡旋转
LR平衡旋转(先左后右双旋转)
RL平衡旋转(先右后左双旋转)
插入
平衡二叉树
在含有n个带权叶结点的二叉树中，WPL最小的二叉树称为哈夫曼树
构造
没有一个编码是其他编码的前缀
前缀编码
哈夫曼树不唯一，因此哈夫曼编码不唯一
哈夫曼编码
哈夫曼树和哈夫曼编码
树与二叉树的应用
树与二叉树
0 条评论
回复 删除
下一页
