树的概念和结构树的概念树是一种非线性的数据结构，是由n(n=0)个有限节点组成的具有层次关系的集合。把它叫做“树”，是因为它看起来像一颗倒挂的树，也就是说它是根朝上，而叶朝下的。
树的特点：
有一个称为根节点的特殊节点，根节点没有前驱节点。
除了根节点之外，剩下的节点分为m(m0 )互不相交的集合T1、T2…Tm，其中的各集合ti(1=I=m )又是与树相似结构的子树。
每个子树的根节点只有一个前驱体，并且可以有0个以上的继承人。
因此，树是递归定义的。
树中的固有名词3358www.Sina.com/:1:一个节点包含的子树的数量称为该节点的度。
结点的度:角度为0的节点称为axdxx。
axdxx（终端结点）:度不为0的节点。
非终端结点（分支结点）:如果某个节点包含子节点，则将该节点称为该子节点的父节点。
父结点（双亲结点）:将某个节点包含的子树的根节点称为该节点的子节点。
子结点（孩子结点）:具有相同父节点的节点相互称为兄弟节点。
兄弟结点:在一棵树中，最大的节点度称为树度。
从树的度根定义，根是第一层，根的子节点是第二层。
结点的层次:树中节点的最大级别。
树的高度（树的深度）:父母在同一层的节点互相称为表兄弟节点。
堂兄弟结点:从根到该节点的经支上的所有节点。
结点的祖先:把以某个节点为根的子树的任何一个节点称为该节点的子孙。
33558www.Sina.com/:m(m )条由互不相交的树构成的集合称为森林。
树的表示树结构相对于线性表来说比较复杂，保存和表示比较麻烦，实际上树有多种表示方法。 例如，父母表示法、孩子表示法、xhdxmf表示法等。 其中最常用的是子孙
在xhdxmf表示法中，定义的节点类型大致如下：
typedefintdatatypestructnode { struct node * first child； //第一子节点struct Node* nextBrother； //指向下一个同级节点DataType data； //节点中的数据域； 在任何树中，都可以使用xhdxmf方法访问树中的所有节点。
实际的树的运用(表示文件系统的目录树结构) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )。
二叉树的概念及其重要性质二叉树的概念二叉树是n个节点的有限集合，该集合为空，或者由一个根节点加上两个树的二叉树构成。 当集合为空时，将此二叉树称为空二叉树。
二叉树的特征：
各节点最多有2棵子树，是二叉树的不存在度大于2的节点。
二叉树有左右之分，不能颠倒子树的顺序。
自然界的二叉树
数据结构中的二叉树
的二叉树森林:一个二叉树，当每层节点数达到最大值时，该二叉树将填满二叉树。 也就是说，如果一个二叉树的层数为k，节点的总数为2k-1，则其充满二叉树。
xhdxmf表示法:完全二叉树是一种高效的数据结构，完全二叉树由二叉树组成。 关于深度为k，具有n个节点的二叉树，只有在各个节点与深度为k的满二叉树中编号从1到n的节点一一对应的情况下，才称为完全二叉树。 需要注意的是，二叉树是一种特殊的完全二叉树。
总结：
满二叉树:假设树的深度为k，则每层的节点数必须全部填满。
完全二叉树:假设数的深度为k，则其前K-1层的节点数必须全部满，第k层的节点数可以不满，但必须从左到右连续。
二叉树的性质(重要！ )满二叉树)如果根节点的层数为1，则在一棵非空二叉树的第I层最多有2i-1个节点。
设完全二叉树根节点的层数为1，则深度为h的二叉树的最大节点数为2h-1个。
性质一:对于任何二叉树，如果将角度0的axdxx的个数设为n0，将角度2的分支节点的个数设为n2，则n0=n2 1。
性质二:设根节点的层数为1，则具有n个节点的二叉树的深度h=log2(n1 )。
33558www.Sina.com/:n:对于具有n个节点的完全二叉树，从
上至下、从左至右的数组顺序对所有结点从0开始编号，则对于序号为i的结点：若 i > 0，则该结点的父结点序号为：( i - 1) / 2；若 i = 0，则无父结点。
若2i + 1 < N，则该结点的左孩子序号为：2i + 1；若2i + 1 >= N，则无左孩子。
若2i + 2 < N，则该结点的右孩子序号为：2i + 2；若2i + 2 >= N，则无右孩子。
练习一下：
1.某二叉树共有399个结点，其中199个度为2的结点，则该二叉树中的叶子结点数为（ ）。
A.不存在这样的二叉树
B.200
C.198
D.199
2.在具有2n个结点的完全二叉树中叶子结点个数为（ ）。
A.n
B.n+1
C.n-1
D.n/2
3.一棵完全二叉树的结点数为531，那么这棵树的高度为（ ）。
A.11
B.10
C.8
D.12
4.一个具有767个结点的完全二叉树，其叶子结点个数为（ ）。
A.383
B.384
C.385
D.386
解析：
1.（答案：B）根据性质三，叶子结点（度为0）的个数200个，由于199+200 = 399（该二叉树的总结点数），所以该二叉树的叶子结点数为200。
2.（答案：A）根据性质三，度为0的结点数和度为2的结点数之和应为奇数，因为该完全二叉树的结点总数为2n（偶数），所以二叉树中必然存在一个度为1的结点。于是可以推出：度为0的结点和度为2的结点总共有2n-1个。性质三：对任何一棵二叉树，度为0的axdxx个数比度为2的分支结点个数多1，所以该二叉树度为1的结点个数为n-1，度为0的结点数（即axdxx数）为n。
注意理解：任何一棵完全二叉树中度为1的结点要么有1个，要么就没有度为1的结点。因为完全二叉树的最后一层的结点必须是从左到右连续的，而位于最后一层之前的层数的结点的度均为2。
3.（答案：B）假设该完全二叉树的层数为K，则该完全二叉树的前K-1层的结点总数为2K-1-1，若该完全二叉树是满二叉树，则该满二叉树的结点总数为2K-1，所以深度为K的完全二叉树的结点总数范围为：2K-1-1 < N <= 2K-1。因为29 < 531 <= 210，所以该完全二叉树的高度为10。
注意记忆：210 = 1024。
4.（答案：B）该题与第2题的道理是一样的，因为该树的结点总数为767（奇数），所以该树中不存在度为1的结点，度为2的结点个数为383，度为0的结点个数为384，即叶子结点个数为384。
二叉树的存储结构 顺序结构 顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实生活中只有堆（一种二叉树）才会使用数组来存储。二叉树的顺序存储在物理上是一个数组，在逻辑上是一棵二叉树。
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素之间的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来存储该结点左孩子和右孩子所在的结点的地址。
链式结构又分为二叉链和三叉链，之后我们会用二叉链来实现二叉树的链式存储结构，三叉链运用于更高阶的数据结构，例如红黑树。