大话数据结构 【七】树2
二叉树
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
特点
- 每个结点最多有两棵子树
- 左子树和右子树是有顺序的，不能颠倒
- 即使树中某结点只有一棵子树，也要区分左还是右
五种基本形态
特殊二叉树
——斜树
——满二叉树
特点：
——完全二叉树
判断：
理解：
- 满二叉树一定是完全二叉树，完全二叉树不一定满
- 完全二叉树所有结点与同样深度的满二叉树，它们按层次编号相同的结点，是一一对应
完全二叉树的特点：
二叉树的性质
二叉树的顺序存储结构
1.顺序存储结构
完全二叉树的顺序存储：
一般的二叉树：
【尽管层序编号不能反应其逻辑关系，但可以按完全二叉树编号，把不存在的结点设置为“^”】
但是，如果是深度为k的右斜树，只有k个结点，却需要分配2k-1个存储单元空间——> 浪费空间
即，顺序存储结构一般只用于完全二叉树
2.二叉链表
data是数据域
lchild 存放指向左孩子的指针
rchild 存放指向右孩子的指针
结点结构定义：
如果有需要，还可以再增加一个指向其双亲的指针域——> 称为“三叉链表”
更多精彩
