第五章树单元小结

水深无声 2022-01-06 14:45 309阅读 0赞

\---恢复内容开始---

这一章有三道编程作业

1.深入虎穴：虽然老师在上机的时候带着我们一起做了但是我按照老师说的做了之后还是有很多错误 从一开始的编译错误到段错误，到答案错误到最后的答案正确

先解释一下正确代码的意思，边解释边说遇到的问题

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<queue>
     3 using namespace std;
     4 
     5 typedef struct 
     6 {
     7     int doors;//每一扇门后面的通道数
     8     int *p;//把p看做一个整型数组，数组中包含具体指向的门的编号 
     9 }node;
    10 
    11 int input(node *&a);
    12 int find(node *a,int root);
    13 
    14 int main()
    15 {
         //定义变量
    16     node *a;//a[]可大可小，所以将它变成一个动态整型数组
    17     int i,j,root;
    18     root = input(a);
    19     cout<<find(a,root)<<endl;//从root开始，一层层往下遍历
    20     return 0; 
    21 }
    22 
    23 int input(node *&a)
    24 {
    25     int N;//一共有N扇门，在第一行输出
    26     cin>>N;
    27     int i,j,number;
    28     
    29     bool *vi;
    30     vi = new bool[N+1];//为了后续判断是否为根节点 
    31     a = new node[N+1];
    32      
    33     for(i=1;i<=N;i++)
    34     {
    35         vi[i] = false;//将vi数组初始化为false 
    36     }
    37     
    38     for(i=1;i<=N;++i)
    39     {
    40         cin >> number;//每扇门后的通道总数
    41         
    42         a[i].doors = number;
    43         
    44         a[i].p = new int[number];//每扇门后面对应的门牌号，构成一个数组
    45     //放若干个int,new的 有效空间是number+1，如果是number 后面j就要从0开始     
    46         for(j=0;j<number;++j)
    47         {
    48             cin >> a[i].p[j];
    49             
    50             vi[a[i].p[j]] = true; 
    51               //满足此循环条件的，即number>=1的，就将vi[a[i].p[i]]赋为true,即编号为a[i].p[i]的不为根节点
    52         } 
    53         
    54         
    55      } 
    56      
    57      for(i=1;i<=N;++i)
    58         if(!vi[i]) break;
    59         return i;
    60 
    61      
    62 }
    63 
    64 int find(node *a,int root)
    65 {
         //从数组的root下标开始往下搜索
    66 
    67      queue<int> q;//定义用于存放待访问的门编号的队列
    68      
    69      q.push(root);//根编号入队 
    70      
    71      int x,i;
    72      while(!q.empty())
    73      {
         //当队列不为空的时候
    74          x = q.front();//x在最前面，为出队 
    75         q.pop();//最后一个出队的就是最后一个进队的 就是最深处的那个 
    76         if(x!=0)
    77         {
    78         for(i=0;i<a[x].doors;i++)
    79         {
    80             q.push(a[x].p[i]);
    81         }     
    82         }
    83         
    84             
    85      
    86       } 
    87     return x; 
    88     
    89 }

深入虎穴正确的完整代码

![1628034-20190501162430628-1984329438.png][] →   →![1628034-20190501162906551-1753810895.png][]

1）一段段的解释

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 int input(node *&a)
     2 {
     3     int N;//一共有N扇门，在第一行输出
     4     cin>>N;
     5     int i,j,number;
     6     
     7     bool *vi;
     8     vi = new bool[N+1];//为了后续判断是否为根节点 
     9     a = new node[N+1];
    10      
    11     for(i=1;i<=N;i++)
    12     {
    13         vi[i] = false;//将vi数组初始化为false 
    14     }
    15     
    16     for(i=1;i<=N;++i)
    17     {
    18         cin >> number;//每扇门后的通道总数
    19         
    20         a[i].doors = number;
    21         
    22         a[i].p = new int[number];//每扇门后面对应的门牌号，构成一个数组
    23     //放若干个int,new的 有效空间是number+1，如果是number 后面j就要从0开始     
    24         for(j=0;j<number;++j)
    25         {
    26             cin >> a[i].p[j];
    27             
    28             vi[a[i].p[j]] = true; 
    29               //满足此循环条件的，即number>=1的，就将vi[a[i].p[i]]赋为true,即编号为a[i].p[i]的不为根节点
    30         } 
    31         
    32         
    33      } 
    34      
    35      for(i=1;i<=N;++i)
    36         if(!vi[i]) break;
    37         return i;
    38 
    39      
    40 }

input函数

input函数顾名思义就是将我们要输入的东西 放进去

![1628034-20190501153036336-489117850.jpg][]

先说说写这个函数的时候遇到的问题 刚开始老是显示编译错误

![1628034-20190501153234187-28937056.png][]因为刚开始一直都是（node \*a）后来参考了同学的改成（node \*&a）才变成正确的

然后我翻了一下C++的书 复习了一下指针

![1628034-20190501153431198-2021001659.png][]

我记得当时老师说的如果直接node \*a，无法直接传空间，node \*&可以间接传空间（听不懂...）(老师下次将指针和传空间的时候 可以讲的细点么）

然后我百度了一下+翻了C++的书 ，发现①&是取变量或者指针的地址；②\*是直接访问即取指针中的数据；③什么都不加，就是去该变量或指针中当前存储的数据

## ④\*a :在定义变量时表示的是一个指针类型的变量，而在代码中（执行部分）则表示取出该指针所指向内容的值。 ##

## 　　　\*a作为参数传入，那么在函数中便可以对a所指向的内存空间的值指直接进行修改；   \*&a:通常用于函数的传值，表示传入指针本身，不作复制 ##

**　\*&a作为参数传入，我们可以对指针本身这个数据，以及它所指向的数据进行修改。**

所以这里node \*&a 是要将整个指针传入 而不是只取值

![1628034-20190501161300066-408536578.png][]→   → ![1628034-20190501161316743-1542845346.png][]

![1628034-20190501161423367-1119161335.png][]→    →  ![1628034-20190501161501587-783114136.png][]

![1628034-20190501161725437-162244992.png][]   →      → ![1628034-20190501162316227-1461338150.png][]

2.List Leaves

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<queue>
     3 using namespace std;
     4  
     5 typedef struct
     6 {
     7     int lch;//左孩子
     8     int rch;//右孩子 
     9 }node; 
    10 
    11 int BuildTree(node t[]);
    12 void levelOrderTraverse(node t[],int root);
    13 
    14 int main()
    15 {
    16     node t[11];
    17     int root;
    18     
    19     root = BuildTree(t);
    20     
    21     levelOrderTraverse(t,root);
    22     return 0;
    23     
    24 }
    25 
    26 
    27 int BuildTree(node t[])
    28 {
    29     bool check[11]={
         false};
    30     int n;//一共有N个节点 
    31     cin>>n;
    32      
    33     char x,y;//因为有可能输入“-”所以定义为char 
    34     
    35     for(int i=0;i<n;i++)
    36     {
    37         cin >> x >> y;
    38         
    39         if(x!='-')
    40         {
    41             t[i].lch = x -'0';//两个ascall值相减就得到真正的值 
    42             check[t[i].lch] = true; 
    43             //如果该值曾经出现过 ，说明它曾经是某个点的子节点，说明它一定不是根节点，当最后只剩一个check[i]为false的时候 他就是根节点 
    44         }
    45         else
    46             t[i].lch = -1; //如果输入“-”，则给他赋值为-1 
    47             
    48         if(y!='-')
    49         {
    50             t[i].rch = y - '0';
    51             check[t[i].rch] = true;
    52         }
    53         else
    54             t[i].rch = -1;
    55              
    56     }
    57 
    58     for(int i=0;i<n;i++)
    59     {
         //寻找根节点，check 为false 的时候，说明它为根节点 
    60         if(!check[i]) return i;
    61      } 
    62 } 
    63 
    64 
    65 void levelOrderTraverse(node t[],int root)
    66 {
         //层次遍历t[x]为根节点的树t
    67     queue<int>q;
    68     q.push(root);//根节点入队
    69     int y;
    70 
    71     
    72     while(!q.empty())
    73     {
    74         y = q.front();
    75         q.pop();
    76         if(y!=-1)
    77         {
    78             if(t[y].lch!=-1) q.push(t[y].lch);
    79             if(t[y].rch!=-1) q.push(t[y].rch);
    80             if(t[y].lch == -1 && t[y].rch == -1 )  
    81             {
    82                 if(q.empty()) cout<<y;
    83                 else cout<<y<<" "; 
    84             }
    85     
    86         }         
    87             
    88      }      
    89  }

List leaves完整代码

其实 List leaves 和 深入虎穴很像 都是先构造树，找到根节点，再从根节点开始遍历，最后都是用队列的方式输出想要的东西

![1628034-20190501210438534-486657698.png][]

一段段解释

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 int BuildTree(node t[])
     2 {
     3     bool check[11]={
         false};
     4     int n;//一共有N个节点 
     5     cin>>n;
     6      
     7     char x,y;//因为有可能输入“-”所以定义为char 
     8     
     9     for(int i=0;i<n;i++)
    10     {
    11         cin >> x >> y;
    12         
    13         if(x!='-')
    14         {
    15             t[i].lch = x -'0';//两个ascall值相减就得到真正的值 
    16             check[t[i].lch] = true; 
    17             //如果该值曾经出现过 ，说明它曾经是某个点的子节点，说明它一定不是根节点，当最后只剩一个check[i]为false的时候 他就是根节点 
    18         }
    19         else
    20             t[i].lch = -1; //如果输入“-”，则给他赋值为-1 
    21             
    22         if(y!='-')
    23         {
    24             t[i].rch = y - '0';
    25             check[t[i].rch] = true;
    26         }
    27         else
    28             t[i].rch = -1;
    29              
    30     }
    31 
    32     for(int i=0;i<n;i++)
    33     {
         //寻找根节点，check 为false 的时候，说明它为根节点 
    34         if(!check[i]) return i;
    35      } 
    36 }

BuildTree

这其中最妙的就是利用ascall值减出真正的值

![1628034-20190501212308986-724008887.png][] 刚开始一直不知道该怎么办，因为输入的有可能是字符“-”有可能是数字刚开始想过用字符串来定义 但是后来听了老师上课讲的 发现用char定义 最后用ascall值 来减出数字 就觉得好秒妙

将二叉树 入队的方法跟深入虎穴的很像

![1628034-20190501212554610-391475099.png][]→ →![1628034-20190501212913775-288075154.png][]刚开始总想着要怎么样才能使最后一个输出的没有空格 想过用flag来标记 但是不知道怎么弄比较好 最后 反应过来 其实最后一个要先pop出来所以 此时用对空来判断就好

![1628034-20190501213054203-561466573.png][]这里找根节点的方法跟深入虎穴也很相似 就是如果该节点 没有出现过在其他节点的左右节点过 那它就是根节点 ，

check为false

3.树的同构

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 using namespace std;
     3 #define NULL -1 //将NULL定义为-1而不是0，因为数组下标为0的地方仍保存有节点 
     4 
     5 typedef struct
     6 {
         //定义二叉树节点
     7     char name;//节点名称 
     8     int lch; //左孩子
     9     int rch;//右孩子 
    10 }treenode;
    11 
    12 treenode T1[10];
    13 treenode T2[10];
    14  
    15 int BuildTree(treenode T[])
    16 {
    17     int Root = NULL,i;//刚开始将节点置为空，若为空树返回NULL
    18     char x,y;//左右节点 
    19     bool check[100] = {
         false};
    20     
    21     int N;//有N个节点 
    22     cin>>N;
    23     if(N)//若不为空树 
    24     {
    25         for(i = 0;i<N;i++)
    26     {
    27         cin >> T[i].name >> x >> y;
    28         if(x!='-')
    29         {
    30             T[i].lch = x-'0';
    31             check[T[i].lch] = true;
    32         }
    33         else
    34             T[i].lch = -1;
    35         
    36         if(y!='-')
    37         {
    38             T[i].rch = y - '0';
    39             check[T[i].rch] = true;
    40         }
    41         else
    42             T[i].rch = -1;
    43     }
    44     
    45     for(i=0;i<N;i++)
    46         if(!check[i]) break;
    47     Root = i; 
    48     }
    49     return Root;
    50  } 
    51 
    52 int lsomorphic(int x,int y)
    53 {
    54     if((x == NULL)&&(y == NULL))//如果两棵树都为空树 则同构
    55         return 1;
    56     if(((x == NULL)&&(y != NULL)) || ((x!=NULL)&&(y == NULL)))//如果一个树为空一个树不为空则不是同构的
    57         return 0;
    58     if((T1[x].name)!=(T2[y].name))//如果数据不同则不是同构
    59         return 0;
    60     //如果左孩子都为空则判断右孩子是否同构：主要看三个方面（1）右孩子是否都为空；（2）是否一棵树有右孩子，一棵树没有右孩子；（3）右孩子的数据是否相同
    61     if((T1[x].lch==NULL)&&(T2[y].lch==NULL))
    62         return lsomorphic(T1[x].rch,T2[y].rch); 
    63     //如果两棵树的左孩子都不为空并且数据都一样，对左孩子进行递归
    64     if(((T1[x].lch!=NULL)&&(T2[y].lch!=NULL))&&((T1[T1[x].lch].name)==(T2[T2[y].lch].name))) 
    65         return(lsomorphic(T1[x].lch,T2[y].lch)&&lsomorphic(T1[x].rch,T2[y].rch));
    66     //如果两棵树左孩子（一个为空一个不空或者都不空）并且数据不一样，那么判断第一节树的左（右)孩子是否跟第二棵树的右（左）孩子同构
    67     else
    68         return(lsomorphic(T1[x].lch,T2[y].rch)&&lsomorphic(T1[x].rch,T2[y].lch));    
    69         
    70 }
    71  
    72 int main()
    73 {
    74     int x,y;//首先建立两棵树，x,y为树的根节点
    75     x = BuildTree(T1);
    76     y = BuildTree(T2);
    77     if(lsomorphic(x,y)) 
    78         cout<<"Yes";
    79     else 
    80         cout<<"No";
    81     return 0;
    82 }
    83  
    84  
    85  
    86  
    87  
    88  
    89  
    90  
    91  
    92  
    93  
    94  
    95  
    96

树的同构完整代码

树的同构这道题 其实和前两道题有一部分是很相似的，就是在构造树这里 都是要输入 节点名 然后输入左右节点 然后从根节点开始遍历

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 int BuildTree(treenode T[])
     2 {
     3     int Root = NULL,i;//刚开始将节点置为空，若为空树返回NULL
     4     char x,y;//左右节点 
     5     bool check[100] = {
         false};
     6     
     7     int N;//有N个节点 
     8     cin>>N;
     9     if(N)//若不为空树 
    10     {
    11         for(i = 0;i<N;i++)
    12     {
    13         cin >> T[i].name >> x >> y;
    14         if(x!='-')
    15         {
    16             T[i].lch = x-'0';
    17             check[T[i].lch] = true;
    18         }
    19         else
    20             T[i].lch = -1;
    21         
    22         if(y!='-')
    23         {
    24             T[i].rch = y - '0';
    25             check[T[i].rch] = true;
    26         }
    27         else
    28             T[i].rch = -1;
    29     }
    30     
    31     for(i=0;i<N;i++)
    32         if(!check[i]) break;
    33     Root = i; 
    34     }
    35     return Root;
    36  }

BuildTree

并且都是用 bool check 的形式来找根节点，但是由于后面要判断是不是树的同构 前面还加了一个判断树是否为空

![1628034-20190502115818404-1605710266.png][]  ![1628034-20190502115834563-1995105605.png][]

最难想的点应该就是怎么判断是不是树的同构，分了很多种情况

![1628034-20190502115912780-1807096765.png][]

两棵树同构：

①两棵树都为空；②如果两棵树的左孩子都为空 ，则判断右孩子，此时用到了递归![1628034-20190502120246371-381308097.png][]再开始遍历右孩子

③如果两棵树的左孩子都不为空且数据相同 则对左孩子递归

![1628034-20190502130503761-480552281.png][]

④如果两棵树的左孩子一个为空 一个不为空 或者数据不同 则判断 是不是 两棵树的左右孩子调换过来

![1628034-20190502130653522-1161872219.png][]

转载于:https://www.cnblogs.com/snowlxy/p/10802114.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211227/beebe0447f9141c8a915f8f7a80892ee.png
[1628034-20190501162430628-1984329438.png]: https://img2018.cnblogs.com/blog/1628034/201905/1628034-20190501162430628-1984329438.png
[1628034-20190501162906551-1753810895.png]: /images/20211227/eab03202015545c9aac808b93e2b2f89.png
[1628034-20190501153036336-489117850.jpg]: /images/20211227/927be33b882d4aa5a3183126eaba36e4.png
[1628034-20190501153234187-28937056.png]: /images/20211227/7308390acf4d4540b6a929ce9a07a0d8.png
[1628034-20190501153431198-2021001659.png]: /images/20211227/fc66aedca0d94f35b0d7c30b5a6dd5f0.png
[1628034-20190501161300066-408536578.png]: https://img2018.cnblogs.com/blog/1628034/201905/1628034-20190501161300066-408536578.png
[1628034-20190501161316743-1542845346.png]: /images/20211227/47836108acc54dad924680501a2def57.png
[1628034-20190501161423367-1119161335.png]: https://img2018.cnblogs.com/blog/1628034/201905/1628034-20190501161423367-1119161335.png
[1628034-20190501161501587-783114136.png]: /images/20211227/f5b7c820c3a34e92a67962991f391926.png
[1628034-20190501161725437-162244992.png]: https://img2018.cnblogs.com/blog/1628034/201905/1628034-20190501161725437-162244992.png
[1628034-20190501162316227-1461338150.png]: /images/20211227/4af7b5e8eb3748ce9b015810561778da.png
[1628034-20190501210438534-486657698.png]: /images/20211227/17dee0a69b984efa82ce06c92ccf95b2.png
[1628034-20190501212308986-724008887.png]: /images/20211227/3d177e75465b40e9b8dd20b4fdd7c88d.png
[1628034-20190501212554610-391475099.png]: https://img2018.cnblogs.com/blog/1628034/201905/1628034-20190501212554610-391475099.png
[1628034-20190501212913775-288075154.png]: /images/20211227/1ee3eae33e1a4e3a93994a27692ce44d.png
[1628034-20190501213054203-561466573.png]: /images/20211227/7dbe14f47d0f4c4d9d1fcf86a44fff4d.png
[1628034-20190502115818404-1605710266.png]: https://img2018.cnblogs.com/blog/1628034/201905/1628034-20190502115818404-1605710266.png
[1628034-20190502115834563-1995105605.png]: /images/20211227/ccd831d2250148edaca220b294368a89.png
[1628034-20190502115912780-1807096765.png]: /images/20211227/2a97448cb6544557b68b75881c9f5a1f.png
[1628034-20190502120246371-381308097.png]: /images/20211227/48d7984825a642b39629ae8134cb2065.png
[1628034-20190502130503761-480552281.png]: /images/20211227/5dc830e629df48a1ae97c4510968f96d.png
[1628034-20190502130653522-1161872219.png]: /images/20211227/1bbe55b5d11c4b62beabd14e078f1fdc.png