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