导图社区 树与二叉树
数据结构第六章树与二叉树（考研自学）
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
马克思主义原理
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
树与二叉树
树
定义
一个前驱多个后继递归
术语
祖先、子孙
度
结点
分支节点
叶子节点
深度、高度、层次
树的高度
有序无序
路径和路径长度
森林
二叉树
有序、左右结点
特殊二叉树
满二叉树
完全二叉树
二叉排序树
平衡二叉树
性质
叶子结点数等于度为2结点的总数加一
k层最多有2^(k-1)个节点
h为深度的树最多有2^h-1个结点
存储结构
顺序
不存在的结点补0
建议从根结点为1开始写
链式
n个结点有n+1个空链域
二叉树线索遍历
递归算法
先序遍历
中序遍历
后序遍历
非递归（栈）
前序和中序只有访问次序不一致
后序遍历可以衍生出求路径
层次遍历（层次）
确定二叉树
中序和前序
中序和后序
层次和中序
线索二叉树
概念
ltag/rtag
0左孩子/右孩子
1前驱/后继
构造
左递归
判断左再判断右
pre跟上p
右递归
遍历
rtag==1为后继
rtag==0
后继为r->rchild的最左下结点
树、森林
双亲表示法
孩子表示法
孩子兄弟表示法
转换
连兄弟
只保留左孩子
旋转45度
树的遍历
先根遍历
后根遍历
森林的遍历
*应用：并查集
树和二叉树的应用
二叉排序树（BST）
左<根<右
插入
查找
哈夫曼树及编码
带权路径长度（WPL）最小
哈夫曼编码
