数据结构与算法 第5天（树和二叉树）
树形结构
一对多 只有一个前驱 可以有多个后继
树的定义
基本术语
有序树：树中结点的各子树从左至右有次序(最左边的为第一个孩子)
森林：是 m(m≥0)棵互不相交的树的集合。 一棵树可以看成特殊的森林
二叉树
每个节点最多有两个分支 所有树可以转化成唯一二叉树
二叉树定义
二叉树不是树的特殊情况 差别是子树是否区分
抽象数据类型定义
二叉树性质
从下往上数，每个孩子都有一条边连着双亲，除了根节点。
如果有n个节点 就会有B=n-1条边
从上往下看，每个度为2的节点会产生两条边，度为1的节点会产生一条边
如果有n个节点，就有 B=n2*2+n1条边
总结点数等于，度为2的节点，加度为1的节点，加度为0的节点
综上叶子树n0=n2+1
简单说就是，一个节点为i，则双亲结点为i/2取整，左子树节点为2i，右子树节点为2i+1
特殊形式的二叉树
满二叉树
注:在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树.
完全二叉树
满二叉树一定是完全二叉树
二叉树顺序存储
按满二叉树的结点层次编号，依次存放二又树中的数据元素。
二叉树链式存储结构
*三叉链表
应用
数据压缩
求解表达式的值
