树和森林

绝地灬酷狼 2021-09-11 00:04 336阅读 0赞

树的存储结构  
\- 一维数组表示：利用数组的下标  
![这里写图片描述][20160605143823084]  
![这里写图片描述][20160605144246261]

- 链表表示
    
    
     - 孩子链表
         - ![这里写图片描述](https://img-blog.csdn.net/20160605145651514)
         - 终端结点后为空
         - 有孩子的结点用next域存储孩子结点的地址
    
     - 孩子兄弟表示法（二叉树表示法）
         - 结点结构 lchild  data  sibling
         - ![这里写图片描述](https://img-blog.csdn.net/20160605151524537)

如果已知一个树的先根序列和每个结点相应的度，则能唯一确定该树的结构  
结点的度就是拥有孩子的个数

--------------------

*  树转换成二叉树
    
     *  所有兄弟结点之间加一条连线
     *  对每个结点，只保留左边的孩子，其它孩子的连线去掉
     *  顺时针旋转45°
     *  ![这里写图片描述][20160605152901264]
 *  二叉树转换成树（逆运算）

--------------------

## 森林与二叉树的转换 ##

森林转换成二叉树原则
    设森林f=（t1，t2,,,tn）
    表示由树t1,t2,,,tn组成的森林
    自然对应下森林f的二叉树b递归定义
        n=0，则为空
        n>0，则b（f）的根是root（t1）,右子树是（t2,,,tn）,左子树是（t11，t22,,,t1m）
            其中t11,t12,,,t1m，是root（t1）诸子树
    
    树转换成的二叉树没有右子树
    将转换成的二叉树依次接到上一个二叉树的右边

--------------------

## 二叉树转换成森林 ##

如果b=（root,lb,rb）是一颗二叉树，则可按如下规则转换成森林f=(t2,t2,,,tn)
    b为空，则f为空
    若b非空，则f中第一棵树t1的根root(t1)即为二叉树b的根root，t1中根节点的子树森林f1是由b的左子树lb转换而成的森林
    f中除t1之外其余树组成的森林f=(t2,,,tn)是由b的右子树rb转换而成的森林

--------------------

## 树的遍历 ##

先根遍历
    先访问树的根节点，然后依次先根遍历每棵子树
    
    后根遍历
    先后根遍历每棵子树，然后访问树的根结点

--------------------

## 森林的遍历 ##

先根森林遍历
        访问森林中第一棵树的根结点
        先序遍历第一棵树中根节点的子树森林
        先序遍历其余的树构成的森林
    
    后根遍历森林
        后序遍历第一棵树的子树森林
        访问森林中第一棵树的根结点
        后序遍历其余的树构成的森林

--------------------

## 二叉树遍历的应用 ##

统计二叉树中叶结点的个数  
template  
void bintree:: countleaf(bintreenode \*t,int &count)  
\{  
if（t!=null）  
\{  
if((t->left == null)&&(t->right == null))//以左右孩子是否等于空为依据来判定该结点是否为终端节点  
count++;  
countleaf(t->left,count);  
countleaf(t->right,count);  
\}  
\}  
//先根遍历的递归算法

[20160605143823084]: /images/20210813/d5570177b4e84db48c0a341db300c613.png
[20160605144246261]: /images/20210813/0b293ffa2d0e42a390b768ccdfb23607.png
[20160605152901264]: /images/20210813/e2d38d1c620a43d29f0c9853ac9c3496.png