一。树型结构
结点之间有分支，具有层次关系
1.树的定义
树(Tree)是n (n≥0)个结点的有限集。
若n=0,称为空树;
若n> 0,则它满足如下两个条件:
(1) 有且仅有一个特定的称为根(Root)的结点;
(2)其余结点可分为m (m≥0)个互不相交的有限集T1, T2, T3, ...Tm,其中每一个集合本身又是一棵树，并称为根的子树(SubTree)。
其他表示：
2.树的基本术语
根结点:非空树中无前驱结点的结点
结点的度:结点拥有的子树数。
树的度:树内各结点的度的最大值。
终端结点/叶子:度=0的结点
分支结点/非终端结点/：度≠0的结点
根结点以外的分支结点称为内部结点
结点的祖先:从根到该结点所经分支上的所有结点。
结点的子孙:以某结点为根的子树中的任一-结点
树的深度:树中结点的最大层次。
有序树:树中结点的各子树从左至右有次序(最左边的为第一个孩子)。
森林：是m (m>=0)棵互不相交的树的集合。
把根结点删除树就变成了森林。
一棵树可以看成是一 个特殊的森林。
给森林中的各子树加上一个双亲结点，森林就变成了树。
二。二叉树
为何要重点研究每结点最多只有两个"叉” 的树?
二叉树的结构最简单，规律性最强;
可以证明，所有树都能转为唯一对应的二叉树，不失一般性。
1.二叉树的定义
二叉树是n (n20)个结点的有限集，它或者是空集(n= 0),或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。
【特点】：
1、每个结点最多有俩孩子(二叉树中不存在度大于2的结点)。
2、子树有左右之分，其次序不能颠倒。
3、二叉树可以是空集合, 根可以有空的左子树或空的右子树。
【思考】
2.案例引入
案例1 ： 数据压缩问题 - 有前缀非等长编码
案例2 : 利用二叉树求解表达式的值
若表达式为“第一操作数运算符第二操作数”的形式，则相应的叉树中以左子树表示第操作数,右子树表示第二操作数，根结点的数据域存放运算符(若为一元运算符，则左子树为空) ,其中，操作数本身又为表达式。
如：
三。树和二叉树的抽象数据类型定义
1.二叉树的抽象数据类型定义：
ADT BinaryTree{
数据对象D:
D是具有相同特性的数据元素的集合。
数据关系R:
若D=中，则R=中;
若D≠中，则R= {H}; H是如下二元关系:
①root 唯一//关于根的说明
②D:nDk=中//关于子树不相交的说明
③//关于数据元素的说明
④//关于左子树和右子树的说明
基本操作P:
CreateBiTree(&T,definition)初始条件; definition给出二叉树T的定义。操作结果:按definition构造二叉树T。
PreOrderTraverse(T)初始条件: 二叉树T存在。操作结果:先序遍历T，对每个结点访问一-次。
InOrderTraverse(T)初始条件: 二叉树T存在。操作结果:中序遍历T，对每个结点访问一次。
PostOrderTraverse(T)初始条件:二叉树T存在。操作结果:后序遍历T，对每个结点访问一次。
}ADT BinaryTree
性质1:在二叉树的第i层上 至多有2i-1个结点(i≥1)。
性质2:深度为k的二叉树至多有2k- 1个结点(k≥1)。
性质3:对任何一棵二叉树T,如果其叶子数为no，度为2的结点数为n2，则no= n2+1。
2.满二叉树 - 一棵深度为k且有2k-1个结点的二叉树称为满二叉树。
【特点】:
1.每一层上的结点数都是最大结点数(即每层都满)
2.叶子节点全部在最底层
3.完全二叉树
深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~ n的结点一一对应时， 称之为完全二叉树。
注:在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树一定是连续的去掉! ! !
1.叶子只可能分布在层次最大的两层上。
2.对任一结点，如果其右子树的最大层次为i,则其左子树的最大层次必为i或i+ 1。
性质5：
(1) 如果i= 1,则结点i是二叉树的根，无双亲;如果i> 1,则其双亲是结点Li/ 2]。
(2)如果2i> n,则结点i为叶子结点，无左孩子;否则，其左孩子是结点2i。
(3)如果2i+ 1 > n,则结点i无右孩子;否则，其右孩子是结点2i + 1。（i为双亲结点的编号）
四。二叉树的存储结构
1.二叉树的顺序存储
按满二叉树的结点层次编号，依次存放二叉树中的数据元素。
2.二叉链表存储结构
struct TElemType
{
int a;//树的元素的任意数据类型
};
typedef struct BiNode
{
struct TElemType data;
struct BiNode * lchild;
struct BiNode * rchild;
}BiNode,*BiTree; 三叉链表，还有一个指针域指向双亲
typedef struct TriTNode{
TelemType data;
struct TriTNode *Ichild, *parent, *rchild;
}TriTNode,*TriTree;