1.1树的概念
树的概念
树（Tree）是n（n≥0）个节点的有限集合T，它满足两个条件 ：
1)有且仅有一个特定的称为根（Root）的节点；
2)其余的节点可以分为m（m≥0）个互不相交的有限集合T1、T2、 …… 、Tm，其中每一个集合又是一棵树，并称为其根的子树（Subtree）。
表示方法 ： 树形表示法 、 目录表示法 。
基本概念 ：
1)一个节点的子树的个数称为该节点的 度数 ，一棵树的度数是指该树中节点的最大度数。
2)度数为零的节点称为 树叶 或 终端节点 ，度数不为零的节点称为分支节点，除根节点外的分支节点称为内部节点。
3)一个节点的子树之根节点称为该节点的 子节点 ，该节点称为它们的 父节点 ，同一节点的各个子节点之间称为兄弟节点。
4)一棵树的根节点没有父节点，叶节点没有子节点。
5)一个节点系列k 1 ,k 2 , …… ,k i ,k i+1 , …… ,k j ,并满足k i 是k i+1 的父节点，就称为一条从k 1 到k j 的 路径 ，路径的长度为 j-1,即路径中的边数 。路径中前面的节点是后面节点的祖先，后面节点是前面节点的子孙。
6)节点的层数等于父节点的层数加一，根节点的层数定义为一。树中节点层数的最大值称为该树的 高度 或 深度 。
7)若树中每个节点的各个子树的排列为从左到右，不能交换，即兄弟之间是有序的，则该树称为 有序树 。一般的树是 有序树。
8)m（m≥0）棵互不相交的树的集合称为 森林 。树去掉根节点就成为森林，森林加上一个新的根节点就成为树。
图理解
树的逻辑结构 ：
树中任何节点都可以有零个或多个直接后继节点（子节点），但至多只有一个直接前趋节点（父节
点）， 根节点没有前趋节点 ， 叶节点没有后继节点 。
1.2二叉树
二叉树的定义 ：
二叉树（Binary Tree）是n（n≥0）个节点的有限集合，它或者是空集（n＝0），或者是由一 个根
节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树与普通有序树不同，二
叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。
二叉树的性质 ：
1）二叉树第i（i≥1）层上的节点最多为 2 i-1 个。
2）深度为k（k≥1）的二叉树最多有 2 k －1 个节点。
3）在任意一棵二叉树中，树叶的数目比度数为2的节点的数目多一。
总节点数为各类节点之和：n = n0 + n 1 + n 2
总节点数为所有子节点数加一：n = n1 + 2*n 2 + 1
故得：n0 = n 2 + 1 ;
4）满二叉树 ：深度为k（k≥1）时有2 k －1个节点的二叉树。
5）完全二叉树 ：只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若
干位置上。
6）具有n个节点的完全二叉树的深度为
（log2n）＋1或『log2(n+1)。
二叉树的存储 ：
顺序存储结构 ：
完全二叉树节点的编号方法是从上到下，从左到右，根节点为1号节点。设完全二叉树的节点数为
n，某节点编号为i
1）当i＞1（不是根节点）时，有父节点，其编号为i/2;
2）当2*i≤n时，有左孩子，其编号为2*i ,否则没有左孩子，本身是叶节点;
3）当2*i＋1≤n时，有右孩子，其编号为2*i+1 ,否则没有右孩子；
4）当i为奇数且不为1时，有左兄弟，其编号为i-1,否则没有左兄弟；
5）当i为偶数且小于n时，有右兄弟，其编号为i＋1,否则没有右兄弟；
且有n个节点的完全二叉树可以用有n+1个元素的数组进行顺序存储，节点号和数组下标
一一对应，下标为零的元素不用。
利用以上特性，可以从下标获得节点的逻辑关系。不完全二叉树通过添加虚节点构成
完全二叉树，然后用数组存储，这要浪费一些存储空间。
虚节点：就是利用一些特殊符号代替当前节点下不存在的节点（因为在顺序存储的条件下要先将非完全二叉树补成完全二叉树才能进行顺序存储和输出）
链式存储结构 ：
typedef int data_t ;//定义数据类型
typedef struct node_t;//定义二叉树节点的内部结构
{
data_t data ;//数据域
struct node_t *lchild ,*rchild ;//指向左孩子和右孩子的指针
} bitree_t ;//二叉树节点类型
bitree_t *root ;//定义指向二叉树的指针
1.3二叉树的遍历
由于二叉树的递归性质，遍历算法也是递归的。三种基本的遍历算法如下：
先访问树根，再访问左子树，最后访问右子树；（先序遍历）
先访问左子树，再访问树根，最后访问右子树；（中序遍历）
先访问左子树，再访问右子树，最后访问树根；（后序遍历）
先序遍历算法
1）若二叉树为空树，则空操作；
2）否则
访问根结点
先序遍历左子树
先序遍历右子树
void PREORDER ( bitree *r)
{
if ( r = = NULL ) return ; //空树返回
printf ( “ %c ”,r->data ); //先访问当前结点
PREORDER( r->lchild ); //递归再访问该结点的左子树
//如果这里看不懂,再返回去看上面那张图理解先序遍历的递归含义，
//且先把这里理解了，以下两种遍历就会清晰明了
PREORDER( r->rchild ); //递归最后访问该结点右子树
}中序遍历算法
1）若二叉树为空树，则空操作；
2）否则
中序遍历左子树
访问根结点
中序遍历右子树
void INORDER ( bitree *r)
{
if ( r = = NULL ) return ; //空树返回
INORDER( r->lchild ); //先访问该结点的左子树
printf ( “ %c ”,r->data ); //再访问当前结点
INORDER( r->rchild ); //最后访问该结点右子树
}
//会发现，其实中序遍历就是把先序遍历的访问顺序调换位置
//以此类推，后序遍历也是调换访问顺序后序遍历算法
1）若二叉树为空树，则空操作；
2）否则
后序遍历左子树
后序遍历右子树
访问根结点
void POSTORDER ( bitree *r)
{
if ( r = = NULL ) return ; //空树返回
POSTORDER( r->lchild ); //先访问该结点的左子树
POSTORDER( r->rchild ); //再访问该结点右子树
printf ( “ %c ”,r->data ); //最后访问当前结点
}还有就是按层数遍历
以上图为例
顾名思义按层数就是一层一层的从上到下从左到右访问
访问顺序就是
A ->B->E->C->F->D->G->H->K
所以，可以运用队列的思想来完成对它遍历 //用队列实现输出二叉树结构体
算法实现思路
1）若二叉树为空树，则空操作
2）否则；
访问当前节点（出队节点），将该节点出队
判断当前节点是否有左孩子，有则将左孩子入队
判断当前节点是否有右孩子，有则将右孩子入队
NOORDER ( bitree *r)
{
int front, rear;
bitree *Q[N];
if ( r == NULL )
{
return ;
}
for (rear=1;rear<N; rear++)
{
Q[rear] = NULL ;
}
front = rear = 1; Q[rear] = r;
while ( Q[front] != NULL )
{
DeQueue(Q, p); //队头结点出队
show(p); //访问出队结点
if(p->lchild != NULL){
EnQueue(Q, p->lchild); //左子树不空，则左子树根节点入队
}
if(p->rchild != NULL)
{
EnQueue(Q, p->rchild); //右子树不空，则右子树根节点入队
}
front++; //front向后移动
}
}
本文含有隐藏内容，请 开通VIP 后查看