树的定义：一棵树是由n（n>0）个元素组成的有限集合。
（1）每个元素称之为结点（node）。
（2）有一个特定的结点，称为根结点或树根（root）。
（3）除根结点外，其余结点能分成m（m>=0）个互不相交的有限集合，
………
。其中的每个子集又都是一棵树，这些集合称为这棵树的子树。
树的基本概念：
（1）树是递归定义的。
（2）一棵树中至少有一个结点。这个结点就是根结点，它没有前驱，其余每个结点都有唯一的一个前驱结点。每个结点可以有0或多个后继结点。因此树虽然是非线性结构，但也是有序结构，至于前驱后继结点是哪个，还要看树的遍历方法。
（3）一个结点的子树个数，称为这个结点的度（degree）；度为0的结点称为叶结点（树叶leaf）；度不为0的结点称为分支结点；根以外的分支结点又称为内部结点；树中各结点的度的最大值称为这棵树的度。
（4）在用图形表示的树形结构中，对两个用线段（树枝）连接的相关联的结点，称上端结点为下端结点的父结点，称下端结点为上端结点的子结点。称同一个父结点的多个子结点为兄弟结点。称从根结点到某个子结点所经过的所有结点为这个子结点的祖先。称从某个结点为根的子树中的任一结点都是该结点的子孙。
（5）定义一棵树的根结点的层次（level）为0，其他结点的层次等于它的父结点层次加一。一棵树中所有的结点的层次的最大值称为树的深度。
（6）对于树中任意两个不同的结点，如果从一个结点出发，自上而下沿着树中连着结点的线段能到达另一结点，称他们之间存在一条路径。可用路径所经过的所有结点序列表示路径，路径的长度等于路径上的结点个数减一。注意，不同子树上的结点之间不存在路径，从根结点出发，到树中其他结点一定存在着一条路径。
（7）森林（forest）是m（m>=0）棵互不相交的树的集合。
树的存储结构：
方法一:数组，称为“父亲表示法”。
const int m=10;//树的结点数
struct node{
int data,parent;//数据域，指针域
}tree[m];
优缺点：利用了树中除根结点之外每个结点都有唯一的父结点这个性质，很容易找到树根，但找孩子时需要遍历整个线性表。
方法二：树形单链表结构，称为孩子表示法，每个结点包括一个数据域和一个指针域（指向若干子结点）。假设树的度为10，树的结点仅存放字符，则这棵树的数据结构定义如下：
const int m=10;
struct node;
node *tree;
struct node{
char data;
tree child[m];
};
tree t;
缺点：只能从父结点遍历到子结点，不能从子结点返回到它的父结点（可以多定义一个指针存储父结点）
方法三：树形双链表结构，称为父亲孩子表示法，每个结点包括一个数据域和两个指针域（一个指向若干子结点，一个指向父结点）：
const int m=10;
struct node;
node *tree;
struct node{
char data;
tree child[m];
tree father;
};
tree t;
方法四：二叉树型表示法，称为孩子兄弟表示法，是双链表结构，每个结点包括一个数据域，两个指针域（一个指向该结点的第一个孩子结点，一个指向该结点的下一个兄弟结点）：
struct node;
node *tree;
struct node{
char data;
tree firstchild,next;
};
tree t;
树的遍历：
1.先序遍历，根左右
2.后序遍历，左右根
3.层次遍历，广搜
4.叶结点遍历，leaf
二叉树：
五种基本形态
性质：
1.在二叉树的第i层最多有二的i-1次方个结点（i>=1）
2.深度为k的二叉树至多有个结点（k>=1）
3.对任意一棵二叉树，如果其叶结点数为，度为2的结点数为
，则一定满足：
+
+1。
4.具有n个结点的完全二叉树的深度为floor（）+1。
5.对于一棵n个结点的完全二叉树，对任一个结点（编号为i）有：
（1）如果i=1，则结点i为根，无父结点；如果i>1，则其父结点编号为i/2。
如果2*i>n，则结点i无左孩子（当然也无右孩子，因为结点i为叶结点）；否则左孩子编号为2*i。
（2）如果2*i+1>n,则结点i无右孩子；否则右孩子编号为2*i+1。
