基本概念：
1.树
树是n个结点的有限集，他或是空树，或是非空树。对于非空树，有且仅有一个称之为根的结点，除根节点以外，其余结点可分为互不相交的有限集，他们每棵又都是树，称为根的子树。树的结构的定义是一个递归的定义。
2.结点
树中一个独立单元，包含一个数据元素及若干指向其子树的分支。
3.结点的度
结点拥有的子树数
4.树的度
树内各结点度的最大值
5.有序树，无序树
如果将树中结点的各子树看成从左至右是有次序的，则称为有序树，反之为无序树。
6.二叉树
树是n个结点的有限集，他或是空树，或是非空树。对于非空树，有且仅有一个称之为根的结点，除根节点以外，其余结点可分为互不相交的有限集，他们每棵又都是树，称为根的子树。树的结构的定义是一个递归的定义。并且二叉树每个结点最多只有两棵子树，二叉树子树有左右之分，次序不能任意颠倒。
7.完全二叉树
深度为k，有n个结点的二叉树,当且仅当每一个结点的深度都为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。叶子结点只可能出现在最大的两层上，对任一结点若其右分支子孙深度为l,则其左分支子孙深度必然是l或l+1;
8.线索二叉树
结点有五个区域：数据域，左孩子(lchild)，右孩子(rchild)，LTag，RTag；
LTag： LTag=0 lchild表示左孩子
LTag=1 lchild表示该结点前驱
RTag： RTag=0 rchild表示右孩子
RTag=1 rchild表示该结点后继
性质
1.在二叉树上第i层至多有个结点（i>=1）
2.深度为k的二叉树至多有个结点（k>=1）
3.对任何一棵二叉树T，如果其终端结点树是n0,度为2的结点树是n2,则n0=n2+1,n=n0+n1+n2
4.具有n个结点的完全二叉树深度为
存储结构
顺序存储：
对于完全二叉树，从根按层存储，依次自上而下，自左而右存储结点元素。如果不是完全二叉树，其他情况可能造成空间浪费
#define MAXSIZE 100 //二叉树最大结点个数 typedef TElemType SqBiTree[MAXSIZE] //0号单元存储根结点 SqBiTree bt;链式存储：（链表头指针指向根结点）
二叉链表：
数据域，左指针域，右指针域。---------------------含有n个结点的二叉链表有n+1个空链域
三叉链表：
数据域，左指针域，右指针域，指向双亲结点指针域。
typedef struct BiTNode { TElemType data;//数据域 struct BiTNode *lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree;
遍历 ( 以一定规则将二叉树中结点排成一个线性序列，得到二叉树结点的先序序列，中序序列，后序序列===对非线性结构进行线性操作，是每个结点有且仅有一个直接前驱和直接后继(除第一个和最后一个以外)
遍历二叉树
以中序为例：先遍历左子树，根结点，右子树
void InOrderTraverse(BiTree T) { if(T)//二叉树非空 { InOrderTraverse(T->left);//遍历左子树 printf（"%d ",T->data）;//访问根结点 InOrderTraverse(T->right);//遍历右子树 } }
遍历线索二叉树
以中序为例
void InOrderTraverse_Thr(BiThrTree T) {//中序遍历，对每个直接输出 //T指向头结点，头结点的左链表lchild指向根结点 p=T->lchild; //p指向根结点 while(p!=T) //p==T空树或遍历结束 { while(p->LTag==0)//沿着左孩子向下 { p=p->lchild; printf("%d ",p->data); } while(p->RTag==1&&p->rchild!=T)//沿着右线索访问后继结点 { p=p->rchild; printf("%d ",p->data); } p=p->rchild; } }
树和森林
哈夫曼树
后面两点晚点补起来
