树：
1.有且仅有一个称为根的节点，
2.有若干个互不相交的子树，这些子树本身也是一棵树

树的分类

• 一般树
  任意一个节点的子节点的个数都不受限制
• 二叉树(还有其他分类) 任意一个节点的子节点的个数最多两个,且子节点的位置不可更改
  还可以具体分类: 一般二叉树 满二叉树 完全二叉树(只删除满二叉树的最后一层从右到左若干节点的树)
• 森林
  n个互不相交的树的集合

树的存储

主要部分是二叉树的存储

• 连续存储
  具体的存储基本上是转成完全二叉树后来存储,虽然很费内存,但是操作起来会相对轻松一点,查找父节点和子节点速度很快
• 链式存储
  每一个节点分三块,左节点指针域,右节点指针域,数据域,没有孩子的指针域值为null,N个节点只耗用N+1个存储空间(线性浪费)

一般树的存储方法有:

• 双亲表示法
  类似数组,每个节点记录父节点的下标 –方便求父节点
• 孩子表示法
  类似数组,每个节点后用指针记录所有孩子 –方便求子节点
• 双亲孩子表示法
  类似数组,存两个值,一个是父节点的下标,另外一个记录孩子的指针
• 二叉树表示法
  把一个普通树转化成二叉树来存储,需要让左指针指向它第一个孩子,右指针指向它的兄弟 –也就会没有右子树

文件的存储就是树,有具体的层次结构

森林的存储
转化为二叉树后在存储,也就是把树根当作右子树链接在上一棵树,剩下的部分和二叉树表示法类似,左指针指向它第一个孩子,右指针指向它的兄弟

树的相关操作

二叉树的遍历:
这里其实就包含一种递归思想

• 先序遍历(根左右)
• 中序遍历(左根右)
• 后序遍历(左右根)

还可以通过先序和中序，或者中序和后序可以还原出原始的二叉树，但是通过先序和后序无法做到的

树的应用

树是数据库种数据组织的一种重要形式
操作系统进程的子线程和进程的关系也就是树
面向对象语言中类的继承关系
哈夫曼树

树的遍历：

void PreTraverseBTree(BTNode *pT)//根左右--递归
{
    if(pT != NULL) //递归条件
    {
        printf("%c  ",pT->data);
        if(NULL != pT->pLchild)
        {
            PreTraverseBTree(pT->pLchild);
        }
        if (NULL != pT->pRchild)
        {
            PreTraverseBTree(pT->pRchild);
        }
    }
}

代码中暂时实现的树结构是静态版本，简单但是并不完善，动态版本和其余部分逐渐完善中

最终的代码存放在Github仓库 Tree部分