小程序开发入门教程_网页制作计算机培训文案_网络销售平台排名前十_南京谷歌推广

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最终为4int subdegree=getDegree(pchild); //subdergg本质还是degree是子函数返回的degreeif(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);}
}