树的基本概念
书上是这么描述树的：树是由n个结点组成的有限集合，如果n=0，这是一颗空树，n>0，这n个结点中有且仅有一个结点作为树的根节点，其余节点可分为m个互不相交的有限集，其中每个子集本身又是一棵符合本定义的树，称为根结点的子树。
当然上面的定义肯定就是不包括无根树的(数据结构里面对树的定义和离散数学里面对树的定义有一些区别，数据结构里面的树相当于离散数学中的有向有根树，方向的定义为上层到下层的方向)。在树的定义中又用到树的定义，可以体现出树的递归性。
先看一些对于树的表达方式和相关的性质结论。
树的基本术语
就是树中的一些概念，基本上都是离散上面的。
结点的度和树的度
某个结点的子节点(子树)称为该节点的度。一棵树中所有结点的度的最大值称为树的度，通常将度为m的树称为m次树，上面的树即是三次树。
因为数据结构中的树相当于有根有向树，定义方向为从上层到下层，某个节点的度可以理解为该节点的出度，树的度即是整个图的最大出度。
分支节点与叶子结点
树中度不为0的结点称为非终端结点，又叫分支结点，度为0的结点称为终端结点，又称为叶子结点。度为1的结点称为单分支结点，度为2的结点称为双分支结点。
路径与路径长度
就是离散概念上有向图两个结点之间的的路径：对于树上的两个结点u和v，如果存在一个长度为k+2的结点序列(u,x1·····,xk,v)，k≥0，使得对于序列中除了u的任一结点都是其在序列中前一个结点的后继节点，则称该节点序列为由u到v的路径，路径的长度为k+1(即路径上经过的边数)。
u->v的结点序列为路径，v->u逆序的结点序列则称为逆路径。
孩子节点，双亲结点和兄弟结点
结点的后继结点即称为该节点的孩子节点，相应地，该节点称为其孩子结点的双亲结点。具有同一双亲结点的孩子节点互为兄弟节点。
(事实上与其说是双亲结点，一般是单亲结点)
结点层次和树的高度
树中的每个结点都处在一定的层次上。结点层或者说结点深度就是从树根开始定义用来表示每个结点对应层次的属性。根结点在第一层，其余的结点遵循一个结点所在层次为其双亲结点所在层次+1的原则，树中结点的最大层次称为树的高度或者树的深度。
有序树和无序树
兄弟节点之间的次数不能随意改变的我们称为有序树，否则称为无序树。一般没有特别说明的都是有序树。
例如treap树，splay树这种平衡二叉搜索树左右孩子结点就不能随意的调换顺序，但像并查集这种结构，结点与结点之间的次序关系没什么意义，就是无序树。
森林
n个互不相交的树的集合称为森林。把含有多棵子树的树的根结点删去就成了森林，反之给m棵独立的树加上一个根结点，并把m棵树作为该结点的子树，则森林就成为了一棵树。
树的逻辑表示方法
就是用一种方式来准确地表示树中结点与节点之间层与层，次序与次序之间的关系，例如广义表中的括号表达法和图形表示法(图形法因为觉得比较简单就没有拿出来介绍)。
树形表达法
类似于广义表中的图形表达法，用一个圆圈表示一个结点，圆圈内的符号表示该节点的数据信息，结点与结点之间存在的关系用连线表示。
和离散数学中不同的是，这里结点与结点之间的连线表示一种有向关系，方向时从上到下的，连线中上方的结点是下方结点的前驱节点，反之下方结点是上方结点的后继节点。
最终得到的图像是一颗倒置的树。
文氏图表达法
这种表达法体现的是树在集合方面和递归方面的性质。用文氏图的一个圈来包括某棵子树的所有元素，圆圈内包括根结点和子树的圆圈，同一个根结点各子树对应的圆圈分属不同的集合，所以不允许相交。得到的图像如下：
可以发现文氏图表达法比起树形表示法的区别在于将每棵树(子树)的元素看作一个元素集合，对于集合而言，并不太看重元素与元素之间的次序关系，强调的只是包含与不包含的关系。例如元素E和元素F，通过文氏图我们只能得到他们都是结点B的子节点，不能知道元素E和元素F之间哪个相对位置较前(左)，哪个相对位置较后(右)。
文氏图一般表示的就是无序树。
凹入表示法
每个结点对于一个条形，子结点相较于根结点是一个较短的条形，且根节点在上，子节点在下。同一个结点的子节点对应的条形长度相等。表达法如下：
可以发现同层的结点(无论是不是同一个根结点的子节点)，他们对应条形的长度都是一样的。条形的长度即是深度的体现。
括号表达法
和广义表中的括号表达法极其类似，对每棵树(子树)用“根结点(子树1,子树2·····子树m)”的字符串来表达。注意是子树而不是子节点，子树的表达方式和整棵树的表达法是一样的。如果某棵子树仅包含根结点一个结点，后面的括号直接省略，这一点和广义表略有区别。表达法如下：
树的性质
1.树中的结点数等于所有结点的度数之和+1。
度其实就是边数，就是离散中树的基本性质->结点数=边数+1。
2.度为m的树中第i层最多有mi-1个结点。
用数学归纳法证明的简单结论，假设结论对i=k成立，即度为m的树中第k层最多有mk-1个结点，对于i=k+1的结论，度为m的树的第k层最多有mk-1个结点，第k+1层的结点数最多是第k层的结点数的m倍，那么度为m的树的第k+1层最多的结点数为mk-1*m=mk，与i=k+1的结论符合，结论成立。
当一颗m次数的第i层上有mi-1个结点时，称该层为满的，若一棵m次树的所有叶子结点都在同一层，并且除了该层以外的每一层都是满的，那么这棵树为满m次树。
3.高度为h的m次树最多有(mh-1)/(m-1)。
度为m的树中第i层最多有mi-1个结点，那么整棵树最多的结点数就是每层最多的结点数求和，m0+m1+m2······+mh-1=(mh-1)/(m-1)，取等的条件当且仅当这棵树为满m次树。
4.具有n个结点的m次树的最小高度为logm(n(m-1)+1)的向上取整。
设高度为h，需要该数的高度最小，前面h-1层需要尽可能的满，第h层的结点数可能是满，也可能只有1个，于是有：
(mh-1-1)/(m-1)+1≤n≤(mh-1)/(m-1)
等价于 (mh-1-1)/(m-1)＜n≤(mh-1)/(m-1)
化简有：mh-1<n(m-1)+1≤mh
取以m为底的对数：h-1＜logm(n(m-1)+1)<=h，即logm(n(m-1)+1)<=h＜logm(n(m-1)+1)+1
因为h为整数，所以h等于logm(n(m-1)+1)的向上取整。
n个结点m次数的最大高度为n-m+1，这个比较简单就不做证明了。
树的基本运算
树的基本运算主要分为以下三种：
1.最基本也是我个人认为最重要的，树的遍历，即遍历树上所有结点。
2.查找，即查找满足某种条件的结点。
3.插入和删除，插入和删除某个结点。
书上主要只介绍了三种遍历，先根遍历，后根遍历和层次遍历，先根遍历是先访问根结点再按照从左到右的顺序遍历根节点的每一棵子树，二叉树中的先序遍历即是一种特殊树类的先根遍历。同理，后根遍历是先按照从右到左的顺序遍历根节点的每一棵子树，再遍历根结点。
向上面的两种遍历方式，遍历子树的规则和遍历总树的方法一致，我们可以将一棵大树的遍历分割成几棵小树的遍历。我们往往会用递归算法来实现这种遍历，这种遍历方式我们称为递归遍历。
层次遍历的过程是从根结点开始按照从上到下，从左到右的次序访问书中的每一个结点，层次遍历的代码编写比起递归遍历要困难一些。
树的存储结构
树的存储结构课件没有代码存储，相较二叉树并不是重点，就简单地看一下(因为我也不会)。
双亲存储结构
双亲存储结构是一种顺序存储结构，用连续的空间来存储所有的结点，每个结点定义一个parent来存储双亲结点在连续空间，即数组中的下标。
//parent为当前结点的双亲结点在tree数组中的下标
struct PTree{ElemType data; int parent;}tree[Maxsize]
这种存储结构求双亲结点非常容易，但求孩子结点就需要遍历整个数组。并且对于某些“并不满”，就是指某些结点的排列比较稀疏但是分支深度很深的树，空间的利用率会很低。
孩子链存储结构
顾名思义，就是在每个结点中用指针建立到孩子结点的链式关系。
//sons为当前结点到孩子结点的指针
struct TSonNode{ElemType data; TSonNode *sons[MaxSons];};
接下来是以孩子链为存储结构的基本操作。
建树
根据括号表达法建立树的结构。由于是按照深度优先的规则去建树，每次先将一个分支结点之间的关系建立完全，需要用栈作为辅助的数据结构来存储结点的指针和结点的度：
TSonNode *CreateTree(char *str){//由括号表达式str建立孩子链存储结构构成的树
struct{TSonNode *nodep; int num;}St[MaxSize];//用于存储结点指针以及分支结点的度(num)的顺序栈
//栈中存放的结点都是含有子节点的结点,由于是深度优先,新遍历到的结点即为当前栈顶结点的子节点
int top=-1,i=0;//栈顶指针
char ch=str[i]; TSonNode *t=NULL,*p;//t为根结点指针
while (ch!='\0'){//将括号表达式str遍历一遍
switch(ch){//如果为左半括号,说明当前的结点存在子节点,将该结点进栈,num置0
case '(':top++; St[top].nodep=p; St[top].num=0; break;
case ')':top--; break;//栈顶结点的子树遍历完全,出栈
case ',':St[top].num++; break;//遇到逗号,说明有新的子节点,num++
default://如果为字母,说明有新的结点,给结点分配空间和赋值
p=(TSonNode *)malloc(sizeof(TSonNode)); p->data=ch;
for (int j=0;j<MaxSons;j++) p->sons[j]=NULL;//孩子指针置空(有新结点,但不一定是新子树)
if (t==NULL) t=p;//遇到的第一个字符即为根结点
else St[top].nodep->sons[St[top].num]=p;//当前结点是栈顶结点的子节点,建立根结点指向孩子结点的指针
break;
}i++; ch=str[i];//遍历下一个结点
}return t;//返回根结点
}
和广义表那里的建表是非常类似的，一个用的是递归建表，一个用的是栈，两者之间是可以相互转化的。
(但还是有点区别的，比如广义表中存在#对应的空表，树中的终端结点后面没有任何的标记，总结下来就是树的基本操作比较好写)
打印
和广义表的打印类似，就是不用讨论空表打印的情况。
//打印树对应的括号表达式,t为根结点
void DispTree(TSonNode *t){
if (t!=NULL){printf("%c",t->data);//打印根结点
if (t->sons[0]!=NULL){printf("(");//如果sons[0]的指向不为空,说明至少有一个孩子结点,首先打印外层括号
for (int i=0;i<MaxSons;i++){DispTree(t->sons[i]);//从左到右递归打印根结点的子结点
//如果下一个指针指向的不为空,在两个子节点(子树)之间加上逗号
if (t->sons[i+1]!=NULL) printf(","); else break;
} printf(")");//打印外层括号
}
}
}
销毁
销毁树，就是先递归销毁子节点，子节点销毁完之后再往上销毁根结点。
//销毁树,t为被销毁的树的根结点
void DestroryTree(TSonNode *&t){
if (t!=NULL){
for (int i=0;i<MaxSons;i++)
if (t->sons[i]!=NULL) DestroryTree(t->sons[i]);//销毁子节点
else break;
free(t);//子节点销毁完之后,释放根结点
}
}
树的高度
和求广义表的深度基本是一样的，以当前结点为根结点的树的深度等于根结点的子树的深度的最大值+1，遇到空树返回深度为0。
//求树的高度,t为根结点
int TreeHeight1(TSonNode *t){TSonNode *p;
if (t==NULL) return 0;//遇到空树返回高度为0
else{int h,maxh=0;
for (int i=0;i<MaxSons;i++){p=t->sons[i];//求以第i+1个孩子为根结点的子树的深度
//当前结点的深度等于所有子树的深度的最大值+1
if (p!=NULL){h=TreeHeight1(p); if (maxh<h) maxh=h;}
}return(maxh+1);//返回子树的最大深度+1
}
}
操作合集如下：
//sons为当前结点到孩子结点的指针
struct TSonNode{ElemType data; TSonNode *sons[MaxSons];};
TSonNode *CreateTree(char *str){//由括号表达式str建立孩子链存储结构构成的树
struct{TSonNode *nodep; int num;}St[MaxSize];//用于存储结点指针以及分支结点的度(num)的顺序栈
//栈中存放的结点都是含有子节点的结点,由于是深度优先,新遍历到的结点即为当前栈顶结点的子节点
int top=-1,i=0;//栈顶指针
char ch=str[i]; TSonNode *t=NULL,*p;//t为根结点指针
while (ch!='\0'){//将括号表达式str遍历一遍
switch(ch){//如果为左半括号,说明当前的结点存在子节点,将该结点进栈,num置0
case '(':top++; St[top].nodep=p; St[top].num=0; break;
case ')':top--; break;//栈顶结点的子树遍历完全,出栈
case ',':St[top].num++; break;//遇到逗号,说明有新的子节点,num++
default://如果为字母,说明有新的结点,给结点分配空间和赋值
p=(TSonNode *)malloc(sizeof(TSonNode)); p->data=ch;
for (int j=0;j<MaxSons;j++) p->sons[j]=NULL;//孩子指针置空(有新结点,但不一定是新子树)
if (t==NULL) t=p;//遇到的第一个字符即为根结点
else St[top].nodep->sons[St[top].num]=p;//当前结点是栈顶结点的子节点,建立根结点指向孩子结点的指针
break;
}i++; ch=str[i];//遍历下一个结点
}return t;//返回根结点
}//打印树对应的括号表达式,t为根结点
void DispTree(TSonNode *t){
if (t!=NULL){printf("%c",t->data);//打印根结点
if (t->sons[0]!=NULL){printf("(");//如果sons[0]的指向不为空,说明至少有一个孩子结点,首先打印外层括号
for (int i=0;i<MaxSons;i++){DispTree(t->sons[i]);//从左到右递归打印根结点的子结点
//如果下一个指针指向的不为空,在两个子节点(子树)之间加上逗号
if (t->sons[i+1]!=NULL) printf(","); else break;
} printf(")");//打印外层括号
}
}
}//销毁树,t为被销毁的树的根结点
void DestroryTree(TSonNode *&t){
if (t!=NULL){
for (int i=0;i<MaxSons;i++)
if (t->sons[i]!=NULL) DestroryTree(t->sons[i]);//销毁子节点
else break;
free(t);//子节点销毁完之后,释放根结点
}
}//求树的高度,t为根结点
int TreeHeight1(TSonNode *t){TSonNode *p;
if (t==NULL) return 0;//遇到空树返回高度为0
else{int h,maxh=0;
for (int i=0;i<MaxSons;i++){p=t->sons[i];//求以第i+1个孩子为根结点的子树的深度
//当前结点的深度等于所有子树的深度的最大值+1
if (p!=NULL){h=TreeHeight1(p); if (maxh<h) maxh=h;}
}return(maxh+1);//返回子树的最大深度+1
}
}
这种存储结构的缺点就是难以查找某节点的双亲结点，并且当树的度比较大时存在大量的空指针域。
孩子兄弟链存储结构
同样是顾名思义，就是在每个结点中用指针建立到兄弟结点和孩子节点的链式关系。但是兄弟结点和孩子结点都有多个，如果全部保存，不仅浪费空间，还需要一个属性来存储当前结点在兄弟结点中的位置。
考虑到广义表中，用sublist指向子表，link遍历整个表。可以用兄弟结点来遍历所有的双亲结点所有的子节点，于是对于存在子节点的结点只需要指向它最左边的子结点即可。
//孩子兄弟链存储结构类型
struct TSBNode{ElemType data;
TSBNode *hp,*vp;//hp指向右边相邻的兄弟节点,vp指向孩子结点中最左边的那个
};
建树
和孩子链那里相比，只有在遍历字母(结点)时不同。因为孩子链中是建立双亲结点到孩子结点的关系，而在孩子兄弟链中，只需要建立一次双亲结点到孩子结点的关系，即当结点存在子节点，且num值等于0，建立栈顶结点到当前结点的关系。对于其他的孩子结点，即num不等于0时，即从当前栈顶结点最左的儿子结点(vp)查询到最右的兄弟结点(hp)，然后在最后添加一个新的兄弟结点。
TSBNode *CreateTree(char *str){//由括号表达式str建立孩子兄弟链存储结构构成的树
struct{TSBNode *nodep; int num;}St[MaxSize];//用于存储结点指针以及分支结点的度(num)的顺序栈
//栈中存放的结点都是含有子节点的结点,由于是深度优先,新遍历到的结点即为当前栈顶结点的子节点
int top=-1,i=0;//栈顶指针
char ch=str[i]; TSonNode *t=NULL,*p,*q;//t为根结点指针
while (ch!='\0'){//将括号表达式str遍历一遍
switch(ch){//如果为左半括号,说明当前的结点存在子节点,将该结点进栈,num置0
case '(':top++; St[top].nodep=p; St[top].num=0; break;
case ')':top--; break;//栈顶结点的子树遍历完全,出栈
case ',':St[top].num++; break;//遇到逗号,说明有新的子节点,num++
default://如果为字母,说明有新的结点,给结点分配空间和赋值
p=(TSBNode *)malloc(sizeof(TSonNode)); p->data=ch;
p->hp=p->vp=NULL;//指针置空
if (t==NULL) t=p;//遇到的第一个字符即是根结点
else{//num等于0,说明当前结点是栈顶结点最左边的(第一个的)儿子结点
if (St[top].num==0) St[top].nodep->vp=p;
else{//其他孩子用栈顶节点的孩子节点尾部的hp指向它
q=St[top].nodep->vp;
for (int j=1;j<St[top].num;j++) q=q->hp;
q->hp=p;//为新的最右边的兄弟结点
}
}
break;
}i++; ch=str[i];//遍历下一个字符
}return t;//返回根结点
}
其实我个人是觉得对于孩子兄弟链存储结构判空就可以了，不用定义一个num来找最右的兄弟结点和判断是否为第一个兄弟节点。
打印
同样的就是遍历孩子结点的方式不同，一个是按照链式遍历，一个是按照顺序方式遍历。
//打印括号表达式
void DispTree(TSBNode *t){TSBNode *p;
if (t!=NULL){printf("%c",t->data);//打印根结点的值
if (t->vp!=NULL){printf("(");//至少有一个孩子,即有子树时输出外层的括号
p=t->vp;//用p遍历根结点所有的子节点,并进行递归打印
while (p!=NULL){DispTree(p); p=p->hp;
if (p!=NULL) printf(",");//存在下一个兄弟结点是,打印一个逗号进行分隔
} printf(")");//打印外层括号
}
}
}
销毁
销毁始终是最简单的，按照从下到上，从右到左的顺序进行销毁即可(始终要记得销毁的顺序和建立的顺序是相反的)。
//销毁,t为根结点
void DestroryTree(TSBNode *&t){//首先销毁下层的子节点,再销毁当前层靠右的兄弟结点,最后销毁自己
if (t!=NULL){DestroryTree(t->vp); DestroryTree(t->hp); free(t);}
}
树的高度
树的高度的求法思想始终是一样的，依旧是遍历方式的区别。
//求树的高度,t为根结点
int TreeHeight2(TSBNode *t){TSBNode *p;
if (t==NULL) return 0;//空树返回高度为0
else{p=t->vp; int h,maxh=0;//指向第1个孩子节点,遍历所有的子节点(子树)
//当前结点的深度等于所有子树的深度的最大值+1
while (p!=NULL){h=TreeHeight2(p); if (maxh<h) maxh=h; p=p->hp;}
return(maxh+1); //返回子树的最大深度+1
}
}
操作合集如下：
//孩子兄弟链存储结构类型
struct TSBNode{ElemType data;
TSBNode *hp,*vp;//hp指向右边相邻的兄弟节点,vp指向孩子结点中最左边的那个
};
TSBNode *CreateTree(char *str){//由括号表达式str建立孩子兄弟链存储结构构成的树
struct{TSBNode *nodep; int num;}St[MaxSize];//用于存储结点指针以及分支结点的度(num)的顺序栈
//栈中存放的结点都是含有子节点的结点,由于是深度优先,新遍历到的结点即为当前栈顶结点的子节点
int top=-1,i=0;//栈顶指针
char ch=str[i]; TSonNode *t=NULL,*p,*q;//t为根结点指针
while (ch!='\0'){//将括号表达式str遍历一遍
switch(ch){//如果为左半括号,说明当前的结点存在子节点,将该结点进栈,num置0
case '(':top++; St[top].nodep=p; St[top].num=0; break;
case ')':top--; break;//栈顶结点的子树遍历完全,出栈
case ',':St[top].num++; break;//遇到逗号,说明有新的子节点,num++
default://如果为字母,说明有新的结点,给结点分配空间和赋值
p=(TSBNode *)malloc(sizeof(TSonNode)); p->data=ch;
p->hp=p->vp=NULL;//指针置空
if (t==NULL) t=p;//遇到的第一个字符即是根结点
else{//num等于0,说明当前结点是栈顶结点最左边的(第一个的)儿子结点
if (St[top].num==0) St[top].nodep->vp=p;
else{//其他孩子用栈顶节点的孩子节点尾部的hp指向它
q=St[top].nodep->vp;
for (int j=1;j<St[top].num;j++) q=q->hp;
q->hp=p;//为新的最右边的兄弟结点
}
}
break;
}i++; ch=str[i];//遍历下一个字符
}return t;//返回根结点
}//打印括号表达式
void DispTree(TSBNode *t){TSBNode *p;
if (t!=NULL){printf("%c",t->data);//打印根结点的值
if (t->vp!=NULL){printf("(");//至少有一个孩子,即有子树时输出外层的括号
p=t->vp;//用p遍历根结点所有的子节点,并进行递归打印
while (p!=NULL){DispTree(p); p=p->hp;
if (p!=NULL) printf(",");//存在下一个兄弟结点是,打印一个逗号进行分隔
} printf(")");//打印外层括号
}
}
}//销毁,t为根结点
void DestroryTree(TSBNode *&t){//首先销毁下层的子节点,再销毁当前层靠右的兄弟结点,最后销毁自己
if (t!=NULL){DestroryTree(t->vp); DestroryTree(t->hp); free(t);}
}//求树的高度,t为根结点
int TreeHeight2(TSBNode *t){TSBNode *p;
if (t==NULL) return 0;//空树返回高度为0
else{p=t->vp; int h,maxh=0;//指向第1个孩子节点,遍历所有的子节点(子树)
//当前结点的深度等于所有子树的深度的最大值+1
while (p!=NULL){h=TreeHeight2(p); if (maxh<h) maxh=h; p=p->hp;}
return(maxh+1); //返回子树的最大深度+1
}
}
孩子兄弟链的存储结构和广义表的存储结构是非常非常类似的，只不过树的每一个结点都存在一个data值，而广义表的结点只能是data和sublist之一(值和子表之一)，所以我个人觉得广义表基本操作的编写要比孩子兄弟链存储结构的树基本操作的编写要困难不少。
相较于二叉树，单一的树始终不是介绍的重点。