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