树和二叉树

一、树的基本概念

树是由一个集合以及在该集合上定义的一种关系构成的。集合中的关系称的结点，所定义的关系为父子关系最上层为根节点树是n（n>=o)个结点的有限集

a.一颗空树，b.有一个根节点的树，c.有许多子结点

结点的度：结点拥有子结点的数目
树的度：树内各节点最大的度数

树的深度：树中结点的最大层树

有序树：各节点从左到右有次序

二、二叉树

每个结点的度都不超过二的有序树，称为二叉树

满二叉树：高度为并且有个2＾（k+1）-1结点的二叉树，每层的结点都达到最大数

完全二叉树：在一棵满二叉树中，在最下层最右侧起去点相邻的叶子结点得到的二叉树

满二叉树必为完全二叉树，反之不一定
二叉树的性质：
1.在二叉树的第i层上最多有2^(i-1) 个结点（根是第一层）
2.高度为h的二叉树最多有2^h -1个节点
3.对于任何一个二叉树，如果其终端节点数为n,度为2 的结点数为m，则n=m+1
4.如果一颗二叉树有n个结点的完全二叉树进行编号，则对任一结点（1<=i<=n)
5.若i=1,则i是二叉树的根、、
6.如果2i>n,则结点i无左孩子，否则其左孩子为2i
7.如果2i+1>n，则结点i无右孩子，否则其右孩子为2i+1

三、叉树的存储结构

１．顺序存储结构
对于满二叉树和完全二叉树来说，可以将其数据元素筑层放到一组连续的存储单元

如果不是满二叉树，则比较浪费空间

2.链式存储结构
若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用链表存储即可。因此，图 1 对应的链式存储结构如图 2 所示：

二叉树链式存储结构示意图

二叉树遍历

遍历：按着某种次序访问树中所以二叉树，且每个节点恰好访问一次。人为的将非线性化线性化。
先序遍历ＤＬＲ：根　左　右
中序遍历ＬＤR:左子树　根　右子树
后序遍历ＬRＤ:左　右　根