提升编程基础能力
数据结构、操作系统、计租、网络
陆续会慢慢更新！
资料获取
六、树 6.1 树的定义
**树(Tree)是n (n≥0)个结点的有限集 。n=0时称为空树 。**在任意一棵非空，树中:
? (1) 有且仅有一个特定的称为根(Root) 的结点;
? (2) 当n>1时，其余结点可分为m (m>0)个互不相交的有限集T1、 T2、… Tn, 其中每一个集合本身又是一棵树，并且称为根的子树() 。
树的定义其实就是我们在讲解栈时提到的递归的方法 。也就是在树的定义之中还用到了栈的概念，这是一种比较新的定义方法 。下图中的子树T1和子树T2就是根结点A的子树 。当然，D、G、H、I组成的树又是B为结点的子树，E、J组成的树是C为结点的子树 。
对于树的定义还需要强调两点:
n>0时根结点是唯一的，不可能存在多个根结点，别和现实中的大树混在一起，现实中的树有很多根须，那是真实的树，数据结构中的树是只能有一个根结点 。m>0时，子树的个数没有限制，但它们一定是 互不相交的 。像下面的两个结构就不符合树的定义，因为它们都有相交的子树 。
下面这张图就是不符合要求的树定义
6.1.1基本术语
根节点：非空树中无前驱结点的结点
结点的度：结点拥有的子树数
树的度：树内各节点的度的最大值
叶子：度为0，没有分支了，也叫终端结点
分支结点：度不为0的点，根结点以外的分支结点称为内部结点
除了根结点以外，其他的结点都称为内部结点
6.1.2结点间的关系
结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲() 。
为啥叫双亲呢？因为就一个结点，对结点来说其父母同体所以只能把它称为双亲
同一个双亲的孩子之间互称兄弟() 。结点的祖先是从根到该结点所经分支上的所有结点 。所以对于H来说，D、B、A都是它的祖先 。反之，以某结点为根的子树中的任一结点都称为该结点的子孙 。B的子孙有D、G、H、I
6.1.3树的其他相关概念
? 结点的层次(Level) 从根开始定义起，根为第一层,根的孩子为第二层 。若某结点在第1层，则其子树的根就在第l+1层 。**其双亲在同一层的结点互为堂兄弟 。**图中D、E、F是堂兄弟，而G、H、I、J也是 。
树中结点的最大层次称为树的深度(Depth) 或高度，当前树的深度为4 。
? 如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树 。
? 森林() 是m (m≥0)棵互不相交的树的集合
? 把根节点删除，树就变成了森林
? 两棵子树其实就可以理解为森林 。
? 给森林中的各子树加上一个双亲结点，森林就变成了树
? 对比线性表与树的结构，它们有很大的不同
线性结构
第一个数据元素:无前驱
中间元素：一个前驱一 个后继
最后一个数据元素:无后继
树结构
根结点:无双亲，唯一
叶结点:无孩子，可以多个
中间结点:一个双亲多个孩子
6.2树的抽象数据类型
ADT树(tree)Data树是由一个根结点和若干棵子树构成 。树中结点具有相同数据类型及层次关系 。OperationInitTree (*T) :构造空树T 。DestroyTree(*T) :销毁树T 。CreateTree ( *T, definition) :按definition中給出树的定义来构造树 。ClearTree (*T) :若树T存在，则将树T清为空树 。TreeEmpty (T) :若T为空树，返回true,否则返回false 。TreeDepth(T):返回T的深度 。Root (T) :返回T的根结点 。Value (T,cur e) : cur_ e是树T中一个结点，返回此结点的值 。Assign (T, cur_ e,value) :给树T的结点cur_ e赋值为value 。Parent (T,cur e):若cur_ e是树T的非根结点，则返回它的双亲，否则返回空 。LeftChild (T,cur_ e) :若cur_ e是树T的非叶结点，则返回它的最左孩子，否则返回空 。RightSibling (T,cur _e) :若cur_ e有右兄弟，则返回它的右兄弟，否则返回空 。InsertChild(*T, *p,i,c) :其中p指向树T的某个结点，i为所指结点p的度加上1,非空树c与T不相交，操作结果为插入C为树T中p指结点的第i棵子树 。DeleteChild (*T,*p,i) :其中p指向树T的某个结点，i为所指结点p的度，操作结果为删除T中P所指结点的第i棵子树 。endADT