一、关于树：
数的定义是递归的：
定义树是满足以下条件的，包含至少一个结点的有限集合：
（1）树中有一个特别指定的结点，称为根，或树根。
（2）其它结点划分成n>=0个不相交的集合T1…Tn ,每个集合又还是一棵树，但称为根的子树。
树的主要操作包括：求树的深度、求给定节点的子节点、兄弟节点、遍历树、插入子树、删除子树等等。
因为树的定义本身就是递归的，所以在实际的程序中，很多操作也是通过递归来完成的。树是如何表示的
呢？有一种常用的表示方法，成为孩子、兄弟表示法，对于每个节点，通过孩子指针指向自己的子节点，
通过兄弟指针指向自己右边的兄弟。
二、树的存储方法：
双亲表示法（顺序存储）
孩子表示法（顺序存储与链式存储结合）
孩子兄弟表示法/二叉树表示法/二叉链表表示法（顺序存储与链式存储结合）(左链域为该节点的第一个孩子，右链域为该节点的下一个兄弟)
三、基本操作：
//节点
typedef struct CSNode{
char data;
struct SCNode *firstchild,*nextsibling;
}TNode,*Tree;
构造树与删除树，插入子树与删除子树
1.构造树
Tree InitTree(){
Tree T=NULL;
int ch;
ch=getchar();
if(ch!='#'){
T=(Tree)malloc(sizeof(TNode));
T->firstchild=NULL;
T->nextsibling=NULL;
T->data=ch;
}
return T;
}
2.插入子树
Tree pos=NULL; //标记子树的父节点的位置
bool insertSubTree(Tree T,ElemType e,Tree Tadd)
{
locateElem(T,e); //查找到其父节点位置
if(pos!= NULL)
{
Tadd->nextSibling=pos->firstChild; //将新子树根节点作为该节点的最左孩子
pos->firstChild=Tadd;
return true;
}
else
return false;
}
3.删除树(调用删除函数逐个删除节点)
void deleteTree(Tree T){
if(!T)
return OK;
else{
deleteTree(T->firstchild);
deleteTree(T->nextsibling);
free(T);
T=NULL;
}
}
4.删除子树
Tree pos=NULL;//标记其父节点的位置
bool deleteSubTree(Tree T,ElemType e)
{
locateElem(T,e);
//先判断pos是否有孩子节点
if(pos->firstChild!=NULL)
{
deleteTree(pos->firstChild); //调用删除树函数，删除以该节点最左孩子为根节点的子树
return true;
}
else
return false;
}
----------------------------------------------------------------------------------------
遍历树
//先序遍历
void TraverseTree(Tree T){
if(T){
visit(T->data);
TreaverseTree(T->firstchild);
TreaverseTree(T->nextsibling);
}
return 0;
}
//或者
void TraverseTree(Tree T){
Tree p;
if(T){
visit(T->data);
p=T->firstchild;
while(!p){
TreaverseTree(p);
p=p->nextsiling;
}
}
return 0;
}
------------------------------------------------------------------------------------------
查找某个节点x，查找左孩子，右兄弟
Tree p; //用全局变量标记查找到的节点
Tree searchnode(Tree &T,char ch){
p=T;
if(T){
if(p->data==ch)
return p;
else{
p=T->firstchild;
while(p){
searchnode(p->firstchild,ch);
p=p->nextsibling;
}
}
return Null;
}
1.查找某个节点的左孩子
Tree findChild(Tree T,ElemType e)
{
searchnode(T,e);
//如果没有找到或者该节点是叶子节点，返回空
if( p==NULL&&NULL==p->firstChild)
return NULL;
else
return p->firstChild;
}
2.查找某个节点的右兄弟
Tree findSibling(Tree T,ElemType e)
{
searchnode(T,e);
//如果没有找到或者该节点没有右兄弟，返回空
if(p==NULL&&p->nextSibling==NULL)
return NULL;
else
return p->nextSibling;
}
------------------------------------------------------------------------------------------
求树的高度
void TreeDepth(Tree T){
int height=0,hmax=0;
if(T){
Tree p=T->firstchild;
while(p){
height=TreeDrpth(p);
p=p->nextsibling;
if(hmax
hmax=height;
}
}
return hmax+1;
}
--------------------------------------------------------------------------------------
总结：对于树的核心操作，毫无疑问是如何递归的遍历一棵树。我们的作法是这样的：
对于一个节点，先访问它的数据域，然后通过孩子指针来访问它的孩子，一直到
沿着这条分支的叶子节点，此时，访问这个节点的兄弟，直到所有的兄弟都访问
过了，然后回退到上一节点，访问它的兄弟，依次类推。