【www.bbyears.com--php基础】
一:树的创建
在数据结构中，树是以二叉树的形式储存的。
树转换为二叉树形式分为三步：
⑴加线――树中所有相邻兄弟之间加一条连线。
⑵去线――对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。
⑶层次调整――以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。
转换后结果如图：
所以树的创建算法有两个思路：
1.将树转化为二叉树后，以二叉树中结点的关系输入而创建树。
2.直接以树中结点的关系输入，用代码转换为相应的二叉树。
第一种方法实际就是二叉树创建，只不过是先把树结构转化为二叉树结构，然后再输入创建。
算法思路：
1.每个结点有三个数据信息需要输入，分别是fa,ch,lrflag。（fa是父元素结点的数据，用于找到父元素结点的位置，ch为输入结点的数据，lrflag记录插入父元素的左孩子还是右孩子）
2.每输入一个结点的信息，先进队列，再通过fa在队列中得到父元素结点的地址，最后根据lrflag将新结点插入相应的位置。
3.当输入的ch为指定'#',即无数据时，停止循环。
void CreatBitree2(BiTree *T) //读边按层次创建二叉树
{
LinkQueue Q;
InitQueue(&Q);
BiTree p,s;
char fa,ch;
int lrflag;
setbuf(stdin,NULL); //清空键盘输入
scanf("%c%c%d",&fa,&ch,&lrflag);
while(ch != '#')
{
p = (BiTree)malloc(sizeof(BiNode)); //二叉树结点p用来记录新数据
p->data = ch;
p->lchild = p->rchild = NULL; //置空
EnQueue(&Q,p); //父结点入队列
if(fa == '#')
{
*T = p; //如果fa为# 则p为总的根结点T
}
else
{
GetHead(Q,&s);
while(s->data != fa) //找到插入结点的父结点的位置
{
DeQueue(&Q,&s);
GetHead(Q,&s);
}
// 此时s为父结点
if(lrflag == 0) //如果子结点标记为0，将新结点p与父节点lchild连接
{
s->lchild = p;
}
else if(lrflag == 1)
{
s->rchild = p; //同理，p连上父结点rchild
}
else
{
free(p);
printf("输入错误！按任意键重新输入...."); //标志输入错误，新结点释放重新输入
getch();
}
}
setbuf(stdin,NULL); //清空键盘输入
scanf("%c%c%d",&fa,&ch,&lrflag);
}
}第二种方法就是直接输入树中结点，通过代码的处理转化为二叉树结构，与第一种方法的处理顺序是相反的。
这种算法与第一种的二叉树创建的算法有一点区别，因为没有左右孩子，树的结构体定义与二叉树不同，所以不需要lrflag,而是将有相同父元素的结点以兄弟指针连起来。
算法思路：
1.每个结点有二个数据信息需要输入，分别是fa,ch.（fa是父元素结点的数据，用于找到父元素结点的位置，ch为输入结点的数据）
2.每输入一个结点的信息，先进队列，再通过fa在队列中得到父元素结点的地址，如果父元素结点的firstchild指针为空，则firstchild连接上新结点。若不为空，则连上当前父元素的最后一个兄弟结点的nextsibling指针。
3.当输入的ch为指定'#',即无数据时，停止循环。
void CreateCSTree(CSTree *T)//树的按边层次创建
{
LinkQueue Q;
InitQueue(&Q);
CSTree p,s,sign;
char fa,data;
printf("请输入新建结点的父元素和子元素的数据：");
scanf("%c %c",&fa,&data); //scanf(" %c") 一个空格在加上%c：表示读取遇到的第一个非空格字符
getchar();
while(data != '#')
{
s = (CSTree)malloc(sizeof(CSNode));
s->data = data;
s->firstchild = s->nextsibling = NULL;
EnQueue(&Q,s);
if(fa == '#')
{
*T = s;
}
else
{
GetHead(Q,&p);
while(p->data != fa)
{
DeQueue(&Q,&p);
GetHead(Q,&p);
}
//此时p为父元素结点地址
if(p->firstchild == NULL)//父元素的firstchild连接
{
p->firstchild = s;
sign = s; //父元素firstchild已被连接，用sign记住s；
}
else //父元素其他孩子连在sign的nextsibling上
{
sign->nextsibling = s;
sign = s; //依然记住，便于下一个结点连接
}
}
printf("请输入新建结点的父元素和子元素的数据：");
scanf("%c %c",&fa,&data);
getchar();
}
}
二:树的遍历
树的遍历和二叉树的遍历差不多，只是根据结构的调整，没有中序遍历。
不过有两个规则：
1.二叉树的前序遍历是树的前序遍历。
2.二叉树的中序遍历是树的后序遍历。
利用这两个规则可以直接使用二叉树的遍历算法来相应的遍历树。
三:根结点到叶子结点所有的路径
二叉树：
二叉树求从根结点到叶子结点的路径可以借助前序递归遍历的思想。
算法思路：
1.按照前序递归的思路遍历二叉树且对每个遍历的结点进栈，但是不访问
2.然后当遇到叶子结点时，按从栈底到栈顶的顺序输出栈中的数据（即为一个根结点到叶子结点的路径），然后出栈叶子结点
3.前序递归遍历的过程不断遇到叶子节点并输出路径，直到根结点出栈
void DispPath(BiTree T,SqStack *s) //输出所有的根到叶子结点的路径
{
Bitree p;
if(T)
{
Push(s,p);
if(T->lchild == NULL && T->rchild == NULL)
{
PrintStack(*s);
printf("\\n");
}
else
{
DispPath(T->lchild,s);
DispPath(T->rchild,s);
}
Pop(s),&p);
}
}
树：
由于树是以二叉树的形式存储的，所以实际的树的叶子结点与二叉树叶子结点不同。
树的叶子节点：firstchild指针为NULL的结点。
除了这个差别带来的算法带来的if条件语句的差异之外，还有一点与二叉树的根到叶子结点算法不同。
都是使用前序递归遍历的思想，但是树一直向firstchild方向遍历，遇到叶子结点，则向兄弟结点nextsibling遍历。
且需要将firstchild结点先出栈后再遍历兄弟结点，所以需要将上述的算法中向右子树的遍历放在出栈之后。
算法思路：
1.从根结点一直向firstchild方向遍历，并进栈。
2.若遍历到叶子结点则输出路径，且出栈叶子结点，然后转向兄弟结点nextsibling。
3.重复1,2步骤
void DispPath(CSTree T,SqStack *s)//输出树从根结点到叶子结点的所有路径
{
CSTree temp = T;
if(T)
{
Push(s,temp);
if(T->firstchild == NULL) //第一个孩子结点为空说明当前结点为叶子结点
{
PrintStack(*s);
printf("\\n");
}
else //一直向左遍历
{
DispPath(T->firstchild,s);
}
Pop(s,&temp);
if(T->nextsibling) //必须保证firstchild出栈后，才能向兄弟结点遍历
{
DispPath(T->nextsibling,s);
}
}
}
四：数据插入与删除
数据的插入，二叉树和树都是差不多的，插入结点是叶子结点，都是先找到父结点，然后插入。
二叉树则是分左右孩子，树则是fistchild存在，就插入兄弟结点。
在树中数据的插入
算法思路：
1.根据父元素数据找到父元素的位置
2.若当前父元素firstchild为空，则将数据连到firstchild上，否则则插入到最后一个兄弟结点上。
void SearchCST(CSTree T,char keyword,CSTree *p)//查找插入位置 { if(T) { if(T->data == keyword) { *p = T; } if(p) { SearchCST(T->firstchild,keyword,p); SearchCST(T->nextsibling,keyword,p); } } } int Insert(CSTree T,char fa,char data)//数据插入 { CSTree pos = NULL,s; //pos记录新结点插入地址 if(T == NULL) { return 0; } SearchCST(T,fa,&pos); if(pos) //在树中找到插入结点地址 { s = (CSTree)malloc(sizeof(CSNode)); s->firstchild = s->nextsibling = NULL; s->data = data; if(pos->firstchild == NULL)//根的第一个孩子不存在则连上firstchild指针 { pos->firstchild = s; } else //根的第一个孩子存在，连上nextsibling末尾 { pos = pos->firstchild; while(pos->nextsibling) { pos = pos->nextsibling; } pos->nextsibling = s; } return 1; } else { printf("父结点数据输入错误，在树中找不到此结点数据\\n"); return 0; } }
二叉树结构数据的删除分2两种：
1.叶子结点直接删除
2.非叶子结点则删除此结点下的所有子结点
树结构中数据的删除分以下几个情况:
1.当删除结点为根结点时，直接摧毁整棵树
2.当删除结点为firstchild结点时，删除包括firstchild在内的下面的所有子结点
3.当删除结点是nextsibling结点时，删除包括nextsibling在内的下面的所有子结点，同时如果nextsibling不为NULL，则需连接
算法思路和插入差不多，先找到位置，然后根据不同的情况删除当前结点。
int DeletePoint(CSTree *T,char fa,char data) //删除一个结点 因为删除结点可能是树根，所以*T
{
CSTree p = NULL,s;
SearchCST(*T,fa,&p); //找父结点位置
if(fa == '#') //删除结点是树根的情况
{
CleanCSTree(*T);
*T = NULL;
return 1;
}
if(p == NULL)
{
return 0;
}
else //父结点找到，继续对子结点情况分类
{
if(p->firstchild->data == data) //删除结点是firstchild的情况
{
s = p->firstchild; //记住删除结点地址
p->firstchild = s->nextsibling; //连接上后面的结点
s->nextsibling = NULL;
CleanCSTree(s); //清空以删除结点为树根的树
}
else //删除结点是兄弟结点时
{
p = p->firstchild; //p指向第一个孩子结点
while(p->nextsibling && p->nextsibling->data != data) //用循环找到要删除的结点
{
p = p->nextsibling;
}
if(p->nextsibling->data == data) //此时p状态：p指向删除结点的前一个结点
{
s = p->nextsibling;
p->nextsibling = s->nextsibling; //将p的nextsibling连接到删除结点的后面一个结点
s->nextsibling = NULL;
CleanCSTree(s); //清空以删除结点为树根的树
return 1;
}
else //没有找到结点,删除失败
{
return 0;
}
}
}
return 1;
}数据结构与算法 树与二叉树
我们这篇博文介绍非线性结构―树与二叉树，我先介绍树的一些基本概念，树的遍历，再介绍二叉树相关概念和特性，以及二叉树的遍历，最后再树与二叉树的对比，总结。
树为了描述现实世界的层次结构，树结构中一个数据元素可以有两个或两个以上的直接后继元素。
树的基本概念：
树的概念是学习树的关键所在，掌握了树的基本概念，学会树与二叉树，so easy。我通过一棵树来了解树的基本概念，如下图
1、结点的度
结点的度是子结点的个数。例如：结点1有三个字结点2，3，4，所以结点1的度为3。
2、树的度
树的度等于所有结点度中度最高的值。例如：上图中结点度最高为3，所以树的度为3。
3、叶子结点
叶子结点是度为0的结点即没有子结点的结点。例如：上图中3，5，6，7，9，10。
4、分支结点
分支结点是除了叶子结点，树中的其他所有结点。例如：上面树的分支结点为1，2，4，8。
5、内部结点
内部结点是除了根结点以及叶子结点或在分支结点的基础之上在去掉根结点。例如：上面树的内部结点为2，4，8。
6、父结点、子结点、兄弟结点
父节点、子结点和兄弟结点是相对而言的。例如：结点1是结点2，3，4的父节点，结点2，3，4也是结点1的子结点，结点2，3，4又是兄弟结点。
7、层次
图中我们已经表出来了，根为第一层，根的孩子为第二层，依此类推，若某结点在第i层，则其孩子结点在第i+1层。
树的遍历
树的遍历特别简单，我们还是以上面的树为例：
1、前序遍历
基本思想：前序遍历就是先访问根结点，再访问叶子结点。
图中树的前序遍历为：1，2，5，6，7，3，4，8，9，10。
2、后序遍历
基本思想：本后序遍历就是先访问子结点，再访问根结点。
图中树的后序遍历为：5，6，7，2，3，9，10，8，4，1。
3、层次遍历
基本思想：从第一层开始，依此遍历每层，直到结束。
图中树的层次遍历为：1，2，3，4，5，6，7，8，9，10。
二叉树的一些相关概念和特性
学习二叉树的特性几乎可以帮助我们解决所有的二叉树问题，在学习二叉树特性一定要通过上面给出的二叉树进行实践，实践出真理，同时，印象也会更深刻。
一般二叉树性质：
在非空二叉树的k层上，至多有2k个节点(k>=0)
高度为k的二叉树中,最多有2k+1-1个节点(k>=0)
对于任何一棵非空的二叉树,如果叶节点个数为n0，度数为2的节点个数为n2，则有: n0 = n2 + 1
完全二叉树性质:
具有n个节点的完全二叉树的高度k为[log2n]
对于具有n个节点的完全二叉树,如果按照从上(根节点)到下(叶节点)和从左到右的顺序对二叉树中的所有节点从0开始到n-1进行编号,则对于任意的下标为k的节点，有：
如果k=0,则它是根节点，它没有父节点；如果k>0,则它的父节点的下标为[(i-1)/2];
如果2k+1 <= n-1,则下标为k的节点的左子结点的下标为2k+1;否则,下标为k的节点没有左子结点.
如果2k+2 <= n-1,则下标为k的节点的右子节点的下标为2k+2;否则,下标为k的节点没有右子节点
满二叉树性质:
在满二叉树中，叶节点的个数比分支节点的个数多1
二叉树遍历
1、前序遍历（与树的前序遍历一样）
基本思想：先访问根结点，再先序遍历左子树，最后再先序遍历右子树即根―左―右。
图中前序遍历结果是：1，2，4，5，7，8，3，6。
2、中序遍历
基本思想：先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树即左―根―右。
图中中序遍历结果是：4，2，7，8，5，1，3，6。
3、后序遍历
基本思想：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左―右―根。
图中后序遍历结果是：4，8，7，5，2，6，3，1。
4、层次遍历（与树的层次遍历一样）
基本思想：从第一层开始，依此遍历每层，直到结束。
图中层次遍历结果是：1，2，3，4，5，6，7，8。
树与二叉树区别
1、树可以有多个子结点，二叉树最多只能两个结点。
2、树中的子结点是无序的，二叉树是分左子结点和右子结点。
3、二叉树不是特殊树，而是独立的数据结构。