树
一、定义
数据结构和树状图差不多，有一个根的节点，有若干个互不相交的子树，这些子树本身也是一棵树
二、专业术语
节点 父节点 子节点
子孙 堂兄弟（不同父节点的同一辈分的节点）
深度：从根节点到最底层节点的层数称之为深度，根节点是第一层
叶子节点：没有子节点的节点
非终端节点：非叶子节点
度：该子节点的个数，整个树的度为最大度数节点的度数
三、树的分类
一般树：任意一个节点的子节点的个数都不受限制的树；
二叉树：只有一个根节点，任意一个节点的子节点个数最多两个，且子节点的位置不能更改，有一般二叉树（各节点未饱和）、满二叉树（饱和）、完全二叉树（如果只是删除了满二叉树最底层最右边的连续若干个节点，这样形成的二叉树就是完全二叉树）的分类。二叉树是重点
森林: n个互不相交的集合，多个根节点
四、针对不同树有不同存储方式
一般树
双亲表示法、孩子表示法、双亲孩子表示法、
二叉树表示法：把一个普通树转换成二叉树来存储，具体转换方法：设法保证任意一个节点地左指针域指向它地第一个孩子，右指针域指向它的亲兄弟。只要能满足此条件，就可以把一个一般树转换为二叉树。一个普通树转化成的二叉树一定没有右子树
森林
同上，转换为二叉树存储。
二叉树
连续存储【只有完全二叉树可以连续存储】
优点：查找某个节点的父节点和子节点（也包括判断有没有子节点）速度很快
缺点：很耗内存，要有层次地存储
链式存储
优点：可以只存放有效节点，相对比较简单，相对耗内存也比较少，且不需要有层次地存储
五、二叉树的遍历
l 二叉树的操作：一种是遍历，有三个，是将非线性转化为线性存储的方法；另一种是已知遍历序列求原二叉树。
l 二叉树连续存储的先序遍历操作（重点）：
先访问根节点，再先序访问左子树，再先序访问右子树。有递归思想
l 二叉树连续存储的中序遍历操作（重点）：
中序遍历左子树，再访问根节点，再中序遍历右子树
l 二叉树连续存储的后序遍历操作（重点）：
中序遍历左子树，中序遍历右子树，再访问根节点
l 只有已知两种遍历序列才可以求出原始二叉树
通过先序和中序、或者中序和后序我们可以还原出原始的二叉树，但是通过先序和后序无法还原出原始的二叉树。当然，单靠一个更不可能还原出。
六、链式存储二叉树程序（递归实现）
#include<stdio.h> #include<malloc.h> typedef struct BTNode { char data; struct BTNode *pLchild; struct BTNode *pRchild; }BTNODE,*PBTNODE; PBTNODE CreateBTree(); void PreTraverseBTree(PBTNODE); void InraverseBTree(PBTNODE); void PostTraverseBtree(PBTNODE); int main() { PBTNODE pT; pT=CreateBTree(); PreTraverseBTree(pT);//先序遍历 printf("*********\n"); InraverseBTree(pT); printf("*********\n"); PostTraverseBtree(pT); return 0; } void PreTraverseBTree(PBTNODE pT) { /*用递归实现：先访问根节点，再先序访问左子树，再右子树*/ if(pT!=NULL) { printf("%c\n",pT->data); if(pT->pLchild!=NULL) PreTraverseBTree(pT->pLchild); if(pT->pRchild!=NULL) PreTraverseBTree(pT->pRchild); } return; } void InraverseBTree(PBTNODE pT) { if(pT!=NULL) { if(pT->pLchild!=NULL) PreTraverseBTree(pT->pLchild); printf("%c\n",pT->data); if(pT->pRchild!=NULL) PreTraverseBTree(pT->pRchild); } return; } void PostTraverseBtree(PBTNODE pT) { if(pT!=NULL) { if(pT->pLchild!=NULL) PreTraverseBTree(pT->pLchild); if(pT->pRchild!=NULL) PreTraverseBTree(pT->pRchild); printf("%c\n",pT->data); } return; } PBTNODE CreateBTree()//静态创建树 { PBTNODE pA=(PBTNODE)malloc(sizeof(BTNODE)); PBTNODE pB=(PBTNODE)malloc(sizeof(BTNODE)); PBTNODE pC=(PBTNODE)malloc(sizeof(BTNODE)); PBTNODE pD=(PBTNODE)malloc(sizeof(BTNODE)); PBTNODE pE=(PBTNODE)malloc(sizeof(BTNODE)); pA->data=‘A‘; pB->data=‘B‘; pC->data=‘C‘; pD->data=‘D‘; pE->data=‘E‘; pA->pLchild=pB; pA->pRchild=pC; pB->pLchild=pB->pRchild=NULL; pC->pLchild=pD; pC->pRchild=NULL; pD->pLchild=NULL; pD->pRchild=pE; pE->pLchild=pE->pRchild=NULL; return pA; }