文章目录
- 1.设计算法构造一棵先序线索二叉树
- 2.先序线索二叉树的先序遍历算法
- 3.设计算法构造一棵中序线索二叉树
- 4.遍历中序线索二叉树
- 5.树的先根遍历和后根遍历
- 6.树T的叶子结点个数
- 7.计算一棵以孩子兄弟表示的树T的度，该算法的时间复杂度为O(n)
- 8.计算树孩子兄弟链表表示的T的深度
- 9.森林的遍历
1.设计算法构造一棵先序线索二叉树
在构建先序线索二叉树的过程中，最值得说明的就是中间的核心操作，T代表当前的指针，pre代表它的前一个指针。
先序序列:ABCDE
BiTNode *pre = NULL; // 定义一个全局变量，保存当前结点的前驱结点
void preOrderThreading(BiTree T) //先序线索化二叉树
{
//对根节点处理
if(T==NULL) return; //该结点是空树，则啥也不干
if(T->lchild==NULL)
{
T->ltag=1;
T->lchild=pre;
printf("%d %c %d\n",T->ltag,T->data,T->rtag);
}
if(pre!=NULL&&pre->rchild==NULL) //为什么pre要不等于空，因为后面要用到pre->rchild.NULL是没有右孩子的，如调用会报错
{
pre->rtag=1;
pre->rchild=T;
printf("%d %c %d\n",pre->ltag,pre->data,pre->rtag);
}
//在先序线索化的过程中，我们需要遍历整棵二叉树。递归调用 PreThreading 函数时，必须确保不在递归过程中错误地访问线索指针，这就是为什么需要检查 ltag 和 rtag 的原因。
pre=T; //进入T的子树前，将pre指针后移
if(T->ltag==0) preOrderThreading(T->lchild);
if(T->rtag==0) preOrderThreading(T->rchild);
}
void creatthreadtree(BiTree T)
{
pre=NULL;
if(T!=NULL)
{
preOrderThreading(T);
if(pre->rchild==NULL)
{
T->rtag=1;
}
}
}
2.先序线索二叉树的先序遍历算法
先序线索二叉树就不需要常规二叉树那种递归遍历的方法，而是线性的遍历。
大体上来说，先序线索化二叉树的前驱结点(第一个结点)肯定是根节点，从它出现，开始进行先序遍历，无非有下面的几种情况。
1.存在左孩子，左孩子就是它的下一个结点
2.不存在左孩子，右孩子就是它的下一个结点
3.既不存在左孩子，又不存在右孩子，那么就访问它的线索，即右孩子指向的后继结点
其中，情况2和情况3操作的过程是一样的，所以，写代码的过程中，归为一种。
综上所述，写代码时就是1+23
//前序线索二叉树的遍历
void preOrderTravers(BiTree T)
{
BiTNode *preNode=T; //找到根节点，定义操作根节点的指针,定义前驱结点，也就是第一个结点的指针
// int sum=1;
while(preNode!=NULL)
{
// printf("当前是第%d次循环:",sum); sum++;
if(preNode->ltag==0) //如果它有左孩子且非线索，左孩子就是它的下一个结点
{
printf("%c",preNode->data);
preNode=preNode->lchild;
}else{ //如果它没有左孩子，有右孩子或者既没有右孩子，又没有左孩子，存在线索
printf("%c",preNode->data);
preNode=preNode->rchild;
}
}
}
3.设计算法构造一棵中序线索二叉树
中序遍历二叉树：CDBAE(左根右)
通过中序线索二叉树和通过前序线索二叉树
在处理根节点的过程是一样的，区别在于。
中序遍历，先访问处理左子树，再处理根节点，最后访问处理右子树
前序遍历，先处理根节点，再访问处理左子树，最后访问处理右子树
中序线索化访问子树的过程，不需要像前序线索化那样，判断ltag和rtag，因为，在前序的过程中，要先处理根节点，再处理左子树，左子树处理完，回到根节点，再处理右子树，如果不判断，根节点就会乱套，但是中序就没有这个烦恼，因为先访问左子树。
void inOrderThreading(BiTree T) //中序线索化二叉树
{
//对根节点处理
if(T==NULL) return; //该结点是空树，则啥也不干
inOrderThreading(T->lchild);
if(T->lchild==NULL)
{
T->ltag=1;
T->lchild=pre;
printf("%d %c %d\n",T->ltag,T->data,T->rtag);
}
if(pre!=NULL&&pre->rchild==NULL) //为什么pre要不等于空，因为后面要用到pre->rchild.NULL是没有右孩子的，如调用会报错
{
pre->rtag=1;
pre->rchild=T;
printf("%d %c %d\n",pre->ltag,pre->data,pre->rtag);
}
//在中序线索化的过程中，我们需要遍历整棵二叉树。递归调用 PreThreading 函数时，必须确保不在递归过程中错误地访问线索指针，这就是为什么需要检查 ltag 和 rtag 的原因。
pre=T; //进入T的子树前，将pre指针后移
inOrderThreading(T->rchild);
}
void creatthreadtree_byinorder(BiTree T)
{
pre=NULL;
if(T!=NULL)
{
inOrderThreading(T);
if(pre->rchild==NULL)
{
T->rtag=1;
}
}
}
4.遍历中序线索二叉树
因为是从根开始的遍历(左根右)所以，根之后只找右孩子，每一次寻找最左结点的过程就已经包含了找左这个过程
中序遍历二叉树：CDBAE(左根右)
根节点为左子树最左结点，设置一个函数get_mostleftnode(),得到一个结点的左子树的最左结点(非线索纯图的最左结点)。
无非有下面的几种情况。
1.找左的过程已经被封装好了
2.存在右子树，右子树的最左结点就是它的后继
3.如果没有左子树，也没有右子树，存在线索，访问线索后继即可
if后继有线索，后继线索，没线索的话就找在右孩子里找最左
BiTNode *getinorderFirstNode(BiTree T)
{
BiTNode *p=T;
while (p!=NULL&&p->ltag==0) { //注意这里不能是p->lchild!=NULL,因为线索会扰乱我们要寻找的最左结点
p=p->lchild; //补上一个p!=NULL,防止NULL->ltag，其实不用，如果我们传的不少空树的话
}
return p;
}
//中序线索二叉树的遍历
void inOrderTravers(BiTree T)
{
BiTNode *preNode=getinorderFirstNode(T); //找到根节点，定义操作根节点的指针,定义前驱结点，也就是第一个结点的指针
while(preNode!=NULL)
{
printf("%c",preNode->data);
if(preNode->rtag==1)
{
preNode=preNode->rchild;
}else{ //存在左孩子或者存在右孩子
preNode=getinorderFirstNode(preNode->rchild);
}
}
}
5.树的先根遍历和后根遍历
这种遍历方法是基于树已经被孩子兄弟表示法存储好了
树的先根遍历：先遍历根节点，再遍历子树，等价于二叉树的中序遍历，先访问根节点，再访问左右子树
树的后根遍历：：先遍历根节点，再遍历子树，等价于二叉树的后序遍历
// 定义存储结构
typedef struct CSTNode
{
int data;
struct CSTNode *fristChild;
struct CSTNode *nextSibling;
}CSTNode,*CSTree;
//树的先根遍历，就是先访问根节点，后访问它的子树
void preOrderTraverse(CSTree T)
{
if(T!=NULL)
{
printf("%d",T->data); //访问根
CSTNode * pCurChild=T->fristChild;
while(pCurChild!=NULL)
{
preOrderTraverse(pCurChild);
pCurChild=pCurChild->nextSibling; //指向另一棵子树根
}
}
}
void postOrderTraverse(CSTree T)
{
if(T!=NULL)
{
CSTNode * pCurChild=T->fristChild;
while(pCurChild!=NULL)
{
postOrderTraverse(pCurChild);
pCurChild=pCurChild->nextSibling; //指向另一棵子树根
}
printf("%d",T->data); //访问根
}
}
6.树T的叶子结点个数
思路:
先根遍历子树，若访问到根节点，则计数器+1
int count=0;
int getLeaves(CSTree T)
{
if(T->fristChild==NULL) count++;
else{
for(CSTNode *pchild=T->fristChild;pchild!=NULL;pchild=pchild->nextSibling) //圈（1）+圈（2）
{
getLeaves(pchild); //圈（3）
}
}
return count;
}
7.计算一棵以孩子兄弟表示的树T的度，该算法的时间复杂度为O(n)
对于一个结点来说，它的度是它最孩子连同它全部右孩子的个数
树用孩子兄弟表示，它的遍历，是先遍历到最左结点，然后从下往上向右搜
//统计一个结点的左孩子连同左孩子的右孩子的最大数量
int getDegree(CSTree T)
{
if(T==NULL) return 0;
else{
int maxDegree=0;
int degree=0; //根节点的度
for(CSTNode *pchild=T->fristChild;pchild!=NULL;pchild=pchild->nextSibling)
{
degree++; //for循环执行4次，degree最终为4
int subdegree=getDegree(pchild); //subdergg本质还是degree是子函数返回的degree
if(subdegree>maxDegree)maxDegree=subdegree;
}
return degree>maxDegree?degree:maxDegree;
}
}
8.计算树孩子兄弟链表表示的T的深度
/树T的深度，主要看左孩子，最深到哪，因为右孩子全是同级的，
int getHeight(CSTree T)
{
if(T==NULL) return 0;
else{
int maxheight=0;
int height=0;
for(CSTNode *pchild=T->fristChild;pchild!=NULL;pchild=pchild->nextSibling)
{
int subheight=getHeight(pchild);//每一个结点求它的子树高度
if(subheight>maxheight)maxheight=subheight;
}
return maxheight+1; //往深了加
}
}
9.森林的遍历
把森林的多棵树的根节点用虚拟的根节点连接，就变成了一棵大树，然后还是兄弟孩子结点表示法
森林中，一棵树和其他树，遍历的时候一定是遍历完这棵树，再遍历其他树
这棵树的遍历有两种，一种树先根遍历，一种是后根
先根遍历，根，根的子树，再遍历其他树，类似于先序遍历，森林的(类)先序遍历
后根遍历，根的子树，根，再遍历其他树，类似于中序遍历，森林的(类)中序遍历
9.1 森林的先根遍历
比树的先根遍历，就多一步
void preOrderTraverse(CSTree T)
{
if(T!=NULL)
{
printf("%d",T->data); //访问根
CSTNode * pCurChild=T->fristChild;
while(pCurChild!=NULL)
{
preOrderTraverse(pCurChild);
pCurChild=pCurChild->nextSibling; //指向另一棵子树根
}
preOrderTraverse(T->nextSibling);//若为先根遍历树，就把这个删除
}
}
9.2 森林的后根遍历
void postOrderTraverse(CSTree T)
{
if(T!=NULL)
{
CSTNode * pCurChild=T->fristChild;
while(pCurChild!=NULL)
{
postOrderTraverse(pCurChild);
pCurChild=pCurChild->nextSibling; //指向另一棵子树根
}
printf("%d",T->data); //访问根
postOrderTraverse(T->nextSibling);
}
}