树可以用几种方式定义，其中一种自然的方法是递归方法
一棵树是一些节点的集合，有些节点具有特殊的叫法（如“根”），这个集合可以是空集，若非空，则一棵树则是根与数个或零个的非空的子树的集合
树是由一条条有向的边所连接
1.2.1树的基础相关概念
根（root）：树的开始节点
如果树拥有子树，则子树同样拥有自己的根，如上图二叉树中始根有两个子树，两个子树拥有对应自己的根
儿子（child) : 每一棵子树的根叫做根（root）的儿子（真是令人眼前一黑的神级翻译）
父亲（parent）：根（root）是每一棵对应此根的子树的根的父亲
树叶（leaf）:没有儿子的节点叫做树叶
兄弟（sibling）:具有相同父亲的节点叫做兄弟
同样的可以明确祖父（grandparent）与孙子（grandchild）的关系
1.2.2树的一般结构
一棵树由N个节点与N-1条边组成，一般的，其中位于头部的节点是树的根，每条边都将他的节点连接到他的父亲，去除树的根外，每一个节点都有他的父亲，去除树叶，每一个节点都有他的儿子
1.2.3树的结构关系概念
路径（path）:从节点n1到nk的一个序列，此序列使得对于从n1到nk的的每一个节点都顺序是下一节点的父亲，
路径的长（length）：该路径上的边的条数
深度（depth):对于任意节点，从根到节点的的唯一路径的长,根的深度为0
高度（height）:对于任意节点，从节点到一片树叶的最长路径的长，所有树叶的高度都为0
关系补充：
如果存在从n1到n2的一条路径，则n1是n2的一位祖先（ancestor）,而n2是n1的一位后裔（descendant）
对于n1!=n2的情况，那么n1是n2的一位真祖先（ancestor）,而n2是n1的一位真后裔（descendant）， （类比于集合的基础知识）
2树的实现 2.1如何实现一个树？使用c语言为例，很自然的可以想到利用结构体来创建一个“树”数据结构
但是问题是我们事先不知道各个节点的儿子数，它可以变化很大，因此我们无法直接区建立根与子树的联系，否则对于空间是一种浪费
于是可以这样解决：将每个节点的所有儿子放在树节点的链表中，如下例
typedof struct TreeNode *PtrToNode
struct TreeNode
{
ElementType Element;
PtrToNode FirstChild;
PtrToNode NextSibling
}以下面的树为例（画的比较抽象，抱歉）
利用上述方法，可得
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧