软件设计师 http://www.educity.cn/jiaocheng/zg7.html
图1-3 树的例子
在用图形表示的树中，对两个用线段连接的相关联的结点而言，称位于上端的结点是位于下端的结点的父结点或双亲结点，称位于下端的结点是位于上端的结点的（孩）子结点，称同一父结点的多个子结点为兄弟结点，称处于同一层次上、不同父结点的子结点为堂兄弟结点。例如在图1-3中，结点1是结点2,3,4的父结点。反之，结点2,3,4都是结点1的子结点。结点2,3,4是兄弟结点，而结点5,6,7,8,9是堂兄弟结点。
定义一棵树的根结点所在的层次为1,其他结点所在的层次等于它的父结点所在的层次加1.树中各结点的层次的最大值称为树的层次。 2.树的常用存储结构
因为树是非线性的结构，为了存储树，必须要把树中结点之间的关系反映在存储结构中。最常用树的存储结构有标准存储和带逆存储形式。 1）标准存储结构
在树的标准存储结构中，树中的结点内容可分成两部分，分别为结点的数据和指向子结点的指针数组。对于N度树，在其标准存储结构中指针数组有N个元素。
例如设树的次数为5,树的结点数据仅限于字符，用C语言描述树结点的标准存储结构的数据类型如下： #define N 5
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
typedef struct tnode{
char data; /*树结点的数据信息*/
struct tnode *child[N]; /*树结点的子结点指针*/ }TNODE; /*树结点的数据类型*/ 2）带逆存储结构
带逆存储结构在标准存储结构的基础上增加一个指向其父结点的指针，用C语言描述树结点的带逆存储结构的数据类型如下： #define N 5
typedef struct rtnode{
char data; /*树的结点数据信息*/
struct rtnode *child[N]; /*树结点的子结点指针*/ struct rtnode *parent; /*父结点指针*/ }RTNODE; /*树结点的数据类型*/ 3.树的遍历
按照某种顺序逐个获得树中全部结点的信息，称为树的遍历。常用的树的遍历方法主要有以下3种。
前序遍历：首先访问根结点，然后从左到右按前序遍历根结点的各棵子树。 后序遍历：首先从左到右按后序遍历根结点的各棵子树，然后访问根结点。
层次遍历：首先访问处于0层上的根结点，然后从左到右依次访问处于1层上的结点，然后从左到右依次访问处于2层上的结点等，即自上而下、从左到右逐层访问树中各层上的结点。
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
按上述遍历的定义，图1-3所示的树的各种遍历结果如下。 前序遍历：1,2,5,6,7,8,3,4,9,a,b. 后序遍历：5,6,7,8,2,3,a,b,9,4,1. 层次遍历：1,2,3,4,5,6,7,8,9,a,b.
1.2.2 二叉树 1.二叉树的基本概念
二叉树是一个有限的结点集合，该集合或者为空，或者由一个根结点及其两棵互不相交的左、右二叉子树所组成。二叉树的结点中有两棵子二叉树，分别称为左子树和右子树。因为二叉树可以为空，所以二叉树中的结点可能没有子结点，也可能只有一个左子结点（右子结点），也可能同时有左右两个子结点。如图1-4所示是二叉树的4种可能形态（如果把空树计算在内，则共有5种形态）。
图1-4 二叉树的4种不同形态
与树相比，二叉树可以为空，空的二叉树没有结点（树至少有一个结点）。在二叉树中，结点的子树是有序的，分左、右两棵子二叉树。
二叉树常采用类似树的标准存储结构来存储，其结点类型可以用C语言定义如下： typedef struct Btnode{ char data; /*数据*/
strucrt Btnode *lchild; /*左孩子*/ struct Btnode *rchild; /*右孩子*/
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
}BTNODE; 2.二叉树的性质
二叉树具有下列重要性质（此处省略了推导过程，有兴趣的读者可自行推导）。 性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。 性质2：深度为k的二叉树至多有2k–1个结点（k≥1）。
性质3：对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。
一棵深度为k且有2k-1（k≥1）个结点的二叉树称为满二叉树。如图1-5所示就是一棵满二叉树，对结点进行了顺序编号。
图1-5 满二叉树的例子
如果深度为k、有n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树。如图1-6（a）所示是一棵完全二叉树，而（b）、（c）是两棵非完全二叉树。显然，满二叉树是完全二叉树的特例。
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
图1-6 完全二叉树和非完全二叉树
根据完全二叉树的定义，显然，在一棵完全二叉树中，所有的叶子结点都出现在第k层或k–1层（最后两层）。
性质4：具有n（n>0）个结点的完全二叉树的深度为∟log2n」+1。（注：号为向下取整运算符，
为向上取整运算符，
符
表示不大于m的最大整数，反之，
表示不小于m的最小整数）
性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第∟log2n」+1层，每层从左到右），则对任一结点i（1≤i≤n），有： 如果i=1，则结点i无双亲，是二叉树的根；如果i>1,则其双亲是结点 如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。 如果2i+1>n，则结点i无右孩子；否则，其右孩子是结点2i+1。 3.二叉树的遍历
树的所有遍历方法也同样适用于二叉树，此外，由于二叉树自身的特点，还有中序遍历方法。
前序遍历（先根遍历，先序遍历）：首先访问根结点，然后按前序遍历根结点的左子树，再按前序遍历根结点的右子树。
中序遍历（中根遍历）：首先按中序遍历根结点的左子树，然后访问根结点，再按中序遍历根结点的右子树。
后序遍历（后根遍历，后序遍历）：首先按后序遍历根结点的左子树，然后按后序遍历根结点的右子树，再访问根结点。
。